PaperlayerView exact revision on arXiv

Source-linked AI summary

A Grand Unification of Quantum Algorithms

John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang

arXiv:2105.02859v5quant-ph

TL;DR

The paper addresses how major quantum algorithms can be understood within a common framework rather than as unrelated constructions. It develops QSVT from QSP and applies it to search, phase estimation, simulation, and related problems, concluding that these algorithms share a parameterized structure while retaining important block-encoding constraints.

  • Problem

    Major quantum algorithms solve problems with classical counterparts but appear to obtain speedups through different structures, motivating a framework that relates them.

  • Method

    The paper gives a pedagogical development from QSP to quantum eigenvalue transforms and QSVT, then constructs algorithms using block-encoded operators and parameterized polynomial transformations.

  • Results

    QSVT-based constructions cover search, Hamiltonian simulation, the quantum linear systems problem, eigenvalue thresholding, and phase estimation.

  • Takeaways & Limitations

    QSVT supplies a parameterized lens for relating quantum algorithms and analyzing how problem structure connects with quantum algorithmic efficiency.

  • Takeaways & Limitations

    QSVT requires block encodings, and its runtime can depend linearly on a matrix normalization such as ∥A∥F or the corresponding scaling parameter.

Abstract

from arXiv · show

Quantum algorithms offer significant speedups over their classical counterparts for a variety of problems. The strongest arguments for this advantage are borne by algorithms for quantum search, quantum phase estimation, and Hamiltonian simulation, which appear as subroutines for large families of composite quantum algorithms. A number of these quantum algorithms were recently tied together by a novel technique known as the quantum singular value transformation (QSVT), which enables one to perform a polynomial transformation of the singular values of a linear operator embedded in a unitary matrix. In the seminal GSLW'19 paper on QSVT [Gilyén, Su, Low, and Wiebe, ACM STOC 2019], many algorithms are encompassed, including amplitude amplification, methods for the quantum linear systems problem, and quantum simulation. Here, we provide a pedagogical tutorial through these developments, first illustrating how quantum signal processing may be generalized to the quantum eigenvalue transform, from which QSVT naturally emerges. Paralleling GSLW'19, we then employ QSVT to construct intuitive quantum algorithms for search, phase estimation, and Hamiltonian simulation, and also showcase algorithms for the eigenvalue threshold problem and matrix inversion. This overview illustrates how QSVT is a single framework comprising the three major quantum algorithms, thus suggesting a grand unification of quantum algorithms.

I. INTRODUCTION

The paper frames QSVT as a unified approach to quantum algorithms that transforms singular values of block-encoded operators and encompasses search, phase estimation, and Hamiltonian simulation. It develops this framework pedagogically from QSP and uses it to derive several quantum algorithms and their common structure.

  • Motivation: Quantum circuits are unitary and reversible, creating a challenge when representing generally irreversible Boolean functions.Reversible embeddings address this challenge with small space and time overhead, but Grover search and Hamiltonian simulation do not rely on such embeddings.
  • Quantum singular value transformation: QSVT generalizes QSP to polynomially transform the singular values of a linear operator embedded in a larger unitary.Its phase angles parameterize the desired transformation, while block encodings connect the multi-qubit operator to the QSP construction.
  • Applications: QSVT provides a common framework for quantum search, phase estimation, Hamiltonian simulation, matrix inversion, and eigenvalue thresholding.The algorithms use natural oracles, repeated QSVT sequences, simple gates, and measurements.
  • Quantum signal processing: QSP interleaves fixed-angle signal rotations with variable-angle processing rotations to implement polynomial transformations of an input signal.For suitable polynomials, a corresponding sequence of QSP phase angles exists.
  • Quantum signal processing: QSP phase sequences can sharpen signal discrimination: the BB1 sequence keeps transition probability near one over a wider signal-angle range before a sharp transition near θ ≈ 2π/3.This illustrates how polynomial transformations can increase sensitivity to selected signal values.
  • Amplitude amplification: Amplitude amplification can be performed obliviously without knowing the initial overlap, by choosing QSVT phases whose polynomial approximates the sign function.A Grover-like phase choice increases the target matrix element over approximately ⌈π/(2 sin−1 a)⌉ steps.

