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/ε 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-κ lower bound.
Formalize the input, access, conditioning and output caveats, and quantify readout costs.
Trace the improvements to O(κpolylog(κ/ε)) and O(κlog(1/ε)), including the polynomial approximation of 1/x.
The problem, precisely
A non-Hermitian A is handled by the dilation (0A†A0), whose eigenvalues are ±σi(A); the condition number is unchanged and the cost is one extra qubit. Notice what the definition leaves out: reading x.
Attach a clock to a T-gate circuit UT⋯U1: run it, idle for T ticks, run it backwards. Then U3T=I, and U is sparse.
A=I−e−1/TU,A−1=k≥0∑e−k/TUk,κ=O(T)
The eigenvalues 1−e−1/Tω, with ω3T=1, have moduli between 1−e−1/T≈1/T and 2. (Dilate to make it Hermitian.)
A−1∣0⟩clock∣ψ⟩=k≥0∑e−k/T∣kmod3T⟩⊗Vk−1⋯V0∣ψ⟩
Clock values in the idle block [T,2T) carry the circuit's output state, and they carry a constant fraction of the norm. Estimating ⟨x∣M∣x⟩ with M = "clock in the idle block and output qubit 1" decides any BQP language.
κ1−δ-time solver⇒T-gate circuits simulated in time T1−δ⇒BQP=PSPACE
A solver sublinear in κ would fast-forward circuits; applied recursively, it would compress exponentially long polynomial-space computations into polynomial time. So linear dependence on κ is necessary. ■
Check your understanding
Take κ=Θ(N) with s and ε constant. How does HHL's runtime compare with conjugate gradient's O(Nsκlog(1/ε))?
Still an exponential speedup, since HHL is O(logN)
HHL is slower than conjugate gradient
Only a polynomial speedup: O(N) versus O(N5/4)
They are identical
Show the answer
C. Only a polynomial speedup: O(N) versus O(N5/4)
HHL costs O(κ2)=O(N) here, while conjugate gradient costs O(N⋅N1/4). Even the optimal O(κ) solvers give only O(N): polynomial. The exponential speedup requires κ=polylogN.
HHL step by step, with its error budget
DerivationWhere κ²/ε comes from
QPE with total evolution time t0:λ~−λ≲t01
Phase estimation resolves eigenvalues to about the inverse of the evolution time.
With the sparse Hamiltonian simulation available in 2009. One factor of κ comes from precision, the other from postselection.
The fine print, formalized
Caveat
Requirement for an exponential speedup
What failure costs
Input
Ub with polylogN gates: a formula (e.g. Grover–Rudolph for efficiently integrable distributions) or a QRAM
generic state preparation costs Θ(N)
Matrix access
s-sparse with efficiently computable entries, or an efficient block encoding with small normalization
dense, unstructured A makes each query costly
Conditioning
κ=polylogN
e.g. a Laplacian on a grid of N points in d dimensions has κ=Θ(N2/d)
Output
only ∣x⟩; estimating ⟨x∣M∣x⟩ to δ costs O(1/δ) solver calls with amplitude estimation, O(1/δ2) by sampling
full readout costs Ω(N) runs
Classical competitor
compare against classical algorithms given equivalent access
low-rank problems are dequantized
Aaronson's four caveats (2015) plus the comparison caveat. The κ row is often decisive for discretized differential equations.
Predict before you look
You want ⟨x∣M∣x⟩ for an observable with eigenvalues ±1 whose expectation is near 0, to additive error 0.001, by naive repeated measurement. About how many runs of the full solver (in millions)?
Show the answer
1 million
Each run gives ±1 with variance about 1, so the standard error after S runs is 1/S, and S=106. Amplitude estimation reduces this to about π/δ≈3000 coherent calls, but every call runs the whole solver, including its κ-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 κ grows with the grid and the answer must be extracted, with larger gains possible only in high dimension.
LCU of Fourier or Chebyshev expansions of 1/x, plus VTAA
Gilyén, Su, Low & Wiebe (2019)
degree-O(κlog(κ/ε)) polynomial per inversion
quantum singular value transformation (QSVT)
Costa et al. (2022)
O(κlog(1/ε))
discrete adiabatic theorem plus eigenstate filtering
Query complexities in κ and ε (each query also costs the access oracles). The last is linear in κ, as the lower bound requires, and logarithmic in 1/ε; its authors describe the scaling as optimal.
DerivationA polynomial for 1/x (Childs–Kothari–Somma)
fb(x)=x1−(1−x2)b
An odd polynomial of degree 2b−1: the numerator vanishes to second order at x=0.
fb(x)−x1=∣x∣(1−x2)b≤κe−b/κ2for κ1≤∣x∣≤1
Using (1−x2)b≤(1−1/κ2)b≤e−b/κ2.
b=⌈κ2ln(κ/ε)⌉⇒fb(x)−x1≤ε on the domain
Degree O(κ2log(κ/ε)) suffices, which is still quadratic in κ.
Expand in Chebyshev polynomials and truncate. Like xb, the function is ε-close to a polynomial of degree about b (up to logarithms): linear in κ.
LCU or QSVT:O(κlog(κ/ε))queries per application of ≈A−1/κ
Implementing a degree-d polynomial of a block encoding costs O(d) queries. The output amplitude is only ≳1/κ, and VTAA or adiabatic methods recover it without paying another full factor of κ.
Key takeaways
QLSP outputs a state∝A−1∣b⟩ given sparse (or block-encoded) access to a well-conditioned A and a preparation unitary for ∣b⟩.
HHL runs in O(log(N)s2κ2/ε): one κ from eigenvalue precision near 1/κ, one from postselection.
QLSP is BQP-complete (clock construction), so it cannot be dequantized in general, and sublinear-in-κ algorithms would imply BQP=PSPACE.
The speedup survives only with cheap input, sparse access, κ=polylogN and few-number output; discretized PDEs often fail the κ test in low dimension.
Polynomial approximation of 1/x (CKS, QSVT) and adiabatic methods brought the cost to O(κlog(1/ε)).
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Question 1
Doubling κ, with everything else fixed, multiplies the runtime bounds of HHL (2009) and of Childs–Kothari–Somma (2017) by about…
2 and 4
2 and 2
4 and about 2 (up to logarithmic factors)
4 and 4
Show the answer
C. 4 and about 2 (up to logarithmic factors)
HHL scales as κ2 (precision and postselection each contribute a factor), while CKS is linear in κ up to polylogarithmic factors.
Question 2
Using an exact QLSP solver coherently, how many calls does amplitude estimation need to estimate ⟨x∣M∣x⟩ (with ∥M∥≤1) to additive error δ?
O(1/δ)
O(1/δ2)
O(log(1/δ))
O(N)
Show the answer
A.O(1/δ)
Amplitude estimation is Heisenberg-limited: precision δ needs O(1/δ) coherent applications, a quadratic improvement over sampling.
Question 3
HHL proved that a QLSP algorithm running in time κ1−δpolylogN for some δ>0 would imply…
P=NP
BPP=BQP
Nothing, since faster algorithms are already known
BQP=PSPACE
Show the answer
D.BQP=PSPACE
Such a solver would fast-forward the clock construction, simulating T-gate circuits in time T1−δ; 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 A without changing the condition number?
Replace A by A+A†
Use the dilation (0A†A0), whose eigenvalues are ±σi(A)
Replace A by A†A
It cannot be done; HHL is limited to Hermitian matrices
Show the answer
B. Use the dilation (0A†A0), whose eigenvalues are ±σi(A)
The dilation is Hermitian, its spectrum is {±σi(A)}, so κ is unchanged, and solving with right-hand side (b,0) yields (0,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).