Lesson 24: The Harrow–Hassidim–Lloyd (HHL) Algorithm¶
24.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- State precisely the problem HHL solves — and, equally importantly, the problem it does not solve.
- Derive the algorithm: state preparation → QPE → controlled rotation → uncompute → post-select.
- Analyse the complexity \(O(\log N\, s^2\kappa^2/\epsilon)\) and identify each factor's origin.
- State the four caveats (Aaronson's list) that limit practical speed-up.
- Recognise HHL as the engine of quantum linear regression, differential-equation solvers and some QML proposals.
24.2 The Problem¶
Classical. Given \(A\in\mathbb{C}^{N\times N}\) and \(\vec b\in\mathbb{C}^{N}\), solve \(A\vec x = \vec b\).
Best classical methods: Gaussian elimination \(O(N^3)\); conjugate gradient \(O(Ns\kappa)\) for \(s\)-sparse, well-conditioned \(A\), where \(\kappa = \frac{|\lambda_{\max}|}{|\lambda_{\min}|}\) is the condition number.
Quantum (HHL, 2009). Given oracle access to \(A\) and a routine preparing \(|b\rangle\), produce a quantum state
in time
Exponentially better in \(N\) — \(\log N\) instead of \(N\).
The caveat, stated up front¶
HHL does not output the vector \(\vec x\). It outputs a quantum state \(|x\rangle\) whose amplitudes are proportional to the entries of \(\vec x\). Reading out all \(N\) entries requires \(\Omega(N)\) measurements, destroying the speed-up entirely. HHL is useful only when you want a scalar summary such as \(\langle x|M|x\rangle\) for some observable \(M\) — an average, a norm, a weighted sum, an overlap.
Teach this caveat before the algorithm, not after. It is the single most misrepresented result in quantum computing.
24.3 Assumptions¶
| Assumption | Why it is needed |
|---|---|
| \(A\) is Hermitian | so \(e^{iAt}\) is unitary. Non-Hermitian \(A\) is handled by the dilation \(\tilde A = \begin{pmatrix}0 & A\\ A^\dagger & 0\end{pmatrix}\) |
| \(A\) is \(s\)-sparse and row-computable | so \(e^{iAt}\) can be simulated efficiently |
| \(\kappa\) is small (well-conditioned) | complexity is \(O(\kappa^2)\); ill-conditioned systems are hopeless |
| \(\vert b\rangle\) is efficiently preparable | otherwise state preparation costs \(O(N)\) and dominates |
| Eigenvalues scaled into \((0,1)\) | so QPE phases lie in range |
24.4 The Algorithm¶
Registers¶
- Input register (\(\log N\) qubits): holds \(|b\rangle\), later becomes \(|x\rangle\).
- Clock register (\(t\) qubits): for phase estimation.
- Ancilla (1 qubit): for the conditional rotation and post-selection.
Steps¶
Step 0 — expand \(|b\rangle\) in the eigenbasis of \(A\). Let \(A|u_j\rangle = \lambda_j|u_j\rangle\) with \(\{|u_j\rangle\}\) orthonormal (guaranteed by Hermiticity). Write
This expansion is a bookkeeping device — we never compute the \(\beta_j\).
Step 1 — Quantum phase estimation with \(U = e^{iAt_0}\), whose eigenvalues are \(e^{i\lambda_jt_0}\):
The clock register now holds each eigenvalue, entangled with its eigenvector.
Step 2 — Controlled rotation. Append an ancilla and rotate it by an angle depending on \(\tilde\lambda_j\):
where \(C = O(1/\kappa)\) is a normalisation constant chosen so the argument stays \(\le1\).
This step is the heart of the algorithm: it multiplies each eigen-component's amplitude by \(1/\lambda_j\) — which is exactly what applying \(A^{-1}\) does. Implemented by computing \(\arcsin(C/\tilde\lambda)\) into an ancillary register (reversible classical arithmetic) and applying a controlled \(R_y\).
Step 3 — Uncompute the clock register by running QPE backwards. This is essential: otherwise the clock stays entangled with the eigenvectors and \(|x\rangle\) is not a pure state.
Step 4 — Measure the ancilla and post-select on \(|1\rangle\). Conditioned on that outcome:
Success probability.
With amplitude amplification (L22 §5.1), this is boosted to \(O(1)\) using \(O(\kappa)\) repetitions rather than \(O(\kappa^2)\).
24.5 Complexity Breakdown¶
| Factor | Source |
|---|---|
| \(\log N\) | number of qubits — the exponential win |
| \(s^2\) | sparse Hamiltonian simulation of \(e^{iAt}\) |
| \(\kappa\) (one factor) | QPE must resolve \(\lambda_{\min}\), requiring \(t_0 = O(\kappa/\epsilon)\) |
| \(\kappa\) (second factor) | post-selection success probability \(\Omega(1/\kappa^2)\), halved to \(O(\kappa)\) by amplitude amplification |
| \(1/\epsilon\) | phase-estimation precision |
Improvements. Childs–Kothari–Somma (2015) improved the \(\epsilon\) dependence to \(O(\mathrm{poly}\log(1/\epsilon))\) using linear-combination-of-unitaries and quantum walks. Ambainis (2012) achieved linear \(\kappa\) dependence via variable-time amplitude amplification. Current best:
Lower bound. HHL is BQP-complete: solving linear systems to this specification is as hard as any quantum computation. Hence no classical polynomial algorithm exists unless BPP = BQP, and the \(\kappa\) and \(s\) dependences cannot be removed.
24.6 The Four Caveats (Aaronson, Nature Physics, 2015)¶
"Read the fine print." All four must hold simultaneously for a real speed-up.
1. State preparation. You must produce \(|b\rangle = \frac{1}{\|\vec b\|}\sum_i b_i|i\rangle\) efficiently. For arbitrary classical data this costs \(O(N)\) — killing the advantage. It works only if \(\vec b\) has structure (e.g. it is given by a formula, or produced by an earlier quantum subroutine), or if efficient qRAM exists.
2. Hamiltonian simulation. \(e^{iAt}\) must be efficiently implementable, requiring \(A\) to be sparse (or of low rank) and its entries efficiently computable.
3. Condition number. Runtime scales with \(\kappa\). Real-world matrices are often ill-conditioned; preconditioning is essential but preconditioners are themselves hard to build quantumly.
4. Readout. You obtain \(|x\rangle\), not \(\vec x\). Only scalar functionals like \(\langle x|M|x\rangle\) are cheap.
Dequantisation¶
Ewin Tang (2018–19), then an undergraduate, showed that several HHL-based QML algorithms (recommendation systems, PCA, low-rank linear systems) admit classical algorithms with the same \(\mathrm{polylog}(N)\) scaling, provided the classical algorithm is given the same \(\ell^2\)-norm sampling access that the quantum algorithm implicitly assumes.
The lesson. Much of the claimed exponential advantage came from the input model, not from quantum mechanics. Exponential speed-up survives only for genuinely high-rank, sparse, well-conditioned problems where the input is generated quantumly. This is now the standard caution in the field, and students should carry it into Unit III.
24.7 Solved Problems¶
Problem 1 — HHL on a 2×2 system, by hand¶
Solve \(A\vec x = \vec b\) with \(A = \begin{pmatrix}1 & 0\\ 0 & 2\end{pmatrix}\), \(\vec b = \frac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix}\), tracing the HHL steps.
Solution.
Eigen-decomposition. \(A\) is already diagonal: \(\lambda_1 = 1\) with \(|u_1\rangle=|0\rangle\), \(\lambda_2 = 2\) with \(|u_2\rangle = |1\rangle\).
Step 1 — QPE writes the eigenvalues into the clock register:
Step 2 — controlled rotation with \(C = 1\) (safe since \(\lambda_{\min}=1\)):
(for \(\lambda=1\): \(C/\lambda = 1\), so \(\sqrt{1-1}=0\); for \(\lambda=2\): \(C/\lambda = \frac12\), \(\sqrt{1-\frac14} = \frac{\sqrt3}{2}\).)
Step 3 — uncompute the clock.
Step 4 — post-select ancilla \(=1\). The surviving (unnormalised) state is
Norm\(^2 = \frac12 + \frac18 = \frac58\). Normalising:
Verify against the classical solution.
Normalised: \(\frac{1}{\sqrt{1.25}}(1, 0.5)^T = (0.8944, 0.4472)^T = \left(\frac{2}{\sqrt5},\frac{1}{\sqrt5}\right)^T\) ✓
Success probability. \(\Pr[1] = \frac{5}{8} = 62.5\%\).
Note what was obtained: the direction of \(\vec x\), not its magnitude. The overall scale \(\|\vec x\|\) is lost in normalisation and must be estimated separately (e.g. from the post-selection probability).
Problem 2 — Condition number and its cost¶
Compute \(\kappa\) for \(A_1 = \begin{pmatrix}1&0\\0&2\end{pmatrix}\), \(A_2 = \begin{pmatrix}1 & 0.99\\ 0.99 & 1\end{pmatrix}\), and compare HHL runtimes.
Solution.
\(A_1\): eigenvalues 1 and 2.
\(A_2\): symmetric with eigenvalues \(1\pm0.99\), i.e. \(1.99\) and \(0.01\).
Runtime ratio (using the \(O(\kappa^2)\) scaling of original HHL):
With the improved \(O(\kappa)\) algorithms, the ratio is still \(\approx100\times\).
Interpretation. \(A_2\) is nearly singular: its rows are almost parallel. HHL must run QPE with enough precision to resolve \(\lambda_{\min} = 0.01\), requiring \(t_0 \sim \kappa/\epsilon\) and correspondingly deep circuits, and the post-selection succeeds only \(\sim1/\kappa^2\) of the time.
Practical rule: HHL is worthwhile only when \(\kappa = O(\mathrm{polylog}\,N)\). Since real physical and engineering systems typically have \(\kappa\) growing polynomially with problem size, preconditioning is not optional — and constructing quantum preconditioners is an open research problem.
Problem 3 — Estimating an observable, the correct use of HHL¶
After HHL, we want \(\langle x|M|x\rangle\) where \(M = |0\rangle\langle0|\) (i.e. \(|x_0|^2/\|x\|^2\)). Using Problem 1's result, compute it and state the sampling cost to 1 % relative accuracy.
Solution.
From Problem 1, \(|x\rangle = \frac{2}{\sqrt5}|0\rangle + \frac{1}{\sqrt5}|1\rangle\).
Sampling cost. Measure in the computational basis and count zeros. This is a Bernoulli estimate with \(p = 0.8\):
Require relative accuracy 1 %, i.e. absolute accuracy \(0.008\):
Add post-selection overhead. Each useful shot requires the ancilla to read 1, which happens with probability \(0.625\):
This is HHL used correctly: a single scalar functional of \(\vec x\), estimated with a problem-size-independent number of shots. Extracting all \(N\) components would instead require \(\Omega(N)\) shots and eliminate the advantage.
Problem 4 — Where HHL genuinely helps¶
Identify which of these problems admits a real HHL speed-up, and justify each answer.
(a) Solve a \(10^{6}\times10^{6}\) dense system and print all entries of \(\vec x\). (b) Compute the total resistance of a large sparse electrical network. (c) Estimate the mean of \(\vec x\) where \(A\) is a sparse Laplacian and \(\vec b\) is uniform. (d) Machine-learning regression on a low-rank data matrix.
Solution.
(a) No. Two independent failures: (i) dense \(A\) (\(s = N\)) breaks the sparsity assumption, and Hamiltonian simulation costs \(O(N)\); (ii) printing all \(10^{6}\) entries needs \(\Omega(N)\) measurements. Both readout and simulation caveats are violated.
(b) Yes, potentially. Effective resistance between two nodes is \(R_{uv} = (\vec e_u - \vec e_v)^T L^{+}(\vec e_u - \vec e_v)\) — a scalar functional of the solution. The graph Laplacian \(L\) is sparse for bounded-degree graphs, and \(\vec b\) is a simple two-nonzero vector, trivially preparable. The one risk is \(\kappa\): for graphs with poor connectivity, \(\lambda_{\min}\) (the spectral gap) can be tiny. Speed-up holds for expander-like graphs.
(c) Yes. The mean \(\frac{1}{N}\sum_i x_i \propto \langle s|x\rangle\) where \(|s\rangle = \frac{1}{\sqrt N}\sum_i|i\rangle\) — computable by a swap test in \(O(1)\) shots per unit precision. \(\vec b\) uniform means \(|b\rangle = |s\rangle = H^{\otimes n}|0\rangle\) — one layer of Hadamards. Sparse Laplacian ✓, scalar output ✓, easy preparation ✓. All four caveats satisfied.
(d) No — dequantised. Low rank is precisely the case Tang's algorithms handle. A classical algorithm with \(\ell^2\)-sampling access achieves \(\mathrm{polylog}(N)\) scaling too. Only a polynomial speed-up (in rank and condition number) survives, not an exponential one.
Pattern. HHL helps when the matrix is sparse and high-rank, the input is structured or quantum-generated, the condition number is small, and the output is a scalar.
Problem 5 — HHL for quantum linear regression¶
Show how ordinary least squares \(\vec\beta = (X^TX)^{-1}X^T\vec y\) maps onto HHL, and state the speed-up and its conditions.
Solution.
Setup. Data matrix \(X\in\mathbb{R}^{M\times d}\) (\(M\) samples, \(d\) features), targets \(\vec y\in\mathbb{R}^{M}\). The normal equations are
Mapping to HHL.
- \(A = X^TX\) is Hermitian (symmetric real) and positive semi-definite ✓ — no dilation needed.
- \(A\) is \(d\times d\), so HHL runs on \(\log_2 d\) qubits.
- \(|b\rangle \propto X^T\vec y\) must be prepared — feasible if \(X\) and \(\vec y\) come from a quantum process or efficient qRAM.
- Output: \(|\beta\rangle \propto A^{-1}|b\rangle\) — the regression coefficients as amplitudes.
Complexity.
Exponential in \(d\) — but only under the standing conditions.
What can be extracted usefully.
| Quantity | Cost |
|---|---|
| Predict a new point \(\hat y_{\text{new}} = \vec x_{\text{new}}^T\vec\beta\) | \(O(1)\) shots — a swap test overlap ✓ |
| Coefficient of determination \(R^2\) | scalar functional ✓ |
| Total coefficient norm $\Vert \vec\beta\Vert $ | from the post-selection probability ✓ |
| All \(d\) coefficients \(\beta_1,\dots,\beta_d\) | \(\Omega(d)\) shots ✗ — no speed-up |
The condition number problem is severe here. \(\kappa(X^TX) = \kappa(X)^2\) — squaring the data matrix's condition number. Highly correlated features (multicollinearity) make \(\kappa\) enormous. Ridge regression helps: replacing \(A\) by \(X^TX + \lambda I\) raises \(\lambda_{\min}\) to at least \(\lambda\), giving \(\kappa \le \frac{\lambda_{\max}+\lambda}{\lambda}\). Regularisation is therefore not just statistically desirable but computationally essential for the quantum algorithm.
Honest summary. Quantum linear regression gives an exponential speed-up for making predictions, not for learning interpretable coefficients. This distinction runs through all of Unit III's QML content.
24.8 Practice Problems¶
- Solve \(A\vec x=\vec b\) by HHL for \(A = \mathrm{diag}(1,3)\), \(\vec b = \frac{1}{\sqrt2}(1,1)^T\). Give \(|x\rangle\) and \(\Pr[\text{ancilla}=1]\) with \(C=1\). [Ans: \(|x\rangle\propto 3|0\rangle+|1\rangle\); \(\Pr=5/9\)]
- Compute \(\kappa\) for \(\begin{pmatrix}2&1\\1&2\end{pmatrix}\). [Ans: 3]
- Why must the clock register be uncomputed?
- List Aaronson's four caveats and give one example where each is violated.
- Explain why \(\kappa(X^TX) = \kappa(X)^2\).
- Show that a dilation \(\tilde A\) handles non-Hermitian \(A\); write the corresponding \(\tilde b\).
- Give one problem where HHL provably helps and one where it is dequantised.
24.9 Summary¶
- HHL produces the quantum state \(|x\rangle\propto A^{-1}|b\rangle\) in \(O(\log N\,s^2\kappa^2/\epsilon)\) — exponentially better in \(N\) than classical solvers.
- Steps: prepare \(|b\rangle\) → QPE writes eigenvalues into a clock register → controlled rotation multiplies amplitudes by \(C/\lambda_j\) → uncompute the clock → post-select the ancilla on \(|1\rangle\).
- The \(\kappa^2\) arises from QPE precision and post-selection probability; amplitude amplification reduces it to \(\kappa\).
- HHL is BQP-complete, so the caveats cannot all be removed.
- Aaronson's four caveats: state preparation, Hamiltonian simulation (sparsity), condition number, and readout. HHL gives \(|x\rangle\), not \(\vec x\) — only scalar functionals are cheap.
- Tang's dequantisation eliminated the exponential advantage for low-rank problems; it survives only for sparse, high-rank, well-conditioned systems with quantum-native inputs and scalar outputs.
- Applications: effective resistance, differential equations, quantum linear regression (prediction, not coefficient recovery), and as a subroutine in QML (Unit III).
Next lesson: L25 — Post-quantum cryptography: Kyber and quantum-attack-resistant signatures.
Practise now: unit2-algorithms-lab.html → HHL Explorer: enter a \(2\times2\) or \(4\times4\)
system, see the eigen-decomposition, the conditional-rotation angles, the post-selection probability
and a comparison of \(|x\rangle\) with the exact classical solution.