# HHL algorithm
**HHL algorithm** (Harrow-Hassidim-Lloyd algorithm) is a quantum algorithm for solving systems of linear equations $Ax = b$ where $A$ is an $N\times N$ sparse Hermitian matrix. Proposed in 2009, it achieves an exponential speedup over classical linear solvers under certain conditions.

A classical sparse linear system solver (e.g. conjugate gradient) runs in time $O(Ns\kappa\log(1/\varepsilon))$ where $s$ is the sparsity (number of non-zero entries per row), $\kappa$ is the condition number, and $\varepsilon$ is the desired precision. HHL runs in time $O(\log(N)s^2\kappa^2/\varepsilon)$ — exponentially faster in $N$.

## Algorithm
HHL encodes $\lvert b\rangle$ as a quantum state and applies [[qpe|quantum phase estimation]] to the operator $A$ to record the eigenvalues $\lambda_j$ of $A$ in an ancilla register. A controlled rotation then maps $\lvert\lambda_j\rangle \mapsto (C/\lambda_j)\lvert\lambda_j\rangle$ for each eigencomponent, effectively computing $A^{-1}$. Finally, the ancilla is uncomputed by inverse QPE, leaving the solution state $\lvert x\rangle \propto A^{-1}\lvert b\rangle$.

## Caveats
The HHL speedup comes with important caveats. First, the input $\lvert b\rangle$ must be efficiently preparable as a quantum state — loading a classical vector of $N$ entries generally costs $O(N)$, eliminating the speedup. Second, the output is a quantum state $\lvert x\rangle$, not a classical vector; reading out all $N$ components requires $O(N)$ measurements. The speedup is therefore only useful when one needs a scalar property of $x$, such as $\langle x\rvert M\lvert x\rangle$ for some efficiently implementable observable $M$. These limitations make practical use of HHL quite narrow, and it is not yet clear whether HHL provides a genuine end-to-end speedup for any commercially relevant problem.