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 with is stored in only qubits as
Two facts follow from what you just did.
- Loading is expensive. Preparing an arbitrary -qubit state takes on the order of gates, the same order of work as reading the data classically. Quantum random access memory (QRAM) proposals answer a query in depth, but need 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 with probability ; estimating all amplitudes needs at least on the order of repetitions.
Quantum kernels and variational classifiers
A feature map embeds a data point into a state, . Two learning models use it.
- Kernel methods. The quantum computer estimates the fidelity kernel 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 follows the embedding; the prediction is for an observable , trained by gradient descent.
Run , then ("compute–uncompute") and measure: the probability of all zeros is the kernel.
With shots the estimate is a binomial frequency.
Every pair needs its own estimate: the Gram matrix is .
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 (representer theorem; Schuld 2021).
A kernel entry is near . About how many shots give a standard error of ?
Show the answer
2500 shots
gives . For training points that is about entries, so over circuit runs for one Gram matrix.
HHL: an exponential speedup with fine print
The flagship quantum linear-algebra algorithm solves in a quantum sense: given and access to a sparse Hermitian matrix with condition number , prepare the state .
Expand the input in the eigenbasis of (rescaled so that ). You never compute this expansion; the algorithm acts on it linearly.
Phase estimation writes an estimate of each eigenvalue into a register.
An ancilla rotation controlled by the eigenvalue register, with .
Uncompute the eigenvalue register and keep the runs where the ancilla reads 1. With the success probability is , so amplitude amplification needs rounds.
| Fine print | What the exponential speedup needs | If it fails |
|---|---|---|
| Input | prepared in time (a formula, or a QRAM) | generic loading costs about |
| Matrix access | sparse (or efficiently block-encoded) with computable entries | simulating becomes expensive |
| Conditioning | the factor dominates | |
| Output | a few expectation values or samples, not itself | full readout costs at least about runs |
| Fair comparison | classical algorithms given equivalent data access | low-rank problems were dequantized (Tang) |
HHL has finished. What do you actually hold?
- The solution vector , written in a classical register
- A quantum state proportional to , from which you can estimate quantities like
- The list of eigenvalues of
- A certificate that has a unique solution
Show the answer
B. A quantum state proportional to , from which you can estimate quantities like
The output is a normalized state . Measurements give samples and expectation values; extracting all entries would cost at least about 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 with oracle calls instead of , and the BBBV lower bound shows nothing faster exists for unstructured search.
A classical computer checks candidates per second by brute force. An error-corrected quantum computer runs Grover oracle calls per second, needing calls. Above roughly what problem size does Grover win?
Show the answer
39
Break-even when , i.e. , so . Below that the classical machine is faster despite doing quadratically more work.
Brute force at checks per second; Grover at error-corrected oracle calls per second.
Beyond break-even, the quadratic speedup does pay off, in principle.
But brute force parallelizes perfectly, while splitting Grover across machines gains only . Real classical solvers also use heuristics and branch-and-bound that are vastly better than brute force.
Where the advantage is real
| Claim | Status (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 classifiers | Provable 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 data | Provable exponential reductions in the number of experiments for some tasks (Huang et al. 2022). |
| Optimization | Quadratic speedups (often erased by overheads); heuristics without general guarantees. |
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 ; expressive embeddings concentrate exponentially, and variational classifiers are kernel models in disguise.
- HHL prepares in : exponentially fast in only when 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.
Why does loading an arbitrary -dimensional classical vector into amplitudes threaten claims of exponential speedup?
- Amplitudes cannot represent negative numbers
- Amplitude encoding needs qubits
- Measurement destroys the encoded state
- Preparing a generic state takes about gates (or a QRAM with about components), comparable to the classical cost of reading the data
Show the answer
D. Preparing a generic state takes about gates (or a QRAM with about components), comparable to the classical cost of reading the data
The quantum algorithm may be after the state exists, but preparing it generically costs , which already matches a classical pass over the data.
In which situation can HHL's exponential speedup survive end to end?
- A dense matrix with , where you need every entry of
- A sparse, well-conditioned (), a preparable in time, and a need for only a few expectation values
- Any matrix, provided is large enough
- A sparse, well-conditioned matrix where you must print every entry of
Show the answer
B. A sparse, well-conditioned (), a preparable in time, and a need for only a few expectation values
All four conditions must hold: sparse access, small , cheap input, and an output that is a few numbers like .
In the compute–uncompute test, which measured quantity estimates the fidelity kernel ?
- The expectation value of on the first qubit after
- The average number of qubits measured as 1
- The probability of the all-zeros outcome after
- The phase of the amplitude of
Show the answer
C. The probability of the all-zeros outcome after
: the all-zeros probability is exactly the squared overlap.
For an NP-hard optimization problem whose structure you cannot exploit, what does Grover search offer over classical brute force on candidates?
- A quadratic speedup, about oracle calls: still exponential
- An exponential speedup, giving polynomial time
- No speedup at all
- A speedup that grows linearly with the number of parallel quantum processors
Show the answer
A. A quadratic speedup, about oracle calls: still exponential
Amplitude amplification reduces to about oracle calls, which is optimal for unstructured search (BBBV) and still exponential.
What did Ewin Tang's 2018 result show about the quantum recommendation-system algorithm of Kerenidis and Prakash?
- The quantum algorithm was incorrect
- It needs millions of physical qubits
- A classical algorithm with sample-and-query access to the same data matches it up to polynomial factors
- 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
- HHL & the Fine Print of Quantum Linear Algebra · Exponential speedups and the caveats that come with them.
- Dequantization & Quantum Kernels · When classical algorithms catch up, and when they cannot.
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).