Source-linked AI summary
Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
Andrew M. Childs, Robin Kothari, Rolando D. Somma
TL;DR
The HHL algorithm’s phase-estimation step limits precision dependence to poly(1/ε). This work directly applies matrix inverses using Fourier or Chebyshev decompositions, achieving poly(log N, log(1/ε), d, 1/κ) resources while retaining essentially the same dependence on other parameters.
Problem
HHL’s use of phase estimation requires Ω(1/ε) unitary applications for eigenvalue precision ε, limiting the algorithm’s precision dependence.
Method
The paper bypasses phase estimation by implementing A−1 directly through Fourier-series or Chebyshev-polynomial decompositions and linear combinations of unitaries.
Results
poly(log N, log(1/ε), d, 1/κ) resources exponentially improve precision dependence under the same assumptions as HHL.
Takeaways & Limitations
The Fourier approach is more generally applicable because it uses Hamiltonian simulation as a black box, and the algorithm has already been used in quantum finite-element methods.
Takeaways & Limitations
The problem assumes a Hermitian, normalized, d-sparse matrix with known condition number κ; bounds can improve to κ′ only when b lies in a lower-condition-number invariant subspace.
Abstract
from arXiv · showhide
Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x}=\vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time $\mathrm{poly}(\log N, 1/ε)$, where $ε$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/ε)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $ε$ is prohibitive.
1 Introduction
The paper improves the quantum linear systems algorithm’s precision dependence from polynomial in 1/ε to polynomial in log(1/ε), while retaining essentially the same dependence on other parameters. It achieves this by directly implementing A^-1 through Fourier or Chebyshev expansions, avoiding phase estimation’s prohibitive precision cost.
- Problem: The QLSP prepares a quantum state proportional to the solution of A x = b, rather than solving the system with a classical output.For sparse, well-conditioned A, HHL uses resources polynomial in log N, 1/ε, d, and 1/κ.
- Motivation: Phase estimation limits HHL’s precision scaling because estimating eigenvalues to precision ε requires Ω(1/ε) unitary uses.Replacing only HHL’s Hamiltonian-simulation subroutine therefore leaves polynomial dependence on 1/ε.
- Approach: The paper directly applies A^-1 using Fourier or Chebyshev expansions, circumventing the phase-estimation bottleneck.The framework implements operators represented as linear combinations of easy-to-implement unitaries and can extend to other functions of A.
- Results: The Chebyshev approach uses O(dκ^2 log^2(dκ/ε)) queries to P_A and O(κ log(dκ/ε)) uses of P_B.Its gate complexity is O(dκ^2 log^2(dκ/ε)(log N + log^2.5(dκ/ε))).
- Results: The algorithms are incomparable: Fourier is more general and has slightly better d-dependence, whereas Chebyshev has better κ- and ε-dependence but requires sparse Hamiltonians.A later refinement achieves nearly linear κ-scaling together with logarithmic ε-dependence.
2 Implementing a linear combination of unitaries
The paper implements non-unitary operators by expressing them as linear combinations of unitary or unitary-block operators, then uses postselection and amplitude amplification to prepare the normalized output state.
- Framework: The framework applies a linear combination of implementable operators to an input state using controlled unitaries and an ancilla preparation operator.The construction supports operators that are unitary or appear as blocks of larger unitaries.
- Postselection: Measuring the ancilla after applying the constructed operation yields a state proportional to M|ψ⟩ upon the all-zero outcome.The success probability is (∥M|ψ⟩∥/α)^2.
- Amplitude amplification: Amplitude amplification raises the preparation success probability using reflections about the input state.When the input state |b⟩ can be prepared, the procedure uses O(α/∥M|b⟩∥) applications in expectation.
- Complexity: The query cost of the multiplexed controlled unitary equals the maximum query cost among its component unitaries.Gate complexity can be larger in general, but behaves well when the components are powers of one unitary.
- Application to QLSP: The QLSP application approximates A^-1 with such an operator combination and transfers operator approximation error to normalized-state error.If C and D differ by at most ε under the stated assumptions, the resulting states differ by at most 4ε.
3 Fourier approach
The Fourier approach approximates A^-1 using a finite linear combination of Hamiltonian evolutions e^-iAt, obtained by taming, transforming, truncating, and discretizing an integral representation of 1/x.
- Fourier representation: The approach represents 1/x on Dκ=[-1,-1/κ]∪[1/κ,1] as a linear combination of unitaries e^-ixt.The corresponding matrix operators are Hamiltonian evolutions e^-iAt.
- Function taming: The singularity at zero is controlled by multiplying 1/x by a function that is close to one on Dκ and small near the origin.This produces a bounded function suitable for Fourier analysis.
- Discretization: The integral representation is converted into an explicit finite sum by truncating the integration range and discretizing the variables.The discretization can be made arbitrarily accurate without changing query complexity because that complexity is independent of the number of terms.
- Approximation: The Fourier approximation achieves ε accuracy on Dκ with evolution times O(κ log(κ/ε)).The truncation parameters are chosen so the tail error is at most ε.
- Complexity: The resulting sparse-Hamiltonian gate complexity is O(dκ log^2(κ/ε′)(log N+log^2.5(κ/ε′))).The cost combines Hamiltonian simulation with the linear-combination implementation and amplitude amplification framework.
4 Chebyshev approach
The Chebyshev approach implements A^-1 through quantum-walk operators whose powers encode Chebyshev polynomials, yielding an approximation specialized to sparse Hamiltonians.
- Method: The method approximates 1/x by a linear combination of Chebyshev polynomials T_n(x), implemented through a quantum walk.The walk is designed for a d-sparse Hamiltonian and uses T_n(A/d) as building blocks.
- Approximation: The Chebyshev approximation is 2ε-close to 1/x on Dκ for b=κ^2 log(κ/ε).The construction first bounds the function near zero and then expands the resulting polynomial in the Chebyshev basis.
- Quantum walk: The quantum walk operator acts on eigenvectors through a block structure whose powers generate Chebyshev-polynomial expressions.For eigenvalues of magnitude one, the walk acts directly by multiplication by the eigenvalue.
- Query implementation: Implementing the walk-based operation corresponding to a degree-n polynomial requires O(n) oracle queries.The walk and its state-preparation isometry each use O(1) oracle queries.
- Complexity: The Chebyshev approach has total query complexity O(dκ^2 log^2(dκ/ε)) and uses O(κ log(κd/ε)) applications of P_B.The highest Chebyshev order determines the operation cost, while amplitude amplification contributes the additional factor.
- Gate complexity: The gate complexity exceeds the query complexity by O(log N+log^2.5(κd/ε)).This factor accounts for implementing the underlying walk-based operations.
5 Improved dependence on condition number
The paper reduces the condition-number dependence of its quantum linear-systems algorithms from quadratic to nearly linear using variable-time amplitude amplification and low-precision phase estimation. The construction applies approximations of A^-1 across eigenvalue ranges and achieves the desired output state with controlled error and improved stopping-time complexity.
- Condition-number improvement: Nearly linear condition-number dependence replaces the previous quadratic dependence in both algorithms.The improvement is established using variable-time amplitude amplification, low-precision phase estimation, and either the Fourier or Chebyshev approach.
- Condition-number improvement: Quadratic κ-dependence arises from both implementing A^-1 and amplifying its success probability.The implementation cost is close to linear in κ, while the amplification factor α also depends approximately linearly on κ.
- Condition-number improvement: If |b⟩ occupies a subspace with condition number κ′, the upper bounds can replace κ with κ′.When the relevant singular values are close to 1, κ′ = O(1); when they are close to 1/κ, the expected complexity becomes O(α/κ) = poly(log(dκ/ε)).
- Algorithmic tools: The method combines variable-time amplitude amplification with gapped phase estimation and eigenvalue-range-specific approximations of A^-1.Gapped phase estimation distinguishes eigenphases near zero from those separated by a gap, while the approximations support the variable stopping-time construction.
- Algorithmic tools: Variable-time amplitude amplification exploits algorithms whose branches have different stopping times to reduce amplification cost.The framework represents potential stopping times with clock qubits and prevents later operations on branches that have already halted.
- Complexity: The variable-time amplification theorem produces the successful state with high probability and a success flag, with gate efficiency inherited from the underlying algorithm.Its query complexity depends on the root-mean-square average stopping time rather than only the maximum stopping time.
- Correctness: The final procedure applies variable-time amplification, then reverses the preparation unitary to obtain A^-1|b⟩ up to error O(ε).The amplified state is normalized with constant probability, and applying (A′)† erases ancillary states.
- Complexity: The stopping-time construction has tj = eO(d2^j) and tm = eO(dκ), while eigenvalue λk determines a stopping scale with average squared time eO(d/λk).These bounds support the improved complexity analysis through variable-time amplification.