Linear systems of equations (HHL and successors)
Algorithms and benchmarks / Linear algebra and eigenvalues
Prepares a quantum state proportional to the solution of a sparse, well-conditioned linear system, from which expectation values can be read. Variants address differential equations and other matrix functions.
- Era
- Fault-tolerant
- Problem class
- Linear algebra and eigenvalues
- Speedup
- Runs in poly(log N, kappa) time for an N by N sparse matrix with condition number kappa, against O(N square root of kappa) for the best classical algorithm, for the task of estimating properties of the solution (HHL 2009).
How it works
Phase estimation exposes the eigenvalues of the matrix, a controlled rotation inverts them and uncomputation leaves the solution encoded in amplitudes (Harrow, Hassidim and Lloyd 2009); QSVT gives a more general and efficient framework (Gilyén et al. 2019).
Typical use cases
- Partial differential equations in fluid dynamics and engineering.
- Subroutines of quantum machine learning proposals.
Documented use cases on related problems
From the use case directory; the sources of these cases may use other methods than this one.
Resource estimates
No resource estimate with stated assumptions was verified for this family in this release.
Demonstrations
Only toy-size demonstrations have been reported; none was verified for this release.
Hardware platforms that fit
Platform-independent: a fault-tolerant gate-based algorithm; no platform-specific resource estimate was verified for this release.
What you need to run it
- Classical simulation
- A state-vector simulator holds 2^n complex amplitudes, so memory doubles with every qubit: about 30 qubits fit in 16 GiB at double precision. Circuits with little entanglement can go further with tensor-network methods. See the guide for the calculator.
- Noisy hardware (NISQ)
- Not applicable for this family.
- Fault-tolerant machine
- Deep circuits with phase estimation and state preparation; no verified resource estimate for a practical instance is listed here.
- Annealer or analogue simulator
- Not applicable for this family.
Software
European tools in the software directory
Other open-source frameworks
- Qiskit (IBM (United States); non-European)
A listing is not an endorsement; check each tool for the features you need.
Limitations and open questions
- The output is a quantum state, not the solution vector; reading all of it would cancel the speedup.
- The matrix must be sparse and well conditioned and the input state cheap to prepare.
- Quantum-inspired classical algorithms remove the exponential speedup of some related proposals under similar input assumptions (Tang 2019, for recommendation systems).
In the Quantum Algorithm Zoo
- Linear Systems (Quantum Algorithm Zoo, external site): Optimization, Numerics, and Machine Learning; speedup as the Zoo states it: Superpolynomial
Index: the Quantum Algorithm Zoo by Stephen P. Jordan, last updated 2026-09-10, checked 2026-10-23. The portal links to it and copies no description from it. Browse the full Quantum Algorithm Zoo (external site)
Named in European procurements
- Used in: EuroHPC procurement EuroQCS-France (now Lucy) (Required in the benchmark suite (scored under the award criteria))
As the tender documents state; how a benchmark is weighted against others is described in each procurement.
Sources
- A. W. Harrow, A. Hassidim, S. Lloyd (2009). Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009); arXiv:0811.3171. Read: abstract page, retrieved 2026-10-23.
- A. Gilyén, Y. Su, G. H. Low, N. Wiebe (2019). Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. Proceedings of STOC 2019, 193; arXiv:1806.01838. Read: abstract page, retrieved 2026-10-23.
- E. Tang (2019). A quantum-inspired classical algorithm for recommendation systems. Proceedings of STOC 2019, DOI 10.1145/3313276.3316310; arXiv:1807.04271. Read: abstract page, retrieved 2026-10-23.