Quantum Machine Learning · Chapter 01
What exactly is being learned when the model is a quantum circuit?
Starting point: Linear algebra, probability, and the basics of supervised learning.
Anchor example: Two circuits that fit the same data while making different claims.
Method: Separate the model, the training rule, and the evidence for each claim.
Watch for: A quantum circuit is not automatically a better hypothesis class.
This lesson includes explanations, worked examples, and problems with solutions. Results quoted from the literature are identified as theorems with their hypotheses.
A quantum machine learning model is a classical function computed by a quantum device. That sentence contains the whole difficulty of the subject. The function is classical—it takes classical data in and returns a number or a label—but its computation runs through amplitudes, interference, and measurement. Everything that follows depends on which part of learning the quantum device is supposed to improve: representing the hypothesis, evaluating it, or finding its parameters. This chapter separates those roles, because most confused claims in the literature come from merging them.
Before asking whether a quantum model is better, we need a precise account of what it is being compared with. This section fixes the vocabulary: a task, a class, and a training rule are three different objects, and only the first two define what can be learned in principle.
A supervised learning task is a triple: a distribution \(D\) on \(\mathcal X\times\mathcal Y\), a hypothesis class \(\mathcal H=\{h_\theta\}\), and a loss \(\ell\). The quantity of interest is the risk
\[R(\theta)=\mathbb E_{(x,y)\sim D}\,\ell\bigl(h_\theta(x),y\bigr),\]which nobody can compute exactly, because \(D\) is unknown. What is computable is the empirical risk on a sample \(S=\{(x_i,y_i)\}_{i=1}^N\),
\[\widehat R_S(\theta)=\frac1N\sum_{i=1}^N\ell\bigl(h_\theta(x_i),y_i\bigr),\]and the object of interest is the gap between the two. A learning algorithm succeeds if it returns \(\theta\) whose risk is close to the best achievable in \(\mathcal H\), using only \(S\).
Notice what this definition does not mention: circuits, qubits, or gates. A quantum model enters only when we specify \(\mathcal H\): the hypothesis is a function computed by preparing a state that depends on \(x\) and \(\theta\), then measuring. The task fixes the yardstick; the model chooses how the function is computed. Writing the task first is what prevents the common slide from "our circuit fits the training data" to "we have learned the task".
Four labelled points are given: \((0,0),(1,1),(2,0),(3,1)\). Compute the empirical risk of the best constant classifier under zero–one loss, and of the classifier \(h(x)=\mathbb 1[x\ge 1.5]\).
Two points have label 0 and two have label 1, so any constant predictor is wrong on exactly two points: \(\widehat R=2/4=0.5\). The threshold rule predicts 0 on the first two and 1 on the last two, so \(\widehat R=0\). The example is trivial, but it already shows why a single number is not evidence: the threshold rule can also achieve zero empirical risk on a dataset engineered to make it look perfect, and we still know nothing about \(R\). Only a statement about the distribution—or a bound that holds uniformly over \(\mathcal H\)—converts empirical success into a claim about learning.
A quantum hypothesis class is fixed by three choices: an encoding \(x\mapsto\rho(x)\), a parameterised circuit \(W(\theta)\), and a measurement \(M\). The hypothesis is
\[h_\theta(x)=\operatorname{tr}\!\bigl[W(\theta)\rho(x)W(\theta)^{\dagger}M\bigr],\]a real number in the range of \(M\). For binary classification, a threshold turns it into a label; for regression it is the prediction. Everything the model can do is contained in this triple, so any two models with the same triple are the same model—whatever their circuit diagrams look like.
What does quantum mechanics add to the hypothesis class? Not "more parameters": a circuit with \(p\) angles is a \(p\)-dimensional family, exactly like a classical model with \(p\) weights. What changes is the shape of that family inside function space. Three mechanisms matter, and only the third is specifically quantum.
One concrete restriction is worth stating early, because it disciplines the intuition. When the encoding is a product of single-qubit rotations generated by Pauli operators and the observable is fixed, the model is a trigonometric polynomial in the data: a finite Fourier series whose frequencies are set by the encoding's generator eigenvalues. This is a theorem with hypotheses, not a slogan, and we return to it in Chapter 2.
Take a single qubit, encoding \(R_z(x)=\exp(-ixZ/2)\), a parameter \(\theta\), and the model \(h_\theta(x)=\langle 0|R_z(\theta)R_z(x)\,Z\,R_z(x)^{\dagger}R_z(\theta)^{\dagger}|0\rangle\). Write \(h_\theta(x)\) in closed form and identify its Fourier structure.
The two rotations combine into \(R_z(\theta+x)\), so \(h=\langle 0|R_z(\theta+x)ZR_z(\theta+x)^{\dagger}|0\rangle=\cos(\theta+x)\). Expanding gives \(h_\theta(x)=\cos\theta\cos x-\sin\theta\sin x\), a degree-one trigonometric polynomial whose coefficients are the trainable parameters. Two parameters, two frequencies, and no interference: a single rotation cannot produce a richer function however it is trained. Repeating the encoding block and interleaving entanglers is what adds frequencies—the subject of Chapter 2.
A model is a class plus a loss. A training rule is a procedure that searches the class. The same model trained two ways can produce very different results, and a statement about one is not a statement about the other.
It is useful to keep three questions apart, because each has its own kind of evidence:
| Claim | Question | Evidence that supports it |
|---|---|---|
| Expressivity | Which functions are in \(\mathcal H\)? | A structural theorem, a Fourier or polynomial characterisation, or a counting argument |
| Trainability | Can a stated algorithm find good parameters? | A convergence guarantee, a gradient-variance bound, or a controlled numerical study |
| Generalisation | Does low empirical risk imply low risk? | A bound that holds uniformly over \(\mathcal H\), or a pre-registered test comparison |
Confusing these is the most common error in the field. A circuit whose class contains every function on \(n\) bits is expressive and useless if the optimiser cannot find the right member; a circuit that trains reliably is unremarkable if its class is a subset of linear models; and a model that generalises on one dataset says nothing about the class at large.
Consider the one-parameter loss \(L(\theta)=1-\cos\theta\). Show that gradient descent initialised at \(\theta_0=\pi\) never moves, and classify that stationary point.
The gradient is \(\sin\theta\), which vanishes at \(\theta=\pi\). Gradient descent therefore stays at \(\theta=\pi\) forever, where \(L=2\)—the maximum of the loss, not a minimum. The point is not that the model is inexpressive (it attains \(L=0\) at \(\theta=0\)) nor that the optimiser is broken in general; it is that a trainability claim needs an argument about where the trajectory starts and how it moves. Reporting "the loss did not decrease" would be a statement about initialisation, not about the model.
If a quantum model is a classical function computed on a quantum device, an advantage has to be explained. This section catalogues the legitimate sources, and insists on a ledger that includes the cost of loading the data.
Three mechanisms can, in principle, give a quantum learner something a classical learner cannot cheaply reproduce.
Quantum data. If the data are themselves quantum states—a molecule's ground state, a scattering event, a state produced by an experiment—then a learner that consumes states directly avoids a tomographic bottleneck. This is the cleanest case, because no classical vector has to be loaded: the sample is the state.
Hard-to-evaluate models. Some circuits produce feature vectors whose inner products are believed hard to estimate classically. If a learning problem aligns with that structure, evaluating the model—not merely storing its parameters—can be the expensive step. Chapter 3 makes this precise with kernels.
Hard-to-represent functions. A compact circuit can represent functions with exponentially many Fourier components. Whether such a function is learnable from polynomially many examples is a separate question, and often the answer is no.
The counterweight is loading. Preparing an arbitrary \(n\)-qubit state requires exponentially many gates in general, so a classical dataset of \(2^n\) numbers cannot be poured into amplitudes for free. Either the algorithm assumes a data structure that supplies amplitudes on demand—an assumption about hardware that does not currently exist at scale—or the loading cost must be counted in the ledger. Any claim that omits this step is measuring the wrong thing.
A dataset has \(2^{10}=1024\) features per point. Compare the cost of amplitude encoding one point exactly with the cost of ten rotation angles.
Amplitude encoding needs ten qubits and, in the worst case, on the order of \(2^{10}=1024\) two-qubit gates to prepare an arbitrary normalised vector; angle encoding needs ten rotation gates, one per qubit. The two encodings are therefore three orders of magnitude apart at this size, and the gap doubles with every additional qubit. The comparison is not an argument against amplitude encoding—it is an argument that its cost must appear in the ledger, and that a claim of advantage must show the model's benefit exceeds this price.
Every fair comparison can be written as a sum of three costs:
\[\text{total}=\underbrace{C_{\text{load}}}_{\text{prepare }\rho(x)}+\underbrace{N_{\text{eval}}\cdot C_{\text{eval}}}_{\text{run the circuit}}+\underbrace{C_{\text{opt}}}_{\text{update parameters}},\]where \(N_{\text{eval}}\) counts circuit executions including shots. A quantum advantage requires this total to be smaller than the best classical alternative—not merely that one term is smaller.
| Stage | Classical kernel | Quantum kernel |
|---|---|---|
| Load one example | \(O(d)\) memory access | State preparation, up to \(O(2^{n})\) gates, unless an oracle is assumed |
| One kernel entry | \(O(d)\) arithmetic | One circuit execution, repeated for shots |
| Full Gram matrix | \(O(N^2d)\) | \(O(N^2)\) circuits, each with \(S\) shots |
| Training | Convex in the dual | Convex in the dual, once entries are known |
The table already explains a persistent empirical observation: at modest \(N\), the classical kernel is cheap because its per-entry cost is a few dozen floating-point operations, while the quantum kernel requires a full circuit execution per entry. Making the quantum side competitive requires either an entry cost that is classically prohibitive or a problem where the classical kernel needs a feature dimension far larger than \(d\).
Estimate the circuit executions needed for a quantum kernel on \(N=1000\) training points with \(S=1000\) shots per entry, and the wall-clock time at one microsecond per shot.
The Gram matrix has \(N^2=10^{6}\) entries, and each needs \(S=10^{3}\) shots, so \(10^{9}\) shots in total. At \(1\,\mu s\) each this is \(10^{3}\) seconds—about seventeen minutes—for a single kernel matrix, before any training or testing. A classical kernel on the same 1000 points with \(d=100\) takes roughly \(10^{6}\times10^{2}=10^{8}\) arithmetic operations, well under a second. The quantum route must therefore win on something other than per-entry constant factors, which is why the interesting arguments are asymptotic and structural rather than empirical at small scale.
The strongest empirical QML papers of the last few years share a habit: they compute a strong classical baseline before claiming anything. The pattern is familiar from other fields, but QML has two extra hazards.
The first is that the quantum model is often evaluated on data that was constructed to be hard for a specific classical model—say, data whose labels depend on a parity that a linear classifier cannot express. A gradient-boosted tree or an RBF kernel may solve it easily, so the baseline must be chosen to be strong, not convenient.
The second is the "quantum-inspired" baseline. A classical algorithm derived from the same mathematics—random features, tensor networks, or a classical simulation of the circuit—can often reproduce the quantum model's predictions at a fraction of the cost. If it can, the experiment has demonstrated a simulation, not an advantage.
A useful discipline is to write the comparison before running anything: which classical model, with which hyperparameters, on which data split, at what budget. Deciding afterwards which baseline to report is how weak comparisons survive review.
An advantage claim is a mathematical statement with quantifiers, and it can be checked like any other. This section turns the rhetoric into a template, lists the failure modes that recur, and states what this course does and does not attempt.
A precise claim has the form
\[\exists\,\text{task }(D,\mathcal H,\ell)\ \ \forall\,\text{classical algorithms } A\ \ \exists n:\ \ \text{cost}_Q(n)<\text{cost}_A(n),\]with the cost model, the access to data, and the accuracy target all named. Different quantifier orders give very different statements, and the differences are not pedantry:
Reading a paper, the useful question is which of these three is being claimed, and whether the evidence matches. A theorem establishes the first; a complexity analysis establishes the second; only a controlled experiment with a strong baseline establishes the third.
Rewrite this sentence precisely: "Quantum kernels outperform classical kernels on our dataset."
A defensible version is: "On dataset \(D\) with a fixed train/test split, a support vector machine using the estimated quantum kernel \(K_Q\) achieved test accuracy \(a_Q\), compared with \(a_C\) for an RBF kernel tuned by cross-validation on the training folds; the difference is \(a_Q-a_C\) with a bootstrap interval over splits, at equal total shot and wall-clock budget." The rewrite adds the dataset, the baseline and its tuning rule, the metric, the uncertainty, and the cost model. Without those five items the original sentence cannot be true or false—only persuasive.
The same mistakes recur across the literature, and each has a cheap diagnostic.
| Failure | What it looks like | Diagnostic |
|---|---|---|
| Simulator advantage | Noise-free state-vector results at 20+ qubits | Run the same circuit with a classical simulator and compare cost |
| Barren plateau | Loss flat from the first iteration | Plot gradient variance against qubit count and depth |
| Weak baseline | Only linear models are compared | Add a tuned RBF kernel or gradient boosting |
| Test leakage | Encoding or kernel chosen after seeing test labels | Fix the model before touching the test split |
| Unequal budgets | Quantum gets more shots than the classical model gets time | Report both at matched wall-clock |
| Surrogate metric | Kernel-target alignment instead of accuracy | Report the task metric as well |
None of these is exotic. Each is a natural consequence of working with expensive hardware, small datasets, and a strong incentive to report the best number. Chapter 7 returns to them with quantitative tools.
A paper reports 96% test accuracy with a 12-qubit kernel and 78% with an RBF kernel. It says the quantum kernel was chosen after inspecting kernel-target alignment on the full dataset. Which failure does this describe, and what would repair it?
This is test leakage combined with a weak baseline. Selecting the kernel using alignment computed on all the data—including the test points—optimistically biases the reported accuracy, because the choice has already seen the labels it is later scored against. The repair is procedural: choose the feature map and its hyperparameters using only training folds, tune the RBF baseline with the same protocol, and report both with the spread over splits. Note that the repair may well remove the apparent advantage; that is the point of doing it.
It is worth being explicit about scope, because QML writing often inflates it.
This course will derive the structure of quantum models: how encodings determine the Fourier spectrum, why kernels concentrate, where gradients vanish, and what uniform-convergence bounds do and do not say. It will give you the arithmetic to check a claim yourself, and a laboratory in which to reproduce every numerical example with the Python standard library.
This course will not prove a separation between quantum and classical learners, certify an advantage on real data, or survey the hardware literature. Those are research results with their own hypotheses; the course's job is to make you able to read them.
The remaining chapters follow this structure. Chapter 2 asks what an encoding does to the model's frequency content. Chapter 3 develops kernels and their quantum versions. Chapters 4 and 5 treat variational models and their gradients. Chapter 6 is devoted to trainability failures. Chapter 7 takes up generalisation and evaluation. Chapter 8 examines the classical algorithms that compete with quantum models. Chapter 9 is the audit project.
These sources define the framing used above: what a quantum model is, where an advantage could come from, and how claims are made honest.
These exercises draw on the whole chapter. Attempt each question before opening a hint, explain your reasoning, then compare it with the worked solution.
Which part of a learning task does a quantum circuit replace?
Look at the triple (distribution, class, loss).
The hypothesis class. The distribution and the loss are properties of the task; the circuit only fixes which functions are available and how they are computed.
Four points have labels (0,0,0,1). What is the empirical risk of the best constant classifier under zero–one loss?
Choose the majority label.
Predicting 0 is wrong once, so the risk is 1/4 = 0.25. Predicting 1 is wrong three times. A constant classifier on a balanced set gives 0.5.
A 20-qubit circuit has 2^20 amplitudes, so it has 2^20 parameters and is automatically more expressive than a 20-parameter classical model. Correct this.
Separate the dimension of the state space from the number of trainable parameters.
No. A circuit with p angles is a p-dimensional family of functions, exactly like a classical model with p weights. The state space is large, but the model explores only a p-dimensional slice of it. Expressivity is a property of that slice, not of the Hilbert-space dimension.
For h(x)=cos(θ+x) with θ=π/4, compute h(0) and h(π/2).
Substitute, then use exact cosine values.
h(0)=cos(π/4)≈0.7071 and h(π/2)=cos(3π/4)≈−0.7071. Both values lie in the reachable range of the single-frequency model, which is a degree-one trigonometric polynomial.
What fixes the set of frequencies a Pauli-encoded circuit can represent?
Consider the generator eigenvalues and the number of encoding layers.
The eigenvalues of the encoding generators, together with the number of times the encoding is applied. With L Pauli-generated layers and integer eigenvalues, the accessible frequencies are the integers from −L to L in each feature.
A training loss that does not decrease means the optimiser has converged. Correct this.
Think of a stationary point that is not a minimum.
No. A flat loss means the gradient is (near) zero, which happens at minima, maxima, and saddles alike, and also at initialisation points that sit exactly on a stationary value. The statement to check is where the trajectory started and whether the value is one you would accept.
For L(θ)=1−cos θ with gradient descent started at θ=π, describe the trajectory and classify the point.
Compute the gradient at π.
The gradient sin π = 0, so the trajectory never moves and L stays at 2, the maximum of the loss. The model could achieve L=0 at θ=0, so this is an initialisation failure, not an expressivity limit.
A quantum kernel experiment uses N=200 points and S=1000 shots per entry. Count circuit executions for the Gram matrix, and the time at 1 microsecond per shot.
Square N, then multiply by S.
The matrix has 200² = 40,000 entries, each needing 1000 shots, so 4×10^7 shots, about 40 seconds at 1 microsecond each. Training and testing add more evaluations on top of this.
Rewrite 'quantum kernels outperform classical kernels on our dataset' as a claim that could be checked.
Name the dataset, baseline, metric, uncertainty, and budget.
A checkable version names the dataset and split, the classical baseline and how it was tuned, the metric, the uncertainty over splits, and the cost budget at which both were compared. It also states whether the claim is an existence separation, a runtime speedup, or a practical advantage.
A paper reports 95% test accuracy for a 10-qubit kernel and 80% for an RBF kernel, with the feature map chosen by inspecting test accuracy. Name the two failures and the repair.
Consider selection and baseline strength.
Test leakage (the map was selected using test labels) and a possibly weak baseline. The repair is to select the map and its hyperparameters on training folds only, tune the classical baseline under the same protocol, and report both with the spread over splits.