Harrow-Hassidim-Lloyd Algorithm
The HHL algorithm prepares a quantum state proportional to the solution of a linear system, with runtime polylogarithmic in dimension under strong assumptions.
The linear-system problem
Given a matrix A and vector b, solve A x = b. Classically this costs at least linear time in the dimension N for general dense systems. The Harrow-Hassidim-Lloyd (HHL) algorithm instead prepares a quantum state |x> proportional to the solution vector in time polylogarithmic in N, provided A is sparse and well-conditioned and b can be prepared efficiently. It does not output x classically; it outputs a state encoding x.
How it works
HHL rests on eigen-decomposition. Write |b> in the eigenbasis of A: |b> = sum_j beta_j |u_j>, where A|u_j> = lambda_j |u_j>. The solution is |x> = sum_j (beta_j/lambda_j)|u_j>. HHL realizes the 1/lambda_j scaling with three moves.
- Phase estimation writes each eigenvalue lambda_j into an ancilla register, giving sum_j beta_j |u_j>|lambda_j>.
- A controlled rotation rotates a flag ancilla by an angle proportional to arcsin(C/lambda_j), producing amplitude proportional to 1/lambda_j on the flag-1 branch.
- Uncompute the eigenvalue register and post-select the flag on 1, yielding |x> proportional to sum_j (beta_j/lambda_j)|u_j>.
Runtime
The complexity scales roughly as O(log(N) s^2 kappa^2 / epsilon), where s is sparsity, kappa is the condition number (ratio of largest to smallest eigenvalue magnitude), and epsilon is accuracy. The exponential improvement in N is real but is bought against strong dependence on kappa and on the input and output models.
What you can and cannot do
Reading out all N components of x classically costs O(N), erasing the speedup. HHL pays off when the goal is an expectation value