C. Quantum Eigenvalue Transforms

The quantum eigenvalue transform extends quantum signal processing from amplitudes to polynomial transformations of all eigenvalues of a block-encoded Hamiltonian. Projector-controlled phase shifts act across the encoded subspace, enabling eigenvalue filtering and threshold detection.

  • Eigenvalue transformation: The eigenvalue transform polynomially transforms all eigenvalues of a Hamiltonian embedded in a block of a unitary.The transformation generalizes amplitude amplification from one matrix element to an entire vector space.
  • Block encoding: A block encoding places H in a selected unitary subblock identified by a projector, with ∥H∥≤1 assumed for the illustrative construction.The text notes that rescaling H/α can handle larger operator norms.
  • Bloch-sphere picture: The specialized encoding decomposes into N separate Bloch spheres, one for each eigenspace, where R(λ) supplies the eigenvalue-dependent rotation.This decomposition lets the sequence be analyzed using quantum signal processing on each eigenvalue.
  • Signal processing rotations: Projector-controlled phase shifts apply a phase to the projector-defined subspace and act as z-axis rotations on each Bloch sphere.The circuit can be implemented with two projector-controlled-NOT operations around a single-qubit z-rotation.
  • Eigenvalue filtering: QSP phases can selectively filter eigenvalues, such as distinguishing whether a Hamiltonian has an eigenvalue above a threshold.The procedure assumes an input state with nonzero overlap on relevant eigenstates; amplitude amplification can boost the signal.

D. Quantum Singular Value Transforms

The quantum singular value transform extends the eigenvalue-transform framework to possibly rectangular block-encoded matrices. QSVT applies parity-constrained polynomial transformations to singular values while tracking transitions between left and right singular-vector spaces.

  • Singular value transformation: QSVT polynomially transforms all singular values of a possibly non-square matrix encoded in a unitary block.This extends eigenvalue transformation to matrices without a well-defined eigenvalue set.
  • Singular-value structure: A singular value decomposition supplies singular values σ_k and orthonormal left and right singular-vector bases for the encoded matrix.The singular values are the nonnegative diagonal entries of the SVD, with r = rank(A) nonzero values.
  • Block encoding: The block encoding uses projectors to locate A within U and identify its left and right singular-vector spaces.The projectors select the encoded columns and rows, respectively.
  • Bloch-sphere representation: The specialized encoding decomposes U into Bloch-sphere components indexed by the rank of A, with rotations determined by each singular value.This parallels the eigenvalue-transform construction using eigenvalue-dependent Bloch spheres.
  • Polynomial transformations: Odd and even QSVT sequences implement singular-value polynomials of degree at most d satisfying the QSP conditions.Even-polynomial transformations can return both input and output to the right singular-vector space.
  • Basis switching: Unlike the eigenvalue transform, QSVT switches between right and left singular-vector bases during the Bloch-sphere transformations.This basis switching is the key modification needed for rectangular operators.

E. Block Encodings

Block encodings embed a target operator inside a larger unitary so QSP and QSVT can process it, but constructing and accessing the encoded block require additional operations. The tutorial applies this framework to QSVT-based search, retaining quadratic speedup while avoiding Grover iteration convergence issues.

  • Block encodings: Block-encoded operators are quantum embeddings of a matrix inside a larger unitary and form the starting point for many QSP and QSVT applications.For unitary A, the larger unitary can be a controlled-A operation.
  • Construction constraints: Constructing controlled-A for a large operator generally requires system-specific information and may not be possible from A alone.Given a +1 eigenstate, a controlled-A circuit can be built with two controlled-SWAP gates.
  • Accessing the transformed block: After a QSP or QSVT sequence, a final signal-basis measurement can test whether the desired polynomial-transformed block was applied.The success probability can be amplified using amplitude amplification or classical repetition.
  • Search by QSVT: Unstructured search encodes the initial-to-marked-state amplitude as a single singular value a = 1/√N and uses QSVT to transform it toward unit magnitude.The construction starts from a uniform superposition and targets the marked state.
  • Search result: QSVT search preserves O(√N) scaling and provides a provably optimal quadratic speedup while circumventing Grover search’s convergence issues.The method applies a predetermined polynomial transformation rather than repeatedly using the Grover iterate.
  • Search guarantee: The transformed search state has amplitude at least 1 − ϵ on the marked state, giving measurement probability at least (1−ϵ)^2 ≥ 1−2ϵ.Setting ϵ = δ/2 yields success probability at least 1 − δ.
  • QSVT advantage: This search instance illustrates QSVT’s ability to transform between different input and output spaces, unlike the quantum eigenvalue transform.The relevant singular vectors are the initial state and marked state rather than identical input and output spaces.

