Algorithm Zoo · Linear algebra
HHL Algorithm
Also known as: Quantum linear systems
First described: Harrow, Hassidim, Lloyd, 2009
The problem
Given a sparse, well-conditioned matrix A and vector b, output a state |x⟩ proportional to A^{-1}|b⟩.
Solves linear systems Ax = b in time poly(log N, κ, 1/ε) where N is the dimension, κ is the condition number, ε is precision. Crucially, the output is a quantum state — not the vector — and extracting useful classical information requires measurement.
Best classical
Õ(N · √κ) for Krylov-based sparse solvers (e.g. conjugate gradient)
Quantum complexity
Õ(log(N) · κ · s · 1/ε) (sparsity s, condition number κ)
Our verdict
Asymptotically exponential, practically encumbered. The four caveats (sparse A, well-conditioned A, easy state preparation, easy expectation-value readout) rarely all apply to real engineering problems. Treat as a primitive for QML pipelines, not as a 'solve any linear system' button.
When to use it
- When you only need an expectation value ⟨x|M|x⟩ that can be extracted with few measurements.
- When the matrix and right-hand side admit fast block encodings.
- Inside larger algorithms (QSVD, gradient descent in quantum data spaces).
When not to use it
- When you need the full classical vector x — readout undoes the exponential speedup.
- When κ or s is poly(N) — speedup evaporates.
- When data loading (RAM-like state preparation) is the bottleneck.
Classical baseline
Conjugate gradient and other Krylov methods are extremely strong on real problems. Aaronson's 'Read the Fine Print' (2015) lists four caveats that HHL must clear simultaneously; few real problems clear all four.
Hardware cost
Per Aaronson: requires QRAM-like state preparation (not yet engineered), exponentially precise condition-number estimation, and well-conditioned A. Each caveat adds qubit and depth overhead. No demonstration has solved a problem a classical CG step couldn't.
Key papers
- Quantum algorithm for solving linear systems of equations ↗
Harrow, Hassidim, Lloyd · 2009 · Phys. Rev. Lett.
- Quantum machine learning: a classical perspective (commentary) ↗
Aaronson · 2015 · Nature Physics
Deep-dive tutorials
Last verified: 2026-05-24