HHL and quantum linear algebra, with input/output caveats
Solving a system of linear equations, , 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 as a quantum state . Run phase estimation (Chapter 113) with to write each eigenvalue of into a register. Rotate an ancilla by an angle proportional to , uncompute the eigenvalue register, and keep the result when the ancilla reads 1. What remains is proportional to . The cost is about , with the sparsity (non-zeros per row) and the condition number, the ratio of largest to smallest eigenvalue. Andrew Childs, Robin Kothari and Rolando Somma improved the accuracy dependence to in 2017, and Pedro Costa and colleagues reached the optimal linear dependence on 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 arbitrary numbers into amplitudes costs about operations, unless a special memory device exists. Reading out the full vector needs about repetitions, since each run yields one sample. A dense matrix stored as data has the same loading problem. And if grows with , 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.
And one to work out. To read out every entry of a solution with unknowns by sampling, at least how many runs are needed (to one significant figure)?
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.