IV. THE EIGENVALUE THRESHOLD PROBLEM BY QSVT

The eigenvalue threshold problem distinguishes whether a Hamiltonian has an eigenvalue below a chosen threshold or whether all eigenvalues lie above it. QSVT solves this by filtering eigenvalues and measuring an ancilla qubit.

  • Problem: The problem distinguishes between an eigenvalue λ ≤ λth − ∆λ and all eigenvalues λ ≥ λth + ∆λ.The input state has reasonable overlap with the low-energy subspace when it exists.
  • Block encoding: The Hamiltonian must be block encoded as H/α for a known α ≥ ∥H∥, which can be nontrivial to determine in general.The paper notes that sparse Hamiltonians and linear combinations of terms provide important classes where this can be handled.
  • Polynomial construction: QSVT applies a polynomial filter that behaves differently below and above the threshold λth/α.The construction uses a symmetrized polynomial with definite parity and magnitude bounded by 1 so that QSVT can implement it.
  • Measurement: Measuring the ancilla distinguishes the cases because low eigenvalues increase the probability of measuring |0⟩, whereas spectra entirely above the threshold make |0⟩ unlikely.If an eigenvalue satisfies λ < λth − ∆λ, the |0⟩ outcome is more likely; if all eigenvalues exceed λth + ∆λ, it is unlikely.
  • Success probability: Repeated measurements reduce the threshold decision to distinguishing Bernoulli distributions with separated means.The separation is controlled by the overlap ζ and polynomial error ϵ.
  • Complexity: The presented analysis has a 1/ζ^2 dependence, although the paper notes that Lemma 7 of [40] improves this to 1/ζ.

V. PHASE ESTIMATION BY QSVT

QSVT-based phase estimation determines the phase of a unitary eigenvector through an iterative feedback procedure. Each iteration extracts one phase bit by transforming singular values and measuring an ancilla.

  • Algorithm overview: Given U|u⟩ = e2πiϕ|u⟩, the algorithm estimates the eigenphase ϕ using a parameter θ initialized at zero and updated iteratively.
  • Bit extraction: The procedure determines ϕ bit by bit, beginning with the least significant bit and proceeding toward the most significant bit.At each step, a matrix is constructed whose singular values encode previously determined bits and the current θ.
  • QSVT step: QSVT transforms the singular values of Aj(θ), and the Figure 9 circuit measurement determines the next phase bit before θ is updated.
  • Interpretation: The construction is presented as a binary search through the bits of ϕ, enabled by transforming singular values according to the current feedback parameter.
  • Accuracy: If n ≥ m and the sign function is exactly implementable, the procedure outputs θ = ϕ.
  • Accuracy: If n < m, including m = ∞, the output obeys |θ − ϕ| ≤ 2^−n−1.Thus the procedure produces an n-bit approximation even when the phase has more than n bits.

2. Caveats

The phase-estimation sketch requires several implementation and approximation caveats. The paper addresses block encoding, sign-function approximation, and the resulting accuracy and failure-probability conditions.

  • Block encoding: The matrix Aj(θ) requires a unitary block encoding, constructed by the circuit Wj(θ) shown in Figure 10.
  • Polynomial approximation: The exact sign function cannot be implemented through QSVT, so the algorithm replaces it with an even, bounded phase-estimation polynomial.
  • Gap error: A nonzero approximation gap ∆ can cause an error at one iteration, but under the stated bound its final phase error is at most 2^−n.
  • Approximation error: A nonzero polynomial error ϵ can cause an incorrect measurement at any iteration, with per-iteration failure probability scaling as O(ϵ^2).
  • Success guarantee: Choosing the approximation parameters so that each of n iterations fails with probability at most δ/n yields overall success probability at least 1 − δ.

B. The Complete Algorithm

