HHL Algorithm (Quantum Linear Systems)

HHL solves linear systems Ax=b with an exponential speedup in dimension — under conditions — by encoding the solution in a quantum state.

Speedup

exponential in N (with caveats)

Core

phase estimation + controlled rotation

Caveat

state prep, condition number, readout limits

What it does

HHL uses phase estimation to expose the eigenvalues of A, applies a controlled rotation to invert them, then uncomputes. The result is a quantum state proportional to x — great for computing ⟨x|M|x⟩-type quantities, less so if you need every component of x.

Where it's used

Building block for quantum machine learning and differential-equation solvers; its caveats (sparse, well-conditioned A; efficient state prep) are as important as its promise.

In code (Qiskit)

# HHL: QPE(A) -> controlled 1/lambda rotation -> inverse QPE