MilestoneTheory & algorithmsConfirmed
Harrow, Hassidim and Lloyd publish a quantum algorithm for solving linear equations
Oct 7, 2009
Aram Harrow, Avinatan Hassidim and Seth Lloyd describe a quantum algorithm that, for sparse, well-behaved systems of linear equations, can estimate properties of the solution exponentially faster than the best classical algorithm. A first version was posted in November 2008.
Why it matters
Linear equations appear throughout science and engineering, so this promised a big speedup for a very common task, though only when a summary of the answer is enough, not the full solution.
Aram W. Harrow · Avinatan Hassidim · Seth Lloyd · MIT
Source
-
arXiv (Harrow, Hassidim and Lloyd)
Quantum algorithm for solving linear systems of equations
“In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm.”
Each quote above was checked automatically against the original page. Added Oct 15, 2026. Spotted an error? Tell us and we will review it.