Skip to content

Lesson 31: Quantum Linear Regression

31.1 Learning Outcomes

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

  1. Derive the normal equations for ordinary least squares and state their complexity.
  2. Map linear regression onto HHL and identify each assumption.
  3. Describe the variational alternative and compare the two routes.
  4. Explain the role of ridge regularisation in controlling the condition number.
  5. 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

\[ L(\vec\beta) = \|X\vec\beta - \vec y\|^{2} . \]

The normal equations

Set the gradient to zero:

\[ \nabla_{\vec\beta}L = 2X^{T}\big(X\vec\beta - \vec y\big) = 0 \]
\[ \boxed{\ X^{T}X\,\vec\beta = X^{T}\vec y \qquad\Longrightarrow\qquad \vec\beta = \big(X^{T}X\big)^{-1}X^{T}\vec y\ } \]

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

\[ L_{\text{ridge}}(\vec\beta) = \|X\vec\beta - \vec y\|^{2} + \lambda\|\vec\beta\|^{2} \qquad\Longrightarrow\qquad \vec\beta = \big(X^{T}X + \lambda I\big)^{-1}X^{T}\vec y \]

Two roles for \(\lambda\):

  1. Statistical: shrinks coefficients, reducing variance and handling multicollinearity.
  2. Numerical: raises \(\lambda_{\min}\) from possibly 0 to at least \(\lambda\), so
\[ \kappa\big(X^TX+\lambda I\big) = \frac{\lambda_{\max}+\lambda}{\lambda_{\min}+\lambda} \ \le\ \frac{\lambda_{\max}+\lambda}{\lambda} . \]

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

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

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
\[ \boxed{\ \textbf{Quantum linear regression accelerates prediction, not interpretation.}\ } \]

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----------
\[ \Pr[0] = \frac{1 + |\langle x_{\text{new}}|\beta\rangle|^{2}}{2} \qquad\Longrightarrow\qquad |\hat y|^{2} \propto 2\Pr[0]-1 \]

