MilestoneTheory & algorithmsConfirmed

Harrow, Hassidim and Lloyd publish a quantum algorithm for solving linear equations

Nov 19, 2008

Harrow, Hassidim and Lloyd describe a quantum algorithm that estimates properties of a linear system's solution exponentially faster in its size, provided the matrix is sparse and well-conditioned and the input state can be prepared efficiently.

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

See it on the timeline

Sources (2)

arXiv (Harrow, Hassidim and Lloyd) Quantum algorithm for solving linear systems of equations
Primary sourceNov 19, 2008

“Here, we exhibit a quantum algorithm for solving linear sets of equations that runs in O(log n) time, an exponential improvement over the best classical algorithm.”
arXiv (Harrow, Hassidim and Lloyd) Quantum algorithm for solving linear systems of equations
Primary sourceNov 19, 2008

“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.”

Added Oct 15, 2026 · Updated Oct 27, 2026. Spotted an error? Tell us and we will review it.