Simple Algorithm
Quantum Computing · Excited State · 22 min

Quantum Machine Learning & Optimization

Promise, hype, and the theorems in between.

In 2009 Harrow, Hassidim and Lloyd showed that a quantum computer can solve certain linear systems exponentially faster than any known classical method, and quantum machine learning took off. In 2018 an undergraduate, Ewin Tang, showed that one of its flagship exponential speedups vanishes once a classical algorithm gets the same access to the data. The truth about QML lives in the fine print, and this lesson reads it.

What you’ll learn

  • Explain the data-loading and readout bottlenecks and why they can erase claimed speedups.
  • Define quantum feature maps and fidelity kernels, and estimate a kernel entry by sampling.
  • Trace the HHL algorithm, state its runtime, and list the conditions under which its speedup survives.
  • Quantify why Grover-type speedups for optimization are only quadratic, and why overheads can erase them.
  • Separate provable advantages from heuristic claims.

The input and output problem

Quantum machine learning (QML) comes in flavors: classical data processed by a quantum algorithm (the most common hope), quantum data such as states from a sensor or a quantum simulation, and "quantum-inspired" classical algorithms. Most claimed exponential speedups for classical data rely on amplitude encoding: a vector x∈RN\mathbf x\in\R^N with N=2nN=2^n is stored in only nn qubits as

∣x⟩=1∥x∥∑i=0N−1xi∣i⟩.\ket{\mathbf x}=\frac{1}{\norm{\mathbf x}}\sum_{i=0}^{N-1}x_i\ket i.

Two facts follow from what you just did.

  • Loading is expensive. Preparing an arbitrary nn-qubit state takes on the order of 2n=N2^n=N gates, the same order of work as reading the data classically. Quantum random access memory (QRAM) proposals answer a query in O(log⁡N)\order{\log N} depth, but need O(N)\order{N} hardware components with very low error rates, and no large QRAM exists.
  • Reading out is expensive. The answer is also a state. A measurement returns one index ii with probability ∣xi∣2\abs{x_i}^2; estimating all NN amplitudes needs at least on the order of NN repetitions.

Quantum kernels and variational classifiers

A feature map embeds a data point into a state, x↦∣ϕ(x)⟩=U(x)∣0n⟩\mathbf x\mapsto\ket{\phi(\mathbf x)}=U(\mathbf x)\ket{0^n}. Two learning models use it.

  • Kernel methods. The quantum computer estimates the fidelity kernel k(x,x′)=∣⟨ϕ(x)∣ϕ(x′)⟩∣2k(\mathbf x,\mathbf x')=\abs{\braket{\phi(\mathbf x)|\phi(\mathbf x')}}^2 for all pairs of training points, and a classical support vector machine does the rest (Havlíček et al. 2019; Schuld & Killoran 2019).
  • Variational classifiers. A trainable circuit V(θ)V(\boldsymbol\theta) follows the embedding; the prediction is fθ(x)=⟨ϕ(x)|V(θ)†MV(θ)|ϕ(x)⟩f_{\boldsymbol\theta}(\mathbf x)=\mel{\phi(\mathbf x)}{V(\boldsymbol\theta)^\dagger MV(\boldsymbol\theta)}{\phi(\mathbf x)} for an observable MM, trained by gradient descent.
