Lesson 31: Quantum Linear Regression¶
31.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Derive the normal equations for ordinary least squares and state their complexity.
- Map linear regression onto HHL and identify each assumption.
- Describe the variational alternative and compare the two routes.
- Explain the role of ridge regularisation in controlling the condition number.
- Distinguish what can and cannot be extracted from the quantum solution.
31.2 Classical Least Squares¶
The problem¶
Given design matrix \(X\in\mathbb{R}^{M\times d}\) (\(M\) samples, \(d\) features) and targets \(\vec y\in\mathbb{R}^{M}\), find \(\vec\beta\) minimising
The normal equations¶
Set the gradient to zero:
The matrix \(A = X^TX\) is \(d\times d\), symmetric and positive semi-definite — exactly the form HHL requires, with no Hermitian dilation needed.
Ridge regression¶
Two roles for \(\lambda\):
- Statistical: shrinks coefficients, reducing variance and handling multicollinearity.
- Numerical: raises \(\lambda_{\min}\) from possibly 0 to at least \(\lambda\), so
For the quantum algorithm the second role is decisive. HHL's runtime scales with \(\kappa\), and without regularisation \(\kappa(X^TX) = \kappa(X)^2\) can be enormous. Ridge regularisation is not optional in quantum linear regression — it is what makes it run at all.
Classical complexity¶
| Method | Cost |
|---|---|
| Normal equations (direct) | \(O(Md^2 + d^3)\) |
| QR / SVD | \(O(Md^2)\), numerically stabler |
| Conjugate gradient | \(O(Md\sqrt\kappa)\) per solve |
| Stochastic gradient descent | \(O(Md)\) per epoch |
31.3 Route 1 — HHL-Based Quantum Linear Regression¶
The pipeline¶
1. Prepare |b> proportional to X^T y (state preparation)
2. Apply HHL with A = X^T X + lambda I (QPE + rotation + post-select)
3. Obtain |beta> proportional to A^{-1} |b>
4. Extract a SCALAR functional (never all d coefficients)
Complexity¶
versus the classical \(O(Md^2 + d^3)\) — exponentially better in \(d\), under the L24 caveats.
What can be extracted¶
| Quantity | Method | Cost | Speed-up? |
|---|---|---|---|
| Prediction \(\hat y_{\text{new}} = \vec x_{\text{new}}^{T}\vec\beta\) | swap test between \(\lvert\beta\rangle\) and \(\lvert x_{\text{new}}\rangle\) | \(O(1/\epsilon^2)\) shots | yes |
| \(\lVert\vec\beta\rVert\) | from the post-selection probability | \(O(1/\epsilon^2)\) | yes |
| Coefficient of determination \(R^2\) | scalar functional | \(O(1/\epsilon^2)\) | yes |
| Which feature is largest | measure and take the mode | \(O(d)\) shots | no |
| All \(d\) coefficients | full tomography | \(O(d/\epsilon^2)\) | no |
For applications where the coefficients themselves are the deliverable — econometrics, clinical risk factors, regulated credit models — quantum linear regression offers nothing. This is worth stating clearly, because it is often obscured in popular accounts.
The swap-test prediction circuit¶
To compute \(\hat y = \langle x_{\text{new}}|\beta\rangle\):
|0> --[H]-----*-----[H]--[M]
|
|beta> ----------x----------
|
|x_new> ----------x----------
(The sign requires a Hadamard test with an extra controlled phase, since the swap test returns only the squared magnitude.)
31.4 Route 2 — Variational Quantum Linear Regression¶
For NISQ hardware, HHL is far too deep (it needs QPE). The variational alternative:
Formulation¶
Parameterise the solution as a quantum state \(|\beta(\vec\theta)\rangle = V(\vec\theta)|0\rangle\) and minimise
Each term is an expectation value measurable by a Hadamard test. This is the Variational Quantum Linear Solver (VQLS) of Bravo-Prieto et al. (2019).
Comparison¶
| HHL route | Variational route | |
|---|---|---|
| Circuit depth | \(O(\kappa/\epsilon)\) — deep (QPE) | \(O(\text{layers})\) — shallow |
| Hardware era | fault-tolerant | NISQ |
| Guarantee | provable complexity | heuristic, no guarantee |
| Barren plateaus | none | yes — a real risk |
| Optimisation | none needed | non-convex |
31.5 A Fully Worked Numerical Example¶
Dataset (4 points, 1 feature + intercept).
| \(i\) | \(x_i\) | \(y_i\) |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 2 | 3 |
| 3 | 3 | 5 |
| 4 | 4 | 6 |
Design matrix (with an intercept column):
Compute \(A = X^TX\).
(top-left: \(4\) ones; top-right and bottom-left: \(1+2+3+4=10\); bottom-right: \(1+4+9+16=30\).)
Compute \(\vec b = X^{T}\vec y\).
Solve. \(\det A = 4(30) - 100 = 20\).
Check. Predictions: \(1.9, 3.3, 4.7, 6.1\) against \(2,3,5,6\). Residuals \(0.1, -0.3, 0.3, -0.1\); sum \(= 0\) ✓ (a property of the least-squares fit with an intercept).
Condition number. Eigenvalues of \(A\): from \(\lambda^2 - 34\lambda + 20 = 0\),
Quite ill-conditioned for a 2×2 problem — because the intercept column and the \(x\) column are strongly correlated (the \(x\) values are not centred). Centring \(x\) would make \(A\) diagonal and \(\kappa\) far smaller — an important practical preprocessing step for the quantum algorithm.
31.6 Solved Problems¶
Problem 1 — Effect of centring on the condition number¶
Re-do the example above with \(x\) centred (\(\tilde x_i = x_i - \bar x\)). Compute the new \(A\), \(\kappa\), and the coefficients.
Solution.
\(\bar x = 2.5\), so \(\tilde x = (-1.5, -0.5, 0.5, 1.5)\).
Diagonal! Centring removed the correlation between the intercept and slope columns.
Compare \(\kappa = 55.8\) uncentred — a 45× reduction.
So \(\hat y = 4 + 1.4\tilde x = 4 + 1.4(x - 2.5) = 0.5 + 1.4x\) ✓ — the same fitted line, as it must be.
Impact on HHL runtime. Original HHL scales as \(\kappa^2\):
Problem 2 — Ridge regression and the condition number¶
A design matrix gives \(A = X^TX\) with eigenvalues \(\{100, 10, 0.01\}\). Compute \(\kappa\), then compute it after ridge regularisation with \(\lambda = 0.1\) and \(\lambda = 1\). Discuss the bias–variance trade-off.
Solution.
Unregularised.
Catastrophic: HHL would need \(\kappa^2 = 10^{8}\) times the base cost.
With \(\lambda = 0.1\). Eigenvalues become \(\{100.1, 10.1, 0.11\}\):
An 11× reduction in \(\kappa\), so a \(121\times\) reduction in HHL runtime.
With \(\lambda = 1\). Eigenvalues \(\{101, 11, 1.01\}\):
A 100× reduction in \(\kappa\), i.e. \(10^{4}\times\) in runtime.
Trade-off.
| \(\lambda\) | \(\kappa\) | HHL cost (rel.) | Statistical bias |
|---|---|---|---|
| 0 | 10 000 | \(1\) | none (unbiased) |
| 0.1 | 910 | \(1.2\times10^{-2}\) | small |
| 1 | 100 | \(10^{-4}\) | moderate |
| 10 | ~10 | \(10^{-6}\) | large — underfits |
The classical view: choose \(\lambda\) by cross-validation to minimise test error, balancing bias against variance.
The quantum view adds a third term: runtime. The optimal \(\lambda\) for a quantum implementation is larger than the statistically optimal one, because the runtime benefit is quadratic in \(1/\kappa\) while the statistical cost grows only gradually. A principled choice minimises
for a cost weight \(\gamma\) reflecting the price of quantum runtime.
This is a genuine and under-appreciated design insight: quantum algorithms change which hyperparameters are optimal.**
Problem 3 — Prediction via swap test, with shot budget¶
After quantum linear regression, \(|\beta\rangle = \frac{1}{\sqrt{1.25}}(0.5, 1.0)^T\) (normalised) and a new point is encoded as \(|x_{\text{new}}\rangle = \frac{1}{\sqrt2}(1,1)^T\). Compute \(\Pr[0]\) in the swap test and the shots needed for 1 % accuracy in \(\hat y\).
Solution.
Normalise \(|\beta\rangle\). \(\|(0.5,1.0)\| = \sqrt{0.25+1} = \sqrt{1.25} = 1.1180\), so
Overlap.
Swap-test probability.
Shot budget. We measure \(\Pr[0]\) and infer \(F = 2\Pr[0]-1\), so \(\delta F = 2\,\delta\Pr[0]\). We want 1 % relative accuracy in \(\hat y \propto \sqrt F\):
Round up to 1024. Note this is independent of \(d\) — predicting with a 10-feature or a 10 000-feature model costs the same number of shots. That is where the quantum advantage lives.
Problem 4 — When is quantum linear regression worth it?¶
For each case, decide whether the quantum route helps, and justify.
(a) \(d = 10\), \(M = 1000\), need all coefficients. (b) \(d = 10^{6}\) sparse features, need predictions only, data from a quantum simulation. (c) \(d = 100\), \(\kappa = 10^{6}\). (d) \(d = 10^{4}\), dense \(X\), classical data in a CSV file.
Solution.
(a) No. \(d = 10\) is trivially small; classical solution takes microseconds. And needing all coefficients forces \(O(d)\) tomography, destroying any advantage even if \(d\) were large.
(b) Yes — the best case. Four boxes ticked:
- sparse ⟹ Hamiltonian simulation is efficient ✓
- predictions only ⟹ scalar readout via swap test ✓
- quantum-generated data ⟹ no state-preparation bottleneck ✓
- \(d = 10^{6}\) ⟹ classical \(O(d^3) = 10^{18}\) operations is infeasible, while \(\log_2 10^6 = 20\) qubits suffice ✓
(c) No. \(\kappa = 10^{6}\) makes HHL cost \(\kappa^2 = 10^{12}\) times the base — worse than classical, which is trivial at \(d = 100\) anyway. Fix first: centre, standardise, and apply ridge regularisation; if \(\kappa\) can be brought below \(\sim10^2\) the question becomes worth revisiting.
(d) No. Two independent killers:
- Dense \(X\) ⟹ \(s = d = 10^4\), and the \(s^2\) factor gives \(10^{8}\) — Hamiltonian simulation is not efficient.
- Data in a CSV ⟹ loading \(10^{4}\) values into amplitudes costs \(O(10^{4})\) gates, which already matches the classical read cost.
The checklist for HHL-based regression.
All four are required. Miss any one and the advantage disappears.
Problem 5 — Variational quantum linear regression by hand¶
Solve \(A\vec\beta = \vec b\) with \(A = \begin{pmatrix}2&0\\0&1\end{pmatrix}\), \(|b\rangle = \frac{1}{\sqrt2}(1,1)^T\) using the VQLS cost with the single-parameter ansatz \(|\beta(\theta)\rangle = R_y(\theta)|0\rangle\). Find the optimal \(\theta\).
Solution.
Ansatz. \(|\beta(\theta)\rangle = \big(\cos\frac\theta2,\ \sin\frac\theta2\big)^{T}\).
Apply \(A\).
Cost function. VQLS uses the normalised overlap (so the solution is found up to scale):
Numerator.
Denominator.
Write \(c = \cos\frac\theta2\), \(s = \sin\frac\theta2\):
Minimise. Equivalently maximise \(g = \frac{(2c+s)^2}{4c^2+s^2}\). By Cauchy–Schwarz, writing \(\vec u = (2c, s)\) and \(\vec v = (1,1)\):
with equality iff \(\vec u \parallel \vec v\), i.e. \(2c = s\):
At the optimum \(g = 2\), so \(C = 1 - \frac12\cdot2 = \mathbf{0}\) — the ansatz represents the exact solution.
Verify against the exact solution.
Normalised: \(\frac{1}{\sqrt5}(1,2)^T = (0.4472, 0.8944)^T\).
From the ansatz at \(\theta^{*}\): \(\cos(1.10715) = 0.4472\), \(\sin(1.10715) = 0.8944\) ✓
Perfect agreement. The variational method found the exact solution because the single-parameter \(R_y\) ansatz happens to cover all real 2-D states — for larger systems the ansatz is only an approximation, and this is precisely where barren plateaus and expressivity limits bite.
31.7 Practice Problems¶
- Fit \(\hat y = \beta_0 + \beta_1 x\) to \((1,3),(2,5),(3,7)\). [Ans: \(\beta_0=1,\beta_1=2\), exact fit]
- Compute \(\kappa\) for \(X^TX = \begin{pmatrix}4&2\\2&4\end{pmatrix}\). [Ans: 3]
- Ridge with \(\lambda=2\) on eigenvalues \(\{50,5,0.5\}\): new \(\kappa\)? [Ans: \(52/2.5 = 20.8\)]
- Swap test gives \(\Pr[0]=0.8\): what is \(|\langle x|\beta\rangle|^2\)? [Ans: 0.6]
- Why does centring features reduce the condition number?
- Shots for 2 % accuracy in \(\hat y\) when \(p = 0.9\)? [Ans: ≈ 141]
- Give the four conditions required for HHL regression to help.
31.8 Summary¶
- OLS: \(\vec\beta = (X^TX)^{-1}X^T\vec y\); \(A = X^TX\) is symmetric PSD — HHL-ready without dilation.
- Ridge regularisation raises \(\lambda_{\min}\), cutting \(\kappa\); for the quantum algorithm this is essential, not merely statistical.
- HHL route: \(O(\log d\cdot s^2\kappa^2/\epsilon)\) versus classical \(O(Md^2+d^3)\) — exponential in \(d\), but only under all four L24 caveats.
- Quantum linear regression accelerates prediction, not interpretation. Predictions cost \(O(1/\epsilon^2)\) shots independent of \(d\); extracting all \(d\) coefficients costs \(O(d)\) and kills the advantage.
- Variational route (VQLS) trades provable guarantees for NISQ-compatible shallow circuits, inheriting barren plateaus and non-convexity.
- Preprocessing pays off enormously: centring features made \(\kappa\) fall from 55.8 to 1.25 in the worked example — a \(\sim2000\times\) HHL speed-up for free.
- Checklist: sparse \(A\) ∧ small \(\kappa\) ∧ quantum-native input ∧ scalar output. All four, or no advantage.
Next lesson: L32 — Quantum k-means clustering and the swap test.
Practise now: unit3-qml-lab.html → Regression Lab: enter data points, see \(X^TX\), its
eigenvalues and \(\kappa\), watch centring and ridge change \(\kappa\) live, and compare the classical
and HHL-simulated solutions.