Algorithm 3 performs phase estimation by iteratively determining bits of an eigenphase through cascaded QSVT operations and adaptive measurement feed-forward. It outputs an n-bit approximation with stated success probability and query complexity, and can also support factoring.

  • Procedure: Each iteration measures an ancilla, records a phase bit in θ, and repeats the procedure adaptively.Measurement results are fed forward through θ to future controlled QSVT operations.
  • Procedure: The algorithm includes an additional iteration for the ones-place bit when n < m, requiring ϵ ≤ 2δ/(n + 1) for success probability at least 1 − δ.Typically θ0 = 0, but θ0 = 1 can occur when 1.0 is a good approximation to ϕ.
  • Complexity: The circuit consists of O(n) QSVT iterations, with each sequence having a degree-dependent query cost.The supplied text states that the resulting oracle query complexity is O(n log n).
  • Factoring: Replacing the eigenstate by a uniform superposition of eigenstates lets phase estimation isolate one eigenstate and estimate an eigenphase s/r for factoring.Continued fractions applied to the estimate can determine r and enable extraction of a factor of N.

2. Robust Phase Estimation

The tutorial presents robust phase estimation and explains how cascaded QSVT sequences connect phase estimation to the inverse QFT. It also places Hamiltonian simulation and matrix inversion within the same polynomial-transformation framework.

  • 2. Robust Phase Estimation: Choosing sufficiently small Δ allows QSVT phase estimation to tolerate additive errors in the binary phase suffix without a high-probability incorrect measurement.The stated tolerated error magnitude is < 1/8 − 3γ/2 under the supplied condition.
  • D. Emergent Quantum Fourier Transform: Cascaded QSVT sequences use one iteration’s measurement result to control subsequent instances, with QFT arising as the simplest case.The construction generalizes the QFT through different QSVT parameters and sequence lengths.
  • D. Emergent Quantum Fourier Transform: For length-one QSVT sequences, commuting controlled-U^2^j operations with z-rotations exposes the standard inverse QFT circuit.The inverse QFT appears after sliding and regrouping gates without changing the circuit elements.
  • Function Evaluation Problems: QSVT evaluates matrix functions by implementing a polynomial P(x) that approximates the desired function f(x).Hamiltonian simulation corresponds to f(x) = e^−ixt.
  • A. Hamiltonian Simulation by QSVT: Hamiltonian simulation by QSVT has complexity linear in t, logarithmic in ϵ, and additive in those terms.The construction assumes a block encoding of H/α when ||H|| may exceed one, requiring α ≥ ||H||.

B. Matrix Inversion by QSVT

QSVT treats matrix inversion as polynomial function evaluation on a block encoding of A, approximating a scaled reciprocal while respecting QSVT’s bounded-polynomial constraint. The resulting algorithm achieves O(κ log(κ/ϵ)) complexity and can solve quantum linear systems.

  • Formulation: Matrix inversion is expressed as applying the reciprocal function to the singular values of A, yielding A−1.The construction rewrites A−1 as f(SV)(A†) with f(x) = 1/x.
  • Polynomial construction: QSVT constructs an odd polynomial that approximates a scaled reciprocal over the allowed singular-value range.The target is an ϵ/(2κ)-approximation to (1/(2κ))(1/x), bounded in magnitude by 1 so it can be implemented through QSVT.
  • Polynomial construction: The matrix inversion polynomial has odd parity, is bounded by 1 on [−1,1], and therefore can be implemented through QSVT.Its construction combines a restricted-range reciprocal approximation with a rectangular-function approximation.
  • Complexity: O(κ log(κ/ϵ)) calls to the block encoding yield matrix inversion by QSVT.This improves the stated κ and ϵ scaling over HHL’s O(κ^2 log(N)/ϵ), while the QSVT complexity has no explicit N dependence, although block-encoding construction may scale with N.
  • Applications: QSVT matrix inversion can also prepare a quantum solution to A|x⟩ = |b⟩ by applying the block encoding to |b⟩.This parallels the use of HHL for solving linear systems.
  • Caveat: QSVT’s advantage depends on access to a suitable block encoding, and QRAM-based implementations may provide only polynomial rather than exponential speedups over classical singular-value transformations.The paper notes that constructing the block encoding itself may scale with the matrix size.

