Simple Algorithm
Quantum Computing · Rydberg State · 30 min

HHL & the Fine Print of Quantum Linear Algebra

Exponential speedups and the caveats that come with them.

HHL is the most-cited exponential speedup after Shor's, and one of the most misunderstood. Stated precisely, it solves a BQP-complete problem, so no classical algorithm should match it. Stated loosely, it promises to accelerate all of numerical linear algebra, which it does not. This lesson lives in the gap between the two statements.

What you’ll learn

  • Define the quantum linear systems problem (QLSP), including the access model and the output.
  • Derive HHL's κ2/ε\kappa^2/\varepsilon scaling from phase-estimation precision, postselection and Hamiltonian simulation.
  • Prove (sketch) that QLSP is BQP-hard via a clock construction, and state the linear-in-κ\kappa lower bound.
  • Formalize the input, access, conditioning and output caveats, and quantify readout costs.
  • Trace the improvements to O(κ poly⁡log⁡(κ/ε))\order{\kappa\,\poly\log(\kappa/\varepsilon)} and O(κlog⁡(1/ε))\order{\kappa\log(1/\varepsilon)}, including the polynomial approximation of 1/x1/x.

The problem, precisely

A non-Hermitian AA is handled by the dilation (0AA†0)\left(\begin{smallmatrix}0&A\\A^\dagger&0\end{smallmatrix}\right), whose eigenvalues are ±σi(A)\pm\sigma_i(A); the condition number is unchanged and the cost is one extra qubit. Notice what the definition leaves out: reading x\mathbf x.