(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

\[ C(\vec\theta) = \big\| A|\beta(\vec\theta)\rangle - |b\rangle \big\|^{2} = \langle\beta|A^{\dagger}A|\beta\rangle - 2\,\mathrm{Re}\langle b|A|\beta\rangle + \langle b|b\rangle \]

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

\[ X = \begin{pmatrix}1&1\\1&2\\1&3\\1&4\end{pmatrix}, \qquad \vec y = \begin{pmatrix}2\\3\\5\\6\end{pmatrix} \]

Compute \(A = X^TX\).

\[ X^{T}X = \begin{pmatrix}4 & 10\\ 10 & 30\end{pmatrix} \]

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

\[ X^{T}\vec y = \begin{pmatrix}2+3+5+6\\ 1(2)+2(3)+3(5)+4(6)\end{pmatrix} = \begin{pmatrix}16\\ 2+6+15+24\end{pmatrix} = \begin{pmatrix}16\\47\end{pmatrix} \]

Solve. \(\det A = 4(30) - 100 = 20\).

\[ A^{-1} = \frac{1}{20}\begin{pmatrix}30 & -10\\ -10 & 4\end{pmatrix} \]
\[ \vec\beta = \frac{1}{20}\begin{pmatrix}30 & -10\\-10 & 4\end{pmatrix}\begin{pmatrix}16\\47\end{pmatrix} = \frac{1}{20}\begin{pmatrix}480 - 470\\ -160 + 188\end{pmatrix} = \frac{1}{20}\begin{pmatrix}10\\28\end{pmatrix} \]
\[ \boxed{\ \vec\beta = \begin{pmatrix}0.5\\ 1.4\end{pmatrix} \qquad\Longrightarrow\qquad \hat y = 0.5 + 1.4x\ } \]

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

\[ \mathrm{RSS} = 0.01+0.09+0.09+0.01 = 0.20 \]

Condition number. Eigenvalues of \(A\): from \(\lambda^2 - 34\lambda + 20 = 0\),

\[ \lambda = \frac{34\pm\sqrt{1156-80}}{2} = \frac{34\pm32.80}{2} = 33.40,\ 0.599 \]
\[ \kappa = \frac{33.40}{0.599} = \mathbf{55.8} \]

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

\[ X^{T}X = \begin{pmatrix}4 & 0\\ 0 & \sum\tilde x_i^2\end{pmatrix} = \begin{pmatrix}4 & 0\\0 & 2.25+0.25+0.25+2.25\end{pmatrix} = \begin{pmatrix}4&0\\0&5\end{pmatrix} \]

Diagonal! Centring removed the correlation between the intercept and slope columns.

\[ \kappa = \frac{5}{4} = \mathbf{1.25} \]

Compare \(\kappa = 55.8\) uncentred — a 45× reduction.

\[ X^{T}\vec y = \begin{pmatrix}16\\ -1.5(2)-0.5(3)+0.5(5)+1.5(6)\end{pmatrix} = \begin{pmatrix}16\\ -3-1.5+2.5+9\end{pmatrix} = \begin{pmatrix}16\\7\end{pmatrix} \]
\[ \vec\beta = \begin{pmatrix}16/4\\ 7/5\end{pmatrix} = \begin{pmatrix}4\\1.4\end{pmatrix} \]

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

\[ \frac{55.8^{2}}{1.25^{2}} = \frac{3114}{1.5625} \approx \mathbf{1993\times \text{speed-up}} \]
\[ \boxed{\ \textbf{Centre and standardise your features. It is free classically and worth } \sim2000\times \textbf{ quantumly.}\ } \]

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.

\[ \kappa = \frac{100}{0.01} = \mathbf{10{,}000} \]

Catastrophic: HHL would need \(\kappa^2 = 10^{8}\) times the base cost.

With \(\lambda = 0.1\). Eigenvalues become \(\{100.1, 10.1, 0.11\}\):

\[ \kappa = \frac{100.1}{0.11} = \mathbf{910} \]

An 11× reduction in \(\kappa\), so a \(121\times\) reduction in HHL runtime.

With \(\lambda = 1\). Eigenvalues \(\{101, 11, 1.01\}\):

\[ \kappa = \frac{101}{1.01} = \mathbf{100} \]

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

\[ \text{test error}(\lambda) + \gamma\cdot\kappa(\lambda)^{2} \]

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

\[ |\beta\rangle = (0.4472,\ 0.8944)^{T} \]

Overlap.

\[ \langle x_{\text{new}}|\beta\rangle = \frac{1}{\sqrt2}(0.4472 + 0.8944) = \frac{1.3416}{1.4142} = 0.94868 \]
\[ |\langle x_{\text{new}}|\beta\rangle|^{2} = 0.9 \]

Swap-test probability.

\[ \Pr[0] = \frac{1 + 0.9}{2} = \mathbf{0.95} \]

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

\[ \frac{\delta \hat y}{\hat y} = \frac{1}{2}\frac{\delta F}{F} \le 0.01 \ \Longrightarrow\ \delta F \le 0.02 F = 0.018 \ \Longrightarrow\ \delta\Pr[0] \le 0.009 \]
\[ \sqrt{\frac{p(1-p)}{S}} \le 0.009, \quad p = 0.95 \]
\[ S \ge \frac{0.95\times0.05}{0.009^{2}} = \frac{0.0475}{8.1\times10^{-5}} = \mathbf{587\ \text{shots}} \]

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.

\[ \text{sparse } A \ \wedge\ \text{small } \kappa \ \wedge\ \text{quantum-native or structured input} \ \wedge\ \text{scalar output} \]

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

\[ A|\beta(\theta)\rangle = \begin{pmatrix}2\cos\frac\theta2\\ \sin\frac\theta2\end{pmatrix} \]

Cost function. VQLS uses the normalised overlap (so the solution is found up to scale):

\[ C(\theta) = 1 - \frac{\big|\langle b|A|\beta(\theta)\rangle\big|^{2}}{\big\|A|\beta(\theta)\rangle\big\|^{2}} \]

Numerator.

\[ \langle b|A|\beta\rangle = \frac{1}{\sqrt2}\left(2\cos\tfrac\theta2 + \sin\tfrac\theta2\right) \]

Denominator.

\[ \big\|A|\beta\rangle\big\|^{2} = 4\cos^{2}\tfrac\theta2 + \sin^{2}\tfrac\theta2 \]

Write \(c = \cos\frac\theta2\), \(s = \sin\frac\theta2\):

\[ C(\theta) = 1 - \frac{\frac12(2c+s)^{2}}{4c^{2}+s^{2}} \]

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

\[ (2c+s)^{2} = (\vec u\cdot\vec v)^{2} \le \|\vec u\|^{2}\|\vec v\|^{2} = (4c^2+s^2)\cdot 2 \]

with equality iff \(\vec u \parallel \vec v\), i.e. \(2c = s\):

\[ \tan\frac{\theta}{2} = 2 \ \Longrightarrow\ \frac{\theta}{2} = \arctan 2 = 1.10715 \ \Longrightarrow\ \boxed{\theta^{*} = 2.2143\ \text{rad} = 126.87°} \]

At the optimum \(g = 2\), so \(C = 1 - \frac12\cdot2 = \mathbf{0}\) — the ansatz represents the exact solution.

Verify against the exact solution.

\[ \vec\beta_{\text{exact}} = A^{-1}\vec b = \frac{1}{\sqrt2}\begin{pmatrix}0.5\\1\end{pmatrix} \ \propto\ \begin{pmatrix}1\\2\end{pmatrix} \]

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

  1. Fit \(\hat y = \beta_0 + \beta_1 x\) to \((1,3),(2,5),(3,7)\). [Ans: \(\beta_0=1,\beta_1=2\), exact fit]
  2. Compute \(\kappa\) for \(X^TX = \begin{pmatrix}4&2\\2&4\end{pmatrix}\). [Ans: 3]
  3. Ridge with \(\lambda=2\) on eigenvalues \(\{50,5,0.5\}\): new \(\kappa\)? [Ans: \(52/2.5 = 20.8\)]
  4. Swap test gives \(\Pr[0]=0.8\): what is \(|\langle x|\beta\rangle|^2\)? [Ans: 0.6]
  5. Why does centring features reduce the condition number?
  6. Shots for 2 % accuracy in \(\hat y\) when \(p = 0.9\)? [Ans: ≈ 141]
  7. 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.