Appendix A: QSP Conventions

QSP constructions are determined by a signal operator, phase-parameterized processing operations, and a measurement basis. Different conventions and bases determine which polynomial families are achievable, with some conventions equivalent and others restrictive for real polynomial approximation.

  • QSP components: A QSP construction uses a signal operator, a signal-processing operator parameterized by phases, and a signal basis for extracting the polynomial.The signal operator remains constant, while the phase sequence is chosen according to the desired output function.
  • Wx convention: The (Wx, Sz, ⟨0|·|0⟩) convention outputs a polynomial matrix element but imposes parity and additional achievability constraints.The projected output is Poly(a) = ⟨0|U⃗φ|0⟩ = P(a).
  • Wx convention: Using the measurement basis M = {|0⟩,|1⟩} restricts achievable functions to those satisfying |Poly(±1)| = 1.The paper identifies this as an immediate consequence of measuring in the same basis as the signal-processing operations.
  • Wx convention: The constraints on the (Wx, Sz, ⟨0|·|0⟩) convention are especially restrictive when approximating real functions.The paper states that none of its polynomial approximations satisfy the final two constraints in that convention.
  • Signal basis: Choosing M = {|+⟩,|−⟩} is more useful when constructing real polynomials.Changing the signal basis avoids the restrictions associated with the computational-basis measurement convention.
  • Equivalent conventions: Reflection-based and rotation-based QSP conventions can be equivalent, while the reflection operator can simplify proofs because it is Hermitian.The paper states that the two conventions are equivalent regardless of the final measurement basis.
  • Laurent formulation: The (Wz, Sx, ⟨0|·|0⟩) Laurent-polynomial convention is equivalent to the (Wx, Sz, ⟨+|·|+⟩) convention and is equally expressive.It uses a z-rotation for the signal operator and an x-rotation for signal processing.

Appendix B: Proofs about Phase Estimation by QSVT

The appendix proves the accuracy behavior of QSVT-based phase estimation under exact sign-function implementation. Exact recovery occurs when the phase has at most n bits, while longer phases receive an n-bit approximation with error at most 2^−n−1.

  • n ≥ m: When n ≥ m and the sign function is implemented exactly, QSVT phase estimation returns θ = ϕ.Appending zeros makes the phase an n-bit number without changing its value.
  • n < m: When n < m, QSVT phase estimation produces an n-bit approximation satisfying |θ − ϕ| ≤ 2^−n−1.An additional j = 0 iteration is required in the complete algorithm.
  • n ≥ m: The induction invariant is θ = 0.ϕ[j+1:] at the end of iteration j.Each iteration determines the next binary digit while retaining the remaining suffix as the current estimate.
  • n < m: The finite-precision proof tracks rounding errors through an additional carried bit and bounds the rounded suffix error by 2^(j−n−1).The induction applies to phases with more than n bits, including infinitely long binary expansions.
  • Boundary case: If the sign-function argument is exactly at the ambiguous point, either measured bit is equally accurate and the theorem’s error bound remains valid.This is analogous to rounding 0.5 either downward or upward.

2. Theorem 8

Theorem 8 analyzes phase-estimation errors caused by a finite region where the QSVT sign approximation is unreliable. With sufficiently small ∆, ambiguity is confined to the final iteration or corrected later, preserving high-probability error below 1/2^n.

  • Error bound: If an error occurs at the final iteration because of ∆, the final estimate still satisfies |θ − ϕ| < 1/2^n, assuming no later errors.The initial error can be corrected or kept within the required approximation range by subsequent iterations.
  • Setup: The sign-function approximation fails inside a finite ∆-region, producing indeterminate QSVT measurements there.The theorem studies how choosing ∆ sufficiently small mitigates this failure.
  • Theorem 8: If ∆ is sufficiently small, the signal can lie in the ∆-region only at iteration j = n − 1.At all later iterations, the relevant signal values remain outside the unreliable region and the next bit can be determined with high probability.
  • Theorem 8: A correct decision at iteration j = n − 1 ensures that subsequent iterations avoid the ∆-region and recover the remaining bits with high probability.The proof establishes this inductively over the later iterations.
  • Generalization: For a general constraint parameter γ, the induced suffix error remains below 1/8 − 3γ/2 while the phase estimate retains |ϕ − θ| < 1/2^n with high probability.The bound applies when the chosen ∆ satisfies the stated restriction.

