The HHL Algorithm

HHL does not hand you the numbers in x. It prepares a quantum state proportional to x, on log₂(dimension) qubits instead of the dimension itself — the source of its famous exponential speedup over classically solving Ax = b when A is sparse and well-conditioned. But a quantum state is not a spreadsheet: reading out every component of x classically means tomography, and tomography on an n-qubit state costs exponentially many measurements in n. What HHL is actually good for is folding the solution into a LARGER quantum computation — a single number extracted from x, like xᵀMx for some observable M — where the exponential number of components never has to be read out one at a time. Treat any claim that HHL “solves linear systems exponentially faster,” full stop, as the oversimplification it is.

Phase estimation writes an eigenvalue λ into the clock register as a binary number; the rotation stage is what turns “a number written down” into “1/λ, multiplied into an amplitude.” It rotates the ancilla by an angle θ(λ) with sin(θ/2) = C/λ, controlled on the clock register reading that exact λ — so eigenvalue 1 gets sin(θ/2) = 1.00 (a full π rotation) and eigenvalue 2 gets sin(θ/2) = 0.50 — a bigger eigenvalue always gets a smaller rotation, and therefore a smaller chance of flipping the ancilla to |1⟩. That is the division, written as trigonometry: amplitude sin(θ/2) is exactly C/λ, which is the only place a reciprocal appears anywhere in this circuit.

C has to be small enough that C/λ ≤ 1 for the smallest eigenvalue the clock register can read — this page sets C to that smallest eigenvalue exactly, which is also what makes the overall success probability as large as this fixed-C scheme allows. A matrix with a much smaller eigenvalue mixed in with much larger ones forces C down for everyone, which is the trigonometric fingerprint of HHL’s well-known sensitivity to A’s condition number: the ratio of the largest eigenvalue to the smallest.

Quantum phase estimation is the engine inside stages 2–4 of this page, run on U = e^{iAt}. That page shows QPE on a SINGLE eigenvector; this page runs it on |b⟩, which is a superposition of two of A’s eigenvectors at once — QPE entangles each with its own eigenvalue in the clock register, which is exactly the two-peak distribution the canvas above draws. The quantum Fourier transform page shows the gate-by-gate machinery — Hadamards and controlled phases — that both the forward QFT (in the uncompute half of this circuit) and its inverse (right after the kickback) are built from.

A is restricted here to c₀·I + c₁·X — a real, symmetric 2×2 matrix with equal diagonal entries — because that makes e^{iAt} exactly a global phase times an RX rotation, a gate this engine already has. A general Hermitian matrix needs Hamiltonian simulation — approximating e^{iAt} by Trotterization or another product formula — which is itself a nontrivial algorithm with its own error budget. Nothing here is Trotterized: every gate applied is the exact unitary, which is what makes the numeric check against the classical solve exact to floating-point precision rather than approximate.

The evolution time and clock register size are also hand-picked so both of A’s eigenvalues land exactly on the clock register’s 2-bit grid. A generic matrix gives phase estimation an eigenvalue that is NOT an exact binary fraction — exactly the case the phase estimation page’s precision section covers — which spreads each eigenvalue’s weight across a few neighbouring clock readings instead of one, and would need more clock qubits to resolve them apart in the first place. Finally, preparing |b⟩ is treated as free: for this specific b it costs nothing (see the “Prepare |b⟩” stage), but preparing an arbitrary n-qubit |b⟩ in general is its own hard problem that HHL assumes is already solved.