DerivationEstimating a kernel entry
  1. P(0n)=∣⟨0n|U(x′)†U(x)|0n⟩∣2=∣⟨ϕ(x′)∣ϕ(x)⟩∣2=k(x,x′)P(0^n)=\abs{\mel{0^n}{U(\mathbf x')^\dagger U(\mathbf x)}{0^n}}^2=\abs{\braket{\phi(\mathbf x')|\phi(\mathbf x)}}^2=k(\mathbf x,\mathbf x')

    Run U(x)U(\mathbf x), then U(x′)†U(\mathbf x')^\dagger ("compute–uncompute") and measure: the probability of all zeros is the kernel.

  2. k^=#{0n}S,Var⁡k^=k(1−k)S≤14S\hat k=\frac{\#\{0^n\}}{S},\qquad\operatorname{Var}\hat k=\frac{k(1-k)}{S}\le\frac{1}{4S}

    With SS shots the estimate is a binomial frequency.

  3. cost≈m22 S circuit runs for m training points\text{cost}\approx\tfrac{m^2}{2}\,S\ \text{circuit runs for } m \text{ training points}

    Every pair needs its own estimate: the Gram matrix is m×mm\times m.

  4. f(x)=Tr⁡[ρ(x) Mθ],ρ(x)=∣ϕ(x)⟩ ⁣⟨ϕ(x)∣f(\mathbf x)=\Tr\big[\rho(\mathbf x)\,M_{\boldsymbol\theta}\big],\qquad\rho(\mathbf x)=\dyad{\phi(\mathbf x)}

    A variational classifier is a linear model in the feature space of density matrices, the same space the kernel lives in. Minimizing a regularized loss over all observables yields a kernel expansion ∑iαik(xi,x)\sum_i\alpha_ik(\mathbf x_i,\mathbf x) (representer theorem; Schuld 2021).

Predict before you look

A kernel entry is near k=0.5k=0.5. About how many shots give a standard error of 0.010.01?

Show the answer

2500 shots

k(1−k)/S=0.5/S=0.01\sqrt{k(1-k)/S}=0.5/\sqrt S=0.01 gives S=2500S=2500. For m=1000m=1000 training points that is about 5×1055\times10^5 entries, so over 10910^9 circuit runs for one Gram matrix.

HHL: an exponential speedup with fine print

The flagship quantum linear-algebra algorithm solves Ax=bA\mathbf x=\mathbf b in a quantum sense: given ∣b⟩\ket{\mathbf b} and access to a sparse Hermitian N×NN\times N matrix AA with condition number κ=∥A∥ ∥A−1∥\kappa=\norm A\,\norm{A^{-1}}, prepare the state ∣x⟩∝A−1∣b⟩\ket{\mathbf x}\propto A^{-1}\ket{\mathbf b}.

DerivationHHL in four moves
  1. ∣b⟩=∑jβj∣uj⟩,A∣uj⟩=λj∣uj⟩\ket{\mathbf b}=\sum_j\beta_j\ket{u_j},\qquad A\ket{u_j}=\lambda_j\ket{u_j}

    Expand the input in the eigenbasis of AA (rescaled so that ∥A∥≤1\norm A\le1). You never compute this expansion; the algorithm acts on it linearly.

  2. → QPE with eiAt  ∑jβj∣uj⟩∣λ~j⟩\xrightarrow{\ \text{QPE with }e^{iAt}\ }\ \sum_j\beta_j\ket{u_j}\ket{\tilde\lambda_j}

    Phase estimation writes an estimate of each eigenvalue into a register.

  3. → rotate  ∑jβj∣uj⟩∣λ~j⟩(1−C2λ~j2 ∣0⟩+Cλ~j∣1⟩)\xrightarrow{\ \text{rotate}\ }\ \sum_j\beta_j\ket{u_j}\ket{\tilde\lambda_j}\Big(\sqrt{1-\tfrac{C^2}{\tilde\lambda_j^2}}\,\ket0+\tfrac{C}{\tilde\lambda_j}\ket1\Big)

    An ancilla rotation controlled by the eigenvalue register, with C≤min⁡j∣λj∣C\le\min_j\abs{\lambda_j}.

  4. → QPE−1, keep ancilla=1  ∑jβjλj−1∣uj⟩∥⋯∥=A−1∣b⟩∥A−1∣b⟩∥\xrightarrow{\ \text{QPE}^{-1},\ \text{keep ancilla}=1\ }\ \frac{\sum_j\beta_j\lambda_j^{-1}\ket{u_j}}{\norm{\cdots}}=\frac{A^{-1}\ket{\mathbf b}}{\norm{A^{-1}\ket{\mathbf b}}}

    Uncompute the eigenvalue register and keep the runs where the ancilla reads 1. With C=1/κC=1/\kappa the success probability is ∑j∣βj∣2C2/λj2≥1/κ2\sum_j\abs{\beta_j}^2C^2/\lambda_j^2\ge1/\kappa^2, so amplitude amplification needs O(κ)\order{\kappa} rounds.

Fine printWhat the exponential speedup needsIf it fails
Input∣b⟩\ket{\mathbf b} prepared in poly⁡log⁡N\poly\log N time (a formula, or a QRAM)generic loading costs about NN
Matrix accessAA sparse (or efficiently block-encoded) with computable entriessimulating eiAte^{iAt} becomes expensive
Conditioningκ=poly⁡log⁡N\kappa=\poly\log Nthe κ2\kappa^2 factor dominates
Outputa few expectation values ⟨x|M|x⟩\mel{\mathbf x}{M}{\mathbf x} or samples, not x\mathbf x itselffull readout costs at least about NN runs
Fair comparisonclassical algorithms given equivalent data accesslow-rank problems were dequantized (Tang)
Aaronson's caveats, plus the one Tang made famous. Each is a place where the exponential can leak away.
Check your understanding

HHL has finished. What do you actually hold?

  1. The solution vector x\mathbf x, written in a classical register
  2. A quantum state proportional to A−1∣b⟩A^{-1}\ket{\mathbf b}, from which you can estimate quantities like ⟨x|M|x⟩\mel{\mathbf x}{M}{\mathbf x}
  3. The list of eigenvalues of AA
  4. A certificate that Ax=bA\mathbf x=\mathbf b has a unique solution
Show the answer

B. A quantum state proportional to A−1∣b⟩A^{-1}\ket{\mathbf b}, from which you can estimate quantities like ⟨x|M|x⟩\mel{\mathbf x}{M}{\mathbf x}

The output is a normalized state ∣x⟩\ket{\mathbf x}. Measurements give samples and expectation values; extracting all NN entries would cost at least about NN repetitions and erase the speedup.

Optimization: quadratic, not exponential

Many hoped-for applications are optimization: scheduling, portfolios, routing, training models. Most such problems are NP-hard in the worst case, and quantum computers are not believed to solve NP-complete problems efficiently. What they provably offer is amplitude amplification: Grover search finds a marked item among NN with O(N)\order{\sqrt N} oracle calls instead of O(N)\order{N}, and the BBBV lower bound shows nothing faster exists for unstructured search.

Predict before you look

A classical computer checks 10910^9 candidates per second by brute force. An error-corrected quantum computer runs 10310^3 Grover oracle calls per second, needing π4N\tfrac\pi4\sqrt N calls. Above roughly what problem size n=log⁡2Nn=\log_2N does Grover win?

Show the answer

39

Break-even when N/109=π4N/103N/10^9=\tfrac\pi4\sqrt N/10^3, i.e. N=π4×106≈7.9×105\sqrt N=\tfrac\pi4\times10^6\approx7.9\times10^5, so n≈39n\approx39. Below that the classical machine is faster despite doing quadratically more work.

DerivationClock speed versus square roots
  1. Tcl=NRcl,Tq=π4 NRqT_{\text{cl}}=\frac{N}{R_{\text{cl}}},\qquad T_{\text{q}}=\frac{\pi}{4}\,\frac{\sqrt N}{R_{\text{q}}}

    Brute force at RclR_{\text{cl}} checks per second; Grover at RqR_{\text{q}} error-corrected oracle calls per second.

  2. N=260:Tcl≈37 years,Tq≈10 daysN=2^{60}:\qquad T_{\text{cl}}\approx37\ \text{years},\qquad T_{\text{q}}\approx10\ \text{days}

    Beyond break-even, the quadratic speedup does pay off, in principle.

  3. 106 classical cores:Tcl≈20 minutes;P quantum machines:Tq∝N/P10^6\ \text{classical cores}:\quad T_{\text{cl}}\approx20\ \text{minutes};\qquad P\ \text{quantum machines}:\quad T_{\text{q}}\propto\sqrt{N/P}

    But brute force parallelizes perfectly, while splitting Grover across PP machines gains only P\sqrt P. Real classical solvers also use heuristics and branch-and-bound that are vastly better than brute force.

Where the advantage is real

ClaimStatus (mid-2020s)
Linear algebra (HHL and successors)Exponential speedups exist: the problem is BQP-complete. End-to-end applications that satisfy all the fine print are rare.
Low-rank QML (recommendation systems, PCA, regression)Dequantized: classical algorithms with sample-and-query access match them up to polynomial factors (Tang 2019 and successors).
Quantum kernels and variational classifiersProvable advantage only for engineered problems (e.g. discrete-logarithm-based, Liu, Arunachalam & Temme 2021); generic embeddings face concentration and strong classical baselines.
Learning from quantum dataProvable exponential reductions in the number of experiments for some tasks (Huang et al. 2022).
OptimizationQuadratic speedups (often erased by overheads); heuristics without general guarantees.
Promise, hype and the theorems in between.
Think first Why are quantum data (states produced by a quantum experiment) a more promising setting than classical data?

The input problem disappears: the data already are quantum states, so nothing must be loaded. A learner with quantum memory can process several copies coherently (for example, measure them jointly), and for some tasks this provably needs exponentially fewer experiments than any strategy that measures each copy separately and stores only classical outcomes.

Key takeaways

  • End-to-end speedups need cheap input (state preparation or QRAM) and cheap output (a few expectation values, not a full vector).
  • Quantum kernels are estimated by sampling ∣⟨ϕ(x)∣ϕ(x′)⟩∣2\abs{\braket{\phi(\mathbf x)|\phi(\mathbf x')}}^2; expressive embeddings concentrate exponentially, and variational classifiers are kernel models in disguise.
  • HHL prepares A−1∣b⟩A^{-1}\ket{\mathbf b} in O~(log⁡(N)s2κ2/ε)\widetilde{\mathcal O}(\log(N)s^2\kappa^2/\varepsilon): exponentially fast in NN only when AA is sparse and well conditioned and the input and output conditions hold.
  • Grover-type speedups for optimization are quadratic; error-correction overheads and classical parallelism push the break-even to very large instances.
  • Provable advantages exist (BQP-complete linear algebra, quantum data, discrete-log-based learning), but many classical-data QML speedups have been dequantized.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why does loading an arbitrary NN-dimensional classical vector into amplitudes threaten claims of exponential speedup?

  1. Amplitudes cannot represent negative numbers
  2. Amplitude encoding needs NN qubits
  3. Measurement destroys the encoded state
  4. Preparing a generic state takes about NN gates (or a QRAM with about NN components), comparable to the classical cost of reading the data
Show the answer

D. Preparing a generic state takes about NN gates (or a QRAM with about NN components), comparable to the classical cost of reading the data

The quantum algorithm may be poly⁡log⁡N\poly\log N after the state exists, but preparing it generically costs Θ(N)\Theta(N), which already matches a classical pass over the data.

Question 2

In which situation can HHL's exponential speedup survive end to end?

  1. A dense matrix with κ≈N\kappa\approx N, where you need every entry of x\mathbf x
  2. A sparse, well-conditioned AA (κ=poly⁡log⁡N\kappa=\poly\log N), a ∣b⟩\ket{\mathbf b} preparable in poly⁡log⁡N\poly\log N time, and a need for only a few expectation values
  3. Any matrix, provided NN is large enough
  4. A sparse, well-conditioned matrix where you must print every entry of x\mathbf x
Show the answer

B. A sparse, well-conditioned AA (κ=poly⁡log⁡N\kappa=\poly\log N), a ∣b⟩\ket{\mathbf b} preparable in poly⁡log⁡N\poly\log N time, and a need for only a few expectation values

All four conditions must hold: sparse access, small κ\kappa, cheap input, and an output that is a few numbers like ⟨x|M|x⟩\mel{\mathbf x}{M}{\mathbf x}.

Question 3

In the compute–uncompute test, which measured quantity estimates the fidelity kernel k(x,x′)k(\mathbf x,\mathbf x')?

  1. The expectation value of ZZ on the first qubit after U(x)U(\mathbf x)
  2. The average number of qubits measured as 1
  3. The probability of the all-zeros outcome after U(x′)†U(x)U(\mathbf x')^\dagger U(\mathbf x)
  4. The phase of the amplitude of ∣0n⟩\ket{0^n}
Show the answer

C. The probability of the all-zeros outcome after U(x′)†U(x)U(\mathbf x')^\dagger U(\mathbf x)

∣⟨0n|U(x′)†U(x)|0n⟩∣2=∣⟨ϕ(x′)∣ϕ(x)⟩∣2\abs{\mel{0^n}{U(\mathbf x')^\dagger U(\mathbf x)}{0^n}}^2=\abs{\braket{\phi(\mathbf x')|\phi(\mathbf x)}}^2: the all-zeros probability is exactly the squared overlap.

Question 4

For an NP-hard optimization problem whose structure you cannot exploit, what does Grover search offer over classical brute force on 2n2^n candidates?

  1. A quadratic speedup, about 2n/22^{n/2} oracle calls: still exponential
  2. An exponential speedup, giving polynomial time
  3. No speedup at all
  4. A speedup that grows linearly with the number of parallel quantum processors
Show the answer

A. A quadratic speedup, about 2n/22^{n/2} oracle calls: still exponential

Amplitude amplification reduces 2n2^n to about 2n/22^{n/2} oracle calls, which is optimal for unstructured search (BBBV) and still exponential.

Question 5

What did Ewin Tang's 2018 result show about the quantum recommendation-system algorithm of Kerenidis and Prakash?

  1. The quantum algorithm was incorrect
  2. It needs millions of physical qubits
  3. A classical algorithm with sample-and-query access to the same data matches it up to polynomial factors
  4. It works only for sparse matrices
Show the answer

C. A classical algorithm with sample-and-query access to the same data matches it up to polynomial factors

Given the same data structure that the quantum algorithm needs for state preparation, a classical algorithm based on length-squared sampling is only polynomially slower. The exponential speedup came from the input model.

Go deeper

Further reading

  • A. W. Harrow, A. Hassidim & S. Lloyd, "Quantum algorithm for linear systems of equations", Phys. Rev. Lett. 103, 150502 (2009).
  • S. Aaronson, "Read the fine print", Nature Physics 11, 291 (2015).
  • J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe & S. Lloyd, "Quantum machine learning", Nature 549, 195 (2017).
  • V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow & J. M. Gambetta, "Supervised learning with quantum-enhanced feature spaces", Nature 567, 209 (2019).