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">A vector <b>b</b> with 4 numbers becomes the amplitudes of a quantum
state on just <b>2 qubits</b> (log₂4 = 2). Edit the numbers, then normalize: the
squared amplitudes must sum to 1, and each square is the probability of measuring
that basis state. This is <b>amplitude encoding</b> — the first step of HHL.</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">Encode into qubits</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="state" id="state"></div>
<div class="status" id="status">Edit b, then encode.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Amplitude encoding: a vector b = (b0,b1,b2,b3) is stored as the amplitudes of a
// 2-qubit state |psi> = a0|00> + a1|01> + a2|10> + a3|11>, where a_i = b_i / ||b||.
// Then sum(a_i^2) = 1 (a valid quantum state) and a_i^2 is the probability of
// measuring basis state i. This is exactly how HHL loads its input vector b.
const KETS = ['|00⟩','|01⟩','|10⟩','|11⟩'];
const ids = ['b0','b1','b2','b3'];

function readVec(){ return ids.map(id => parseFloat(document.getElementById(id).value) || 0); }
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function encode(){
  const b = readVec();
  const norm = Math.sqrt(b.reduce((s,x)=>s+x*x,0));
  if(norm === 0){ setStatus('The zero vector cannot be encoded — it has no direction to store.','bad');
    document.getElementById('state').innerHTML=''; return; }
  const amps = b.map(x => x / norm);          // normalized amplitudes
  const probs = amps.map(a => a*a);           // measurement probabilities
  const el = document.getElementById('state'); el.innerHTML='';
  amps.forEach((a,i)=>{
    const row=document.createElement('div'); row.className='row';
    const ket=document.createElement('span'); ket.className='ket'; ket.textContent=KETS[i];
    const wrap=document.createElement('div'); wrap.className='bar-wrap';
    const bar=document.createElement('div'); bar.className='bar'+(a<0?' neg':'');
    bar.style.width=(Math.abs(a)*100).toFixed(1)+'%'; wrap.appendChild(bar);
    const pct=document.createElement('span'); pct.className='pct';
    pct.textContent='a='+a.toFixed(3)+'  ('+(probs[i]*100).toFixed(1)+'%)';
    row.append(ket,wrap,pct); el.appendChild(row);
  });
  const probSum = probs.reduce((s,p)=>s+p,0);
  setStatus(fmt('Encoded 4 numbers into 2 qubits. Probabilities sum to %probSum% ✓', { probSum: probSum.toFixed(3) }),'ok');
  console.log('amplitudes', amps.map(a=>+a.toFixed(4)), 'sum of squares', +probSum.toFixed(6));
}
function reset(){ const d=['3','0','1','-2']; ids.forEach((id,i)=>document.getElementById(id).value=d[i]);
  document.getElementById('state').innerHTML=''; setStatus('Edit b, then encode.',''); }
document.getElementById('encode').addEventListener('click',encode);
document.getElementById('reset').addEventListener('click',reset);
encode();

<p class="hint">A vector <b>b</b> with 4 numbers becomes the amplitudes of a quantum
state on just <b>2 qubits</b> (log₂4 = 2). Edit the numbers, then normalize: the
squared amplitudes must sum to 1, and each square is the probability of measuring
that basis state. This is <b>amplitude encoding</b> — the first step of HHL.</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">Encode into qubits</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="state" id="state"></div>
<div class="status" id="status">Edit b, then encode.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Amplitude encoding: a vector b = (b0,b1,b2,b3) is stored as the amplitudes of a
// 2-qubit state |psi> = a0|00> + a1|01> + a2|10> + a3|11>, where a_i = b_i / ||b||.
// Then sum(a_i^2) = 1 (a valid quantum state) and a_i^2 is the probability of
// measuring basis state i. This is exactly how HHL loads its input vector b.
const KETS = ['|00⟩','|01⟩','|10⟩','|11⟩'];
const ids = ['b0','b1','b2','b3'];

function readVec(){ return ids.map(id => parseFloat(document.getElementById(id).value) || 0); }
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function encode(){
  const b = readVec();
  const norm = Math.sqrt(b.reduce((s,x)=>s+x*x,0));
  if(norm === 0){ setStatus('The zero vector cannot be encoded — it has no direction to store.','bad');
    document.getElementById('state').innerHTML=''; return; }
  const amps = b.map(x => x / norm);          // normalized amplitudes
  const probs = amps.map(a => a*a);           // measurement probabilities
  const el = document.getElementById('state'); el.innerHTML='';
  amps.forEach((a,i)=>{
    const row=document.createElement('div'); row.className='row';
    const ket=document.createElement('span'); ket.className='ket'; ket.textContent=KETS[i];
    const wrap=document.createElement('div'); wrap.className='bar-wrap';
    const bar=document.createElement('div'); bar.className='bar'+(a<0?' neg':'');
    bar.style.width=(Math.abs(a)*100).toFixed(1)+'%'; wrap.appendChild(bar);
    const pct=document.createElement('span'); pct.className='pct';
    pct.textContent='a='+a.toFixed(3)+'  ('+(probs[i]*100).toFixed(1)+'%)';
    row.append(ket,wrap,pct); el.appendChild(row);
  });
  const probSum = probs.reduce((s,p)=>s+p,0);
  setStatus(fmt('Encoded 4 numbers into 2 qubits. Probabilities sum to %probSum% ✓', { probSum: probSum.toFixed(3) }),'ok');
  console.log('amplitudes', amps.map(a=>+a.toFixed(4)), 'sum of squares', +probSum.toFixed(6));
}
function reset(){ const d=['3','0','1','-2']; ids.forEach((id,i)=>document.getElementById(id).value=d[i]);
  document.getElementById('state').innerHTML=''; setStatus('Edit b, then encode.',''); }
document.getElementById('encode').addEventListener('click',encode);
document.getElementById('reset').addEventListener('click',reset);
encode();

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.