The HHL Algorithm

Half of computational science boils down to one humble request: solve Ax = b. Find the vector x such that a known matrix A times x gives a known vector b. It hides inside weather models, machine learning, circuit simulation, and the physics of nearly everything that bends, flows, or vibrates.

Classically, solving an n-variable system costs roughly n steps at best for nice sparse matrices — and that n can run into the billions. In 2009, Aram Harrow, Avinatan Hassidim, and Seth Lloyd published a quantum algorithm — now called HHL — that, for the right inputs, runs in time that grows only with the logarithm of n. That is an exponential speedup.

It sounds too good to be true, and there is a catch — a beautiful, instructive one. To even feed b into the machine, you have to perform a trick called amplitude encoding, and that same trick shapes everything the algorithm can and cannot do.

Before HHL can solve anything, the input vector b must live inside a quantum computer. The trick is amplitude encoding: a vector with n numbers is stored as the amplitudes of a state on only $\log_{2}(n)$ qubits. Four numbers fit in 2 qubits; a billion numbers fit in 30.

Edit the components of b below and watch them become the amplitudes of a quantum state. The encoding always normalizes the vector (the squared amplitudes must sum to 1), and each amplitude's square is the probability you would see that basis state if you measured.

<p class="hint">{{hint}}</p>
<div class="inputs">
  <label>b₀ <input id="b0" type="number" value="3" step="0.1"></label>
  <label>b₁ <input id="b1" type="number" value="0" step="0.1"></label>
  <label>b₂ <input id="b2" type="number" value="1" step="0.1"></label>
  <label>b₃ <input id="b3" type="number" value="-2" step="0.1"></label>
</div>
<div class="btns">
  <button id="encode" type="button">{{btn_encode}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="state" id="state"></div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.inputs { display: flex; gap: .6rem; flex-wrap: wrap; margin: .4rem 0 .7rem; }
.inputs label { font: 600 13px ui-monospace, monospace; color: #1d3557; display: flex; align-items: center; gap: .35rem; }
.inputs input { width: 64px; font: 600 14px ui-monospace, monospace; padding: .3rem .4rem; border: 1px solid #cdd9e3; border-radius: 6px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.state { display: grid; gap: .4rem; margin: .5rem 0; }
.row { display: grid; grid-template-columns: 56px 1fr 130px; align-items: center; gap: .5rem; font: 600 13px ui-monospace, monospace; }
.ket { color: #1d3557; }
.bar-wrap { background: #eef2f6; border-radius: 6px; height: 22px; overflow: hidden; }
.bar { height: 100%; background: #1d3557; transition: width .25s; }
.bar.neg { background: #e63946; }
.pct { color: #444; font-weight: 500; text-align: right; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Here is the whole story in miniature. Loading n numbers into $\log_{2}(n)$ qubits is astonishingly compact — that compression is where the exponential speedup comes from. But notice the flip side: once the answer x lives in those amplitudes, you cannot simply read all n of them back. Measuring gives you one sample at a time. HHL is fast precisely because it never lets you see the full answer — only summaries of it. This connects to the broader limits explored in P vs NP and the power of Shor's algorithm.

HHL is a proven, correct quantum algorithm (Harrow, Hassidim & Lloyd, 2009). It is not a conjecture and not open — what is debated is when its speedup is real. The runtime is roughly O(log(n) · κ² · s² / ε), and every factor tells you a condition:

• log(n) — the exponential win. Where classical solvers scale with n, HHL scales with its logarithm. This is the headline.
• κ (condition number) — A must be well-conditioned. If the matrix is close to singular, κ blows up and the advantage evaporates.
• s (sparsity) — A must be sparse: each row has only a few nonzero entries, and they must be efficiently computable.
• ε (precision) — error scales as 1/ε, so high-precision answers cost more.
• The readout caveat — the output is the quantum state |x⟩, not the list of numbers. You can estimate an expectation value like xᵀMx cheaply, but printing all of x would erase the speedup.
• Loading b — amplitude-encoding b must also be efficient (often assuming a QRAM that does not yet exist at scale).

So HHL lives in BQP, the class of problems a quantum computer solves efficiently. Strip away any of the conditions — make A dense, ill-conditioned, or demand the full vector out — and the exponential gap shrinks or vanishes. Related to the dequantization debate, classical algorithms inspired by HHL can sometimes match it, sharpening exactly where quantum still wins.

Because Ax = b is everywhere, an exponentially faster solver would ripple across science — if the conditions hold and the answer is one you can read as a summary:

• Machine learning: least-squares fitting, support vector machines, and Gaussian processes all reduce to linear systems; HHL inspired a wave of "quantum machine learning" proposals.
• Differential equations: discretizing physics — heat, fluids, electromagnetism — produces huge sparse linear systems, the ideal target.
• Optimization: interior-point methods solve a linear system at every step.
• Recommendation and data analysis: estimating a single feature of a solution (an expectation value) is exactly what HHL does well.

The honest lesson is in the caveats. HHL is the algorithm that taught the field to ask the sharper question: not "is it faster?" but "faster including loading the input and reading the output?" That discipline now guides the hunt for genuine quantum advantage. To see a problem where the quantum speedup is far less disputed, compare Shor's algorithm for factoring.

The HHL algorithm is a genuine landmark: a quantum method that solves Ax = b in time logarithmic in the number of unknowns, proven correct by Harrow, Hassidim and Lloyd in 2009. Its engine is amplitude encoding — packing n numbers into $\log_{2}(n)$ qubits — and that same compression is both its superpower and its limit.

The catch is the whole point. The answer lives in a quantum state you can sample but never fully print, the matrix must be sparse and well-conditioned, and loading the input must itself be cheap. HHL is less a finished tool than a sharp lens: it showed that "exponential speedup" is a claim you must read all the way to the fine print — a lesson that now guides the entire search for quantum advantage.