HHL Algorithm

The HHL algorithm, published in 2009 by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, solves linear systems of the form Ax = b, returning a quantum state proportional to the solution vector x in time that scales logarithmically with the system's size, an exponential speedup over the best classical linear solvers under the right conditions. Those conditions are the catch: the speedup requires the matrix A to be sparse and well-conditioned, the input vector b must already be loadable as a quantum state (itself a hard problem in general), and the output is a quantum state encoding the solution rather than the solution's individual numbers, so reading out specific values requires additional measurement and often erases the speedup entirely. HHL is best understood as a subroutine other quantum algorithms build on, most notably several proposed quantum machine learning algorithms that reduce to solving a linear system internally, rather than a general-purpose replacement for classical linear algebra. No fault-tolerant hardware exists yet that can run HHL at a scale where its asymptotic advantage would show up in practice.