“Quantum Algorithm for Solving Linear Systems of Equations,” by Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, was submitted to arXiv in November 2008 and published in Physical Review Letters in 2009. It is universally known by the authors’ initials as the HHL algorithm. Solving a system of linear equations - finding the vector x in Ax = b - is one of the most common operations in all of computing, sitting underneath regression, simulation, and much of machine learning.
The paper does not promise the full solution vector. Instead it shows that when the matrix A is sparse and N by N with condition number kappa, a quantum computer can prepare a quantum state proportional to the solution x and read out expectation values of the form x’Mx in time that scales as poly(log N, kappa). Classical methods that produce the same kind of estimate scale at best with N itself. That is an exponential improvement in the size of the system, the headline result that made the paper famous.
The fine print matters and was widely misunderstood. The speedup requires that the input b can be loaded efficiently into a quantum state, that A is sparse and well-conditioned, and that you only want a summary statistic of x rather than every entry. Strip away any of those assumptions and the advantage can vanish; later “dequantization” work by Ewin Tang showed that some problems thought to need HHL could be matched classically. Even so, HHL became the template for a wave of proposed quantum machine-learning routines for least-squares fitting, support vector machines, and recommendation systems.
Why business readers should care: HHL is the clearest example of why quantum computing is exciting and why the excitement needs caveats. The theoretical speedups are real, but they apply to narrow problem shapes with demanding preconditions, and turning them into a practical advantage on real hardware remains unproven.