DerivationWhy QLSP is BQP-hard (sketch)
  1. U=∑t=03T−1∣t+1 mod 3T⟩ ⁣⟨t∣⊗Vt,Vt={Ut+10≤t<TIT≤t<2TU3T−t†2T≤t<3TU=\sum_{t=0}^{3T-1}\ketbra{t+1\bmod 3T}{t}\otimes V_t,\qquad V_t=\begin{cases}U_{t+1}&0\le t<T\\\id&T\le t<2T\\U_{3T-t}^\dagger&2T\le t<3T\end{cases}

    Attach a clock to a TT-gate circuit UT⋯U1U_T\cdots U_1: run it, idle for TT ticks, run it backwards. Then U3T=IU^{3T}=\id, and UU is sparse.

  2. A=I−e−1/TU,A−1=∑k≥0e−k/TUk,κ=O(T)A=\id-e^{-1/T}U,\qquad A^{-1}=\sum_{k\ge0}e^{-k/T}U^k,\qquad\kappa=\order{T}

    The eigenvalues 1−e−1/Tω1-e^{-1/T}\omega, with ω3T=1\omega^{3T}=1, have moduli between 1−e−1/T≈1/T1-e^{-1/T}\approx1/T and 22. (Dilate to make it Hermitian.)

  3. A−1∣0⟩clock∣ψ⟩=∑k≥0e−k/T∣k mod 3T⟩⊗Vk−1⋯V0∣ψ⟩A^{-1}\ket{0}_{\text{clock}}\ket{\psi}=\sum_{k\ge0}e^{-k/T}\ket{k\bmod3T}\otimes V_{k-1}\cdots V_0\ket{\psi}

    Clock values in the idle block [T,2T)[T,2T) carry the circuit's output state, and they carry a constant fraction of the norm. Estimating ⟨x|M|x⟩\mel{\mathbf x}{M}{\mathbf x} with MM = "clock in the idle block and output qubit 1" decides any BQP language.

  4. κ1−δ-time solver ⇒ T-gate circuits simulated in time T1−δ ⇒ BQP=PSPACE\kappa^{1-\delta}\text{-time solver}\ \Rightarrow\ T\text{-gate circuits simulated in time }T^{1-\delta}\ \Rightarrow\ \mathsf{BQP}=\mathsf{PSPACE}

    A solver sublinear in κ\kappa would fast-forward circuits; applied recursively, it would compress exponentially long polynomial-space computations into polynomial time. So linear dependence on κ\kappa is necessary. ■\blacksquare

Check your understanding

Take κ=Θ(N)\kappa=\Theta(\sqrt N) with ss and ε\varepsilon constant. How does HHL's runtime compare with conjugate gradient's O(Nsκlog⁡(1/ε))\order{Ns\sqrt\kappa\log(1/\varepsilon)}?

  1. Still an exponential speedup, since HHL is O(log⁡N)\order{\log N}
  2. HHL is slower than conjugate gradient
  3. Only a polynomial speedup: O~(N)\widetilde{\mathcal O}(N) versus O(N5/4)\order{N^{5/4}}
  4. They are identical
Show the answer

C. Only a polynomial speedup: O~(N)\widetilde{\mathcal O}(N) versus O(N5/4)\order{N^{5/4}}

HHL costs O~(κ2)=O~(N)\widetilde{\mathcal O}(\kappa^2)=\widetilde{\mathcal O}(N) here, while conjugate gradient costs O(N⋅N1/4)\order{N\cdot N^{1/4}}. Even the optimal O(κ)\order{\kappa} solvers give only O~(N)\widetilde{\mathcal O}(\sqrt N): polynomial. The exponential speedup requires κ=poly⁡log⁡N\kappa=\poly\log N.

HHL step by step, with its error budget

DerivationWhere κ²/ε comes from
  1. QPE with total evolution time t0:∣λ~−λ∣≲1t0\text{QPE with total evolution time }t_0:\qquad\abs{\tilde\lambda-\lambda}\lesssim\frac{1}{t_0}

    Phase estimation resolves eigenvalues to about the inverse of the evolution time.

  2. ∣1λ~−1λ∣≈∣λ~−λ∣λ2 ⇒ relative error ∣λ~−λ∣∣λ∣≤κt0\Big|\frac{1}{\tilde\lambda}-\frac1\lambda\Big|\approx\frac{\abs{\tilde\lambda-\lambda}}{\lambda^2}\ \Rightarrow\ \text{relative error}\ \frac{\abs{\tilde\lambda-\lambda}}{\abs\lambda}\le\frac{\kappa}{t_0}

    Inversion amplifies errors on small eigenvalues; with ∣λ∣≥1/κ\abs\lambda\ge1/\kappa the relative error is at most κ/t0\kappa/t_0.

  3. t0=O(κ/ε)t_0=\order{\kappa/\varepsilon}

    For relative precision ε\varepsilon in ∣x⟩\ket{\mathbf x}.

  4. psucc=∑j∣βj∣2C2λj2 ≥ 1κ2(C=1/κ) ⇒ O(κ) rounds of amplitude amplificationp_{\text{succ}}=\sum_j\abs{\beta_j}^2\frac{C^2}{\lambda_j^2}\ \ge\ \frac{1}{\kappa^2}\quad(C=1/\kappa)\ \Rightarrow\ \order{\kappa}\ \text{rounds of amplitude amplification}

    Postselection is unlikely when ∣b⟩\ket{\mathbf b} sits on large eigenvalues.

  5. O~(s2t0log⁡N)⏟simulate eiAt0×O(κ)⏟amplification=O~(log⁡(N) s2κ2ε)\underbrace{\widetilde{\mathcal O}\big(s^2t_0\log N\big)}_{\text{simulate }e^{iAt_0}}\times\underbrace{\order{\kappa}}_{\text{amplification}}=\widetilde{\mathcal O}\Big(\log(N)\,\frac{s^2\kappa^2}{\varepsilon}\Big)

    With the sparse Hamiltonian simulation available in 2009. One factor of κ\kappa comes from precision, the other from postselection.

The fine print, formalized

CaveatRequirement for an exponential speedupWhat failure costs
InputUbU_b with poly⁡log⁡N\poly\log N gates: a formula (e.g. Grover–Rudolph for efficiently integrable distributions) or a QRAMgeneric state preparation costs Θ(N)\Theta(N)
Matrix accessss-sparse with efficiently computable entries, or an efficient block encoding with small normalizationdense, unstructured AA makes each query costly
Conditioningκ=poly⁡log⁡N\kappa=\poly\log Ne.g. a Laplacian on a grid of NN points in dd dimensions has κ=Θ(N2/d)\kappa=\Theta(N^{2/d})
Outputonly ∣x⟩\ket{\mathbf x}; estimating ⟨x|M|x⟩\mel{\mathbf x}{M}{\mathbf x} to δ\delta costs O(1/δ)\order{1/\delta} solver calls with amplitude estimation, O(1/δ2)\order{1/\delta^2} by samplingfull readout costs Ω(N)\Omega(N) runs
Classical competitorcompare against classical algorithms given equivalent accesslow-rank problems are dequantized
Aaronson's four caveats (2015) plus the comparison caveat. The κ\kappa row is often decisive for discretized differential equations.
Predict before you look

You want ⟨x|M|x⟩\mel{\mathbf x}{M}{\mathbf x} for an observable with eigenvalues ±1\pm1 whose expectation is near 0, to additive error 0.0010.001, by naive repeated measurement. About how many runs of the full solver (in millions)?

Show the answer

1 million

Each run gives ±1\pm1 with variance about 1, so the standard error after SS runs is 1/S1/\sqrt S, and S=106S=10^6. Amplitude estimation reduces this to about π/δ≈3000\pi/\delta\approx3000 coherent calls, but every call runs the whole solver, including its κ\kappa-dependent cost.

Applications that satisfy every line exist in principle (BQP-completeness guarantees hard instances), and candidates include certain discretized differential equations and scattering problems. Careful end-to-end analyses are sobering: for the finite element method, Montanaro and Pallister (2016) found at most a polynomial speedup in fixed spatial dimension, because κ\kappa grows with the grid and the answer must be extracted, with larger gains possible only in high dimension.

Beyond HHL: optimal scaling

AlgorithmQuery complexityKey idea
HHL (2009)O~(κ2/ε)\widetilde{\mathcal O}(\kappa^2/\varepsilon)phase estimation, controlled rotation, amplitude amplification
Ambainis (2012)O(κlog⁡3κ/ε3)\order{\kappa\log^3\kappa/\varepsilon^3}variable-time amplitude amplification (VTAA)
Childs, Kothari & Somma (2017)O(κ poly⁡log⁡(κ/ε))\order{\kappa\,\poly\log(\kappa/\varepsilon)}LCU of Fourier or Chebyshev expansions of 1/x1/x, plus VTAA
Gilyén, Su, Low & Wiebe (2019)degree-O(κlog⁡(κ/ε))\order{\kappa\log(\kappa/\varepsilon)} polynomial per inversionquantum singular value transformation (QSVT)
Costa et al. (2022)O(κlog⁡(1/ε))\order{\kappa\log(1/\varepsilon)}discrete adiabatic theorem plus eigenstate filtering
Query complexities in κ\kappa and ε\varepsilon (each query also costs the access oracles). The last is linear in κ\kappa, as the lower bound requires, and logarithmic in 1/ε1/\varepsilon; its authors describe the scaling as optimal.
DerivationA polynomial for 1/x (Childs–Kothari–Somma)
  1. fb(x)=1−(1−x2)bxf_b(x)=\frac{1-(1-x^2)^b}{x}

    An odd polynomial of degree 2b−12b-1: the numerator vanishes to second order at x=0x=0.

  2. ∣fb(x)−1x∣=(1−x2)b∣x∣≤κ e−b/κ2for 1κ≤∣x∣≤1\Big|f_b(x)-\frac1x\Big|=\frac{(1-x^2)^b}{\abs x}\le\kappa\,e^{-b/\kappa^2}\qquad\text{for }\tfrac1\kappa\le\abs x\le1

    Using (1−x2)b≤(1−1/κ2)b≤e−b/κ2(1-x^2)^b\le(1-1/\kappa^2)^b\le e^{-b/\kappa^2}.

  3. b=⌈κ2ln⁡(κ/ε)⌉ ⇒ ∣fb(x)−1x∣≤ε  on the domainb=\big\lceil\kappa^2\ln(\kappa/\varepsilon)\big\rceil\ \Rightarrow\ \Big|f_b(x)-\frac1x\Big|\le\varepsilon\ \text{ on the domain}

    Degree O(κ2log⁡(κ/ε))\order{\kappa^2\log(\kappa/\varepsilon)} suffices, which is still quadratic in κ\kappa.

  4. fb≈∑j=0j0cj T2j+1(x),j0=O(blog⁡(b/ε))=O(κlog⁡(κ/ε))f_b\approx\sum_{j=0}^{j_0}c_j\,T_{2j+1}(x),\qquad j_0=\order{\sqrt{b\log(b/\varepsilon)}}=\order{\kappa\log(\kappa/\varepsilon)}

    Expand in Chebyshev polynomials and truncate. Like xbx^b, the function is ε\varepsilon-close to a polynomial of degree about b\sqrt b (up to logarithms): linear in κ\kappa.

  5. LCU or QSVT:O(κlog⁡(κ/ε)) queries per application of ≈A−1/κ\text{LCU or QSVT:}\quad\order{\kappa\log(\kappa/\varepsilon)}\ \text{queries per application of }\approx A^{-1}/\kappa

    Implementing a degree-dd polynomial of a block encoding costs O(d)\order d queries. The output amplitude is only ≳1/κ\gtrsim1/\kappa, and VTAA or adiabatic methods recover it without paying another full factor of κ\kappa.

Key takeaways

  • QLSP outputs a state ∝A−1∣b⟩\propto A^{-1}\ket{\mathbf b} given sparse (or block-encoded) access to a well-conditioned AA and a preparation unitary for ∣b⟩\ket{\mathbf b}.
  • HHL runs in O~(log⁡(N)s2κ2/ε)\widetilde{\mathcal O}(\log(N)s^2\kappa^2/\varepsilon): one κ\kappa from eigenvalue precision near 1/κ1/\kappa, one from postselection.
  • QLSP is BQP-complete (clock construction), so it cannot be dequantized in general, and sublinear-in-κ\kappa algorithms would imply BQP=PSPACE\mathsf{BQP}=\mathsf{PSPACE}.
  • The speedup survives only with cheap input, sparse access, κ=poly⁡log⁡N\kappa=\poly\log N and few-number output; discretized PDEs often fail the κ\kappa test in low dimension.
  • Polynomial approximation of 1/x1/x (CKS, QSVT) and adiabatic methods brought the cost to O(κlog⁡(1/ε))\order{\kappa\log(1/\varepsilon)}.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Doubling κ\kappa, with everything else fixed, multiplies the runtime bounds of HHL (2009) and of Childs–Kothari–Somma (2017) by about…

  1. 2 and 4
  2. 2 and 2
  3. 4 and about 2 (up to logarithmic factors)
  4. 4 and 4
Show the answer

C. 4 and about 2 (up to logarithmic factors)

HHL scales as κ2\kappa^2 (precision and postselection each contribute a factor), while CKS is linear in κ\kappa up to polylogarithmic factors.

Question 2

Using an exact QLSP solver coherently, how many calls does amplitude estimation need to estimate ⟨x|M|x⟩\mel{\mathbf x}{M}{\mathbf x} (with ∥M∥≤1\norm M\le1) to additive error δ\delta?

  1. O(1/δ)\order{1/\delta}
  2. O(1/δ2)\order{1/\delta^2}
  3. O(log⁡(1/δ))\order{\log(1/\delta)}
  4. O(N)\order{N}
Show the answer

A. O(1/δ)\order{1/\delta}

Amplitude estimation is Heisenberg-limited: precision δ\delta needs O(1/δ)\order{1/\delta} coherent applications, a quadratic improvement over sampling.

Question 3

HHL proved that a QLSP algorithm running in time κ1−δpoly⁡log⁡N\kappa^{1-\delta}\poly\log N for some δ>0\delta>0 would imply…

  1. P=NP\mathsf P=\mathsf{NP}
  2. BPP=BQP\mathsf{BPP}=\mathsf{BQP}
  3. Nothing, since faster algorithms are already known
  4. BQP=PSPACE\mathsf{BQP}=\mathsf{PSPACE}
Show the answer

D. BQP=PSPACE\mathsf{BQP}=\mathsf{PSPACE}

Such a solver would fast-forward the clock construction, simulating TT-gate circuits in time T1−δT^{1-\delta}; applied recursively this would solve PSPACE problems in quantum polynomial time.

Question 4

HHL needs a Hermitian matrix. How do you handle a non-Hermitian AA without changing the condition number?

  1. Replace AA by A+A†A+A^\dagger
  2. Use the dilation (0AA†0)\left(\begin{smallmatrix}0&A\\A^\dagger&0\end{smallmatrix}\right), whose eigenvalues are ±σi(A)\pm\sigma_i(A)
  3. Replace AA by A†AA^\dagger A
  4. It cannot be done; HHL is limited to Hermitian matrices
Show the answer

B. Use the dilation (0AA†0)\left(\begin{smallmatrix}0&A\\A^\dagger&0\end{smallmatrix}\right), whose eigenvalues are ±σi(A)\pm\sigma_i(A)

The dilation is Hermitian, its spectrum is {±σi(A)}\{\pm\sigma_i(A)\}, so κ\kappa is unchanged, and solving with right-hand side (b,0)(\mathbf b,0) yields (0,x)(0,\mathbf x). One extra qubit suffices.

Further reading

  • A. W. Harrow, A. Hassidim & S. Lloyd, "Quantum algorithm for linear systems of equations", Phys. Rev. Lett. 103, 150502 (2009).
  • S. Aaronson, "Read the fine print", Nature Physics 11, 291 (2015).
  • A. M. Childs, R. Kothari & R. D. Somma, "Quantum algorithm for systems of linear equations with exponentially improved dependence on precision", SIAM J. Comput. 46, 1920 (2017).
  • A. Gilyén, Y. Su, G. H. Low & N. Wiebe, "Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics", Proc. STOC (2019).
  • P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush & D. W. Berry, "Optimal scaling quantum linear-systems solver via discrete adiabatic theorem", PRX Quantum 3, 040303 (2022).