Appendix C: Construction of the Matrix Inversion Polynomial

The matrix inversion polynomial combines an inverse-function approximation with a rectangular polynomial that controls its magnitude. The resulting QSVT polynomial approximates a scaled inverse over the allowed singular-value range while remaining bounded.

  • Inverse approximation: The construction begins by approximating 1/x outside a gap around zero using Chebyshev polynomials.The approximation has degree O(κ^2 log(κ/ϵ)) and achieves a 2ϵ approximation on the stated domain.
  • Bounding issue: The naive scaled inverse candidate is accurate outside the gap but may exceed magnitude 1 inside the gap.Its bound can scale as O(log(κ/ϵ)), so it does not automatically satisfy QSVT boundedness.
  • Bound enforcement: A rectangular polynomial is multiplied into the candidate to transition between values near 0 and 1 while staying bounded.The transition polynomial is built from step-function approximations and has even degree O(κ log(1/ϵ)).
  • Final polynomial: The final matrix inversion polynomial is an ϵ/(2κ)-approximation to (1/(2κ))(1/x) over the possible singular values and is bounded by 1.Its degree is obtained by adding the degrees of the inverse and rectangular components.
  • Example: For the illustrated parameters, the matrix inversion polynomial is a degree-77 approximation to the inverse function.Figure 19 sketches its transition behavior.

Appendix D: QSP Phase Angle Sequence Examples

The appendix provides explicit QSP phase sequences for several useful polynomial transformations. The examples cover amplification, sign and inverse functions, and illustrate their corresponding response functions.

  • Overview: The appendix presents pedagogically clear, not necessarily optimal, polynomials and QSP phase angles for quantum signal processing applications.Unless otherwise specified, phases use the (Wx, Sz, ⟨+|·|+⟩)-QSP convention, with code available in pyqsp.
  • Amplification: Oblivious amplitude amplification maps small input values close to 1 using phase sequences with error 1−δ^2.The sequence is parameterized by degree d and δ; an example uses d=10 and δ=0.5.
  • Sign function: A degree-19 polynomial with k=10 approximates the sign function and can serve as a step function for positive inputs.The corresponding response function is shown in Figure 21.
  • Inverse function: Chebyshev polynomials provide the inverse-function approximation used for Moore–Penrose pseudoinverses through QSVT.The example uses κ=3 and ϵ=0.3, with its response function shown in Figure 22.

4. Cosine and sine functions for Hamiltonian simulation

The appendix demonstrates QSP polynomial examples for Hamiltonian simulation and several related transformations. These examples approximate trigonometric, threshold, phase-estimation, filtering, Gibbs, and ReLU functions under explicit parameter choices and conventions.

  • Hamiltonian simulation: Hamiltonian simulation approximates e^(-iat) by separately approximating cos(at) and sin(at) with Jacobi–Anger polynomials.The degree is chosen so the error is bounded by ϵ for a∈[−1,1].
  • Threshold function: A polynomial approximation to step(a−1/2) distinguishes singular values above or below 1/2.With k=10 and degree d=18, increasing k and degree makes the threshold sharper.
  • Phase estimation: Degree-18 phase-estimation polynomials are provided in two QSP conventions, with the second clarifying a reduction to the quantum Fourier transform.The (Wx, Sz, ⟨0|·|0⟩) example has a small non-zero imaginary response because the real approximation is not compatible with Theorem 9.
  • Eigenstate filtering: The eigenstate filtering function is an optimal degree-2k polynomial for filtering unwanted information from eigenstates separated by a gap.Changing Δλ relocates the threshold in the illustrated response function.
  • Gibbs distribution: The Gibbs-distribution example approximates e^(-βa) using an even polynomial approximation to e^(-β|a|).For β=3.5, a degree-20 approximation deviates near a=0 because the symmetrized target is non-analytic there.
  • ReLU: The ReLU example uses an even softplus-based approximation whose threshold offset and steepness are controlled by δ and Δ.The illustrated construction uses δ=0.6, Δ=15, and degree 20.
Loading 2105.02859v5…