120
Part Three · B · Algorithms

HHL and quantum linear algebra, with input/output caveats

Solving a system of linear equations, Ax=bA\mathbf x = \mathbf b, underlies almost all of scientific computing, from finite-element models of bones to the reconstruction of CT images. In 2009 Aram Harrow, Avinatan Hassidim and Seth Lloyd gave a quantum algorithm whose cost grows only logarithmically with the number of unknowns: an exponential speedup. The algorithm is correct. But the speedup comes with conditions so restrictive that Scott Aaronson wrote an article called “Read the fine print.” This chapter reads it.

On the plate: a checklist. Describe your problem, and see whether an exponential advantage survives.

How HHL works

Load b\mathbf b as a quantum state ∣b⟩|b\rangle. Run phase estimation (Chapter 113) with eiAte^{iAt} to write each eigenvalue λj\lambda_j of AA into a register. Rotate an ancilla by an angle proportional to 1/λj1/\lambda_j, uncompute the eigenvalue register, and keep the result when the ancilla reads 1. What remains is proportional to A−1∣b⟩=∣x⟩A^{-1}|b\rangle = |x\rangle. The cost is about log⁡N⋅s2κ2/ε\log N\cdot s^2\kappa^2/\varepsilon, with ss the sparsity (non-zeros per row) and κ\kappa the condition number, the ratio of largest to smallest eigenvalue. Andrew Childs, Robin Kothari and Rolando Somma improved the accuracy dependence to polylog(1/ε)\mathrm{polylog}(1/\varepsilon) in 2017, and Pedro Costa and colleagues reached the optimal linear dependence on κ\kappa in 2022, using the QSVT ideas of Chapter 119. Established

The fine print

Set your problem: size 6 (log₁₀ unknowns), condition number 2.0 (log₁₀ κ). Then answer: input is or ; output needed is or ; matrix is or .

Each caveat can erase the advantage. Loading NN arbitrary numbers into amplitudes costs about NN operations, unless a special memory device exists. Reading out the full vector needs about NN repetitions, since each run yields one sample. A dense matrix stored as data has the same loading problem. And if κ\kappa grows with NN, as it does for many discretized differential equations, the speedup shrinks to polynomial. Established

Where it might still matter

The favourable cases are those where the matrix and the right-hand side come from a compact physical description, and you want a global property of the solution: the average stress in a region, a scattering amplitude, the probability that a particle is in a cell. Recent work targets linear differential equations in physics and engineering on this basis. Whether practically valuable problems fit all the conditions, at sizes where the quantum overhead pays off, is open. Debated

What you now have

The HHL algorithm, its dependence on size, sparsity, condition number and accuracy, the improved algorithms, and the four pieces of fine print: input loading, output readout, matrix access, and condition number.

· · ·

Three questions to carry with you.

What does HHL output?tap
A quantum state |x⟩ proportional to the solution, not the numbers themselves.
Why does loading classical data cancel the speedup?tap
Preparing an arbitrary N-amplitude state costs about N operations.
What is the condition number’s role?tap
Cost grows with κ; if κ grows with N, the advantage shrinks.

And one to work out. To read out every entry of a solution with N=106N = 10^6 unknowns by sampling, at least how many runs are needed (to one significant figure)?

runs ≥

Sources: A. W. Harrow, A. Hassidim and S. Lloyd, Phys. Rev. Lett. 103, 150502 (2009). A. M. Childs, R. Kothari and R. D. Somma, SIAM J. Comput. 46, 1920 (2017). P. C. S. Costa et al., PRX Quantum 3, 040303 (2022). S. Aaronson, Nat. Phys. 11, 291 (2015). Checked by the plate’s cost model: quantum cost ~ κ s log N per run, classical conjugate gradient ~ N s √κ; readout and loading terms ~ N.

Next · Chapter 121
Dequantization: what survived and what didn't

An undergraduate thesis removed a celebrated exponential quantum speedup.

Turn the page