Skip to content

Lesson 24: The Harrow–Hassidim–Lloyd (HHL) Algorithm

24.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State precisely the problem HHL solves — and, equally importantly, the problem it does not solve.
  2. Derive the algorithm: state preparation → QPE → controlled rotation → uncompute → post-select.
  3. Analyse the complexity \(O(\log N\, s^2\kappa^2/\epsilon)\) and identify each factor's origin.
  4. State the four caveats (Aaronson's list) that limit practical speed-up.
  5. 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

\[ |x\rangle \propto A^{-1}|b\rangle \]

in time

\[ O\!\left(\frac{\log N \cdot s^{2}\kappa^{2}}{\epsilon}\right) . \]

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

\[ |b\rangle = \sum_{j=1}^{N}\beta_j\,|u_j\rangle, \qquad \beta_j = \langle u_j|b\rangle . \]

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}\):

\[ \sum_j \beta_j |u_j\rangle|0\rangle \ \longrightarrow\ \sum_j\beta_j\,|u_j\rangle\,\big|\tilde\lambda_j\big\rangle \]

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\):

\[ \sum_j\beta_j|u_j\rangle|\tilde\lambda_j\rangle \left(\sqrt{1 - \frac{C^2}{\lambda_j^2}}\;|0\rangle + \frac{C}{\lambda_j}\,|1\rangle\right) \]

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.

\[ \sum_j\beta_j|u_j\rangle|0\rangle \left(\sqrt{1-\frac{C^2}{\lambda_j^2}}|0\rangle + \frac{C}{\lambda_j}|1\rangle\right) \]

Step 4 — Measure the ancilla and post-select on \(|1\rangle\). Conditioned on that outcome:

\[ |x\rangle \propto \sum_j \frac{\beta_j}{\lambda_j}|u_j\rangle = A^{-1}|b\rangle \ \checkmark \]

Success probability.

\[ \Pr[\text{ancilla}=1] = \sum_j \frac{C^2|\beta_j|^2}{\lambda_j^2} = \Omega\!\left(\frac{1}{\kappa^{2}}\right) . \]

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

\[ O\!\left(\frac{\log N \cdot s^{2}\,\kappa^{2}}{\epsilon}\right) \]
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:

\[ O\big(s\kappa\,\mathrm{polylog}(N s\kappa/\epsilon)\big) . \]

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\).

\[ |b\rangle = \tfrac{1}{\sqrt2}|0\rangle + \tfrac{1}{\sqrt2}|1\rangle, \qquad \beta_1 = \beta_2 = \tfrac{1}{\sqrt2} \]

Step 1 — QPE writes the eigenvalues into the clock register:

\[ \tfrac{1}{\sqrt2}|0\rangle|1\rangle + \tfrac{1}{\sqrt2}|1\rangle|2\rangle \]

Step 2 — controlled rotation with \(C = 1\) (safe since \(\lambda_{\min}=1\)):

\[ \tfrac{1}{\sqrt2}|0\rangle|1\rangle\big(0\cdot|0\rangle + 1\cdot|1\rangle\big) + \tfrac{1}{\sqrt2}|1\rangle|2\rangle\left(\tfrac{\sqrt3}{2}|0\rangle + \tfrac12|1\rangle\right) \]

(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

\[ \tfrac{1}{\sqrt2}\cdot 1\cdot|0\rangle + \tfrac{1}{\sqrt2}\cdot\tfrac12\cdot|1\rangle = \tfrac{1}{\sqrt2}|0\rangle + \tfrac{1}{2\sqrt2}|1\rangle \]

Norm\(^2 = \frac12 + \frac18 = \frac58\). Normalising:

\[ |x\rangle = \frac{1}{\sqrt{5/8}}\left(\tfrac{1}{\sqrt2}|0\rangle + \tfrac{1}{2\sqrt2}|1\rangle\right) = \frac{2}{\sqrt5}|0\rangle + \frac{1}{\sqrt5}|1\rangle \]

Verify against the classical solution.

\[ \vec x = A^{-1}\vec b = \begin{pmatrix}1&0\\0&\tfrac12\end{pmatrix} \tfrac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix} = \tfrac{1}{\sqrt2}\begin{pmatrix}1\\ \tfrac12\end{pmatrix} \]

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.

\[ \kappa_1 = \frac{2}{1} = \mathbf{2} \]

\(A_2\): symmetric with eigenvalues \(1\pm0.99\), i.e. \(1.99\) and \(0.01\).

\[ \kappa_2 = \frac{1.99}{0.01} = \mathbf{199} \]

Runtime ratio (using the \(O(\kappa^2)\) scaling of original HHL):

\[ \frac{\kappa_2^2}{\kappa_1^2} = \frac{199^2}{2^2} = \frac{39601}{4} \approx \mathbf{9900\times} \]

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\).

\[ \langle x|M|x\rangle = \left|\frac{2}{\sqrt5}\right|^2 = \frac{4}{5} = \mathbf{0.8} \]

Sampling cost. Measure in the computational basis and count zeros. This is a Bernoulli estimate with \(p = 0.8\):

\[ \mathrm{SE} = \sqrt{\frac{p(1-p)}{N_{\text{shots}}}} = \sqrt{\frac{0.16}{N_{\text{shots}}}} \]

Require relative accuracy 1 %, i.e. absolute accuracy \(0.008\):

\[ \sqrt{\frac{0.16}{N_{\text{shots}}}} \le 0.008 \ \Longrightarrow\ N_{\text{shots}} \ge \frac{0.16}{6.4\times10^{-5}} = \mathbf{2500} \]

Add post-selection overhead. Each useful shot requires the ancilla to read 1, which happens with probability \(0.625\):

\[ \text{Total circuit runs} = \frac{2500}{0.625} = \mathbf{4000} . \]

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

\[ \underbrace{\big(X^TX\big)}_{A}\ \vec\beta = \underbrace{X^T\vec y}_{\vec b} . \]

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.

\[ \text{Classical: } O(Md^2 + d^3) \qquad\qquad \text{HHL: } O\!\left(\frac{\log d\cdot s^2\kappa^2}{\epsilon}\right) \]

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

  1. 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\)]
  2. Compute \(\kappa\) for \(\begin{pmatrix}2&1\\1&2\end{pmatrix}\). [Ans: 3]
  3. Why must the clock register be uncomputed?
  4. List Aaronson's four caveats and give one example where each is violated.
  5. Explain why \(\kappa(X^TX) = \kappa(X)^2\).
  6. Show that a dilation \(\tilde A\) handles non-Hermitian \(A\); write the corresponding \(\tilde b\).
  7. 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.