Quantum Machine Learning · Chapter 03
When does a quantum feature map give a better kernel than a classical one?
Starting point: Chapter 2 and elementary statistical learning theory.
Anchor example: A two-qubit kernel that is flat, and one that is not.
Method: Estimate the Gram matrix, then test it against a classical kernel.
Watch for: A kernel that is hard to compute is not automatically one that generalises.
This lesson includes explanations, worked examples, and problems with solutions. Results quoted from the literature are identified as theorems with their hypotheses.
Kernel methods are the cleanest way to ask whether a quantum model is better than a classical one, because they make the comparison arithmetic. A kernel is a similarity function; a quantum feature map defines one by an inner product of states. Everything else—training, regularisation, generalisation—is classical theory applied to the resulting matrix. This chapter builds that view, prices the matrix, and shows the limit that appears when the matrix goes flat.
A kernel encodes a notion of similarity, and the learning algorithm never touches the features themselves. Getting this structure right first makes the quantum addition easy to place.
Let \(K\) be a positive semi-definite function on \(\mathcal X\times\mathcal X\). It defines a reproducing-kernel Hilbert space \(\mathcal H_K\) and a feature map \(\phi\) with \(K(x,x')=\langle\phi(x),\phi(x')\rangle\), although the map never has to be written down. Consider any regularised empirical risk of the form
\[\min_{f\in\mathcal H_K}\ \frac1N\sum_{i=1}^N\ell\bigl(f(x_i),y_i\bigr)+\lambda\|f\|_{\mathcal H_K}^2 .\]The representer theorem states that a minimiser has the form
\[f(x)=\sum_{i=1}^N\alpha_i\,K(x,x_i),\]so the search is over \(N\) coefficients rather than over a function space. Substituting the expansion turns the problem into one that depends on the data only through the Gram matrix. That is the kernel trick: the cost scales with the number of examples, not with the dimension of the feature space—which is exactly why an exponentially large quantum feature space is not automatically disqualifying.
Two consequences follow immediately. Training cost is at least \(O(N^2)\) to form \(K\) and \(O(N^3)\) to solve the resulting system, so the method is suited to moderate \(N\) with large feature dimension. And the whole model is determined by \(K\), so comparing two quantum models is comparing two matrices.
Three training points have Gram matrix \(K=\begin{pmatrix}1&0.5&0\\0.5&1&0\\0&0&1\end{pmatrix}\) and dual coefficients \(\alpha=(1,-1,0.5)\). Evaluate \(f\) at a test point whose similarities are \(K(x,x_i)=(0.2,0.1,0.9)\).
The representer expansion gives \(f(x)=1(0.2)+(-1)(0.1)+0.5(0.9)=0.2-0.1+0.45=0.55\), with the sign of the prediction taken from the threshold of the classifier. The first two examples have opposite coefficients, so their contributions nearly cancel at a point where the two similarities are close. This is the mechanism by which a kernel classifier expresses "different from this class but similar to that one", and it is visible entirely in the row of the Gram matrix.
A kernel is useful when its similarity agrees with the labels. Two quantities capture the agreement.
The first is target alignment, the normalised inner product between \(K\) and the label kernel \(yy^{\top}\):
\[A(K,y)=\frac{\langle K,\,yy^{\top}\rangle}{\|K\|_F\,\|yy^{\top}\|_F}.\]It is cheap to compute and useful for diagnostics, but it is not a performance guarantee—a kernel can align well with the training labels and still generalise poorly. The second is the eigenvalue spectrum. A kernel with a few large eigenvalues behaves like a low-dimensional linear model; a kernel with many comparable eigenvalues can fit anything and needs strong regularisation. The spectrum is where concentration damages a quantum kernel, as Section 3.2.3 shows.
Two further properties are non-negotiable. \(K\) must be positive semi-definite, or the optimisation is not convex and the representer theorem does not apply; and the diagonal should be constant if the kernel is to be translation invariant—otherwise the model has a built-in preference for some training points.
Compute the alignment of the identity kernel \(K=I\) with labels \(y=(1,1,-1,-1)\), and of the rank-one kernel \(K=J\) with the same labels.
For \(K=I\): \(\langle I,yy^{\top}\rangle=\sum_i y_i^2=4\), \(\|I\|_F=2\), \(\|yy^{\top}\|_F=\|y\|^2=4\), so \(A=4/(2\cdot4)=0.5\). For \(K=J\): \(\langle J,yy^{\top}\rangle=(\sum_i y_i)^2=0\), so \(A=0\). The identity kernel declares every point unrelated to every other, and the constant kernel declares them all identical; neither can express the two-cluster structure. Alignment detects both failures without training anything.
For squared loss, substituting the representer expansion gives the linear system
\[(K+\lambda I)\,\alpha=y,\qquad f(x)=\sum_i\alpha_i K(x,x_i).\]The parameter \(\lambda\) does two jobs at once: it controls overfitting, and it controls conditioning. The solution's sensitivity to noise in \(K\) is governed by the condition number \(\kappa(K+\lambda I)\), which grows as the smallest eigenvalue of \(K\) shrinks. Every kernel matrix estimated from finitely many shots is noisy, so an ill-conditioned \(K\) turns shot noise into large coefficient errors—a failure mode that has nothing to do with the quantum model's expressivity.
For a soft-margin classifier the dual is a quadratic programme in \(\alpha\) with box constraints, again depending on the data only through \(K\). In both cases the practical message is the same: the kernel matrix is the interface, and its numerical properties decide whether training succeeds.
Let \(K=\begin{pmatrix}1&0.99\\0.99&1\end{pmatrix}\) and \(y=(1,-1)\). Solve the ridge system for \(\lambda=0.01\) and for \(\lambda=1\), and compare the coefficient magnitudes.
The eigenvalues of \(K\) are \(1.99\) and \(0.01\). With \(\lambda=0.01\) the shifted eigenvalues are \(2.0\) and \(0.02\), a condition number of \(100\); solving gives coefficients of roughly \((0.5,-0.5)\) amplified along the near-null direction, with magnitude about \(25\) in the eigenbasis. With \(\lambda=1\) the eigenvalues become \(2.99\) and \(1.01\), the condition number falls to about \(3\), and the coefficients are order one. The data did not change; only the numerical conditioning did—which is why an experiment must report \(\lambda\) alongside any accuracy figure.
A quantum feature map defines a kernel by an inner product of states. Estimating one entry is a small, well-understood circuit problem; estimating a matrix of them is where the cost appears.
With \(U_\phi(x)|0\rangle=|\psi(x)\rangle\), the kernel is the squared overlap
\[K(x,x')=\bigl|\langle 0|U_\phi(x')^{\dagger}U_\phi(x)|0\rangle\bigr|^2 .\]The estimate is direct: apply \(U_\phi(x)\), then \(U_\phi(x')^{\dagger}\), and measure all qubits in the computational basis. The probability of the all-zeros outcome is exactly \(K(x,x')\), so if the outcome occurs \(c\) times in \(S\) shots, \(\hat K=c/S\) is an unbiased estimate with variance \(K(1-K)/S\). No ancilla and no tomography are required—one circuit, run many times.
This is the reason quantum kernels became a practical research topic: the entry cost is a single circuit whose depth is twice the encoding depth, not an exponential state-reconstruction procedure. The depth still matters, because near-term devices accumulate error per gate, and the circuit must be run once per matrix entry.
An entry with true value \(K=0.25\) is estimated from \(S=400\) shots. Give the standard deviation, and the number of shots needed to halve it.
The variance is \(K(1-K)/S=0.25\cdot0.75/400=4.7\times10^{-4}\), so the standard deviation is about \(0.0217\)—roughly 9% of the value. Halving that requires quadrupling the shots to 1600, because the deviation scales as \(S^{-1/2}\). The arithmetic is unforgiving: every factor of two in precision costs a factor of four in circuit executions, and the factor applies to every entry of the Gram matrix separately.
Because \(\hat K\) is a sample mean, its relative error is what matters for a classifier:
\[\frac{\sigma_{\hat K}}{K}=\sqrt{\frac{1-K}{SK}}\approx\frac{1}{\sqrt{SK}}\quad (K\ll1).\]The approximation exposes the danger. If the typical kernel value is small—say \(K\sim2^{-n}\), which is what concentration produces—then constant relative precision requires \(S\sim2^{n}\) shots per entry. The Gram matrix then costs \(\Theta(N^2 2^n)\) circuit executions, and the exponential that amplitude encoding avoided reappears in the estimator.
For \(n=10\) qubits under the concentration model of Section 3.2.3, the typical off-diagonal entry is about \(2^{-n}\). How many shots give a 10% relative error?
\(K\approx2^{-10}\approx9.8\times10^{-4}\). A 10% relative error needs a standard deviation of \(0.1K\), so \(K(1-K)/S=(0.1K)^2\), giving \(S\approx(1-K)/(0.01K)\approx10^{5}\). Each Gram-matrix entry then needs about a hundred thousand shots; with \(N=500\) points the matrix has \(2.5\times10^{5}\) entries, so the total is \(2.5\times10^{10}\) circuit executions. The estimator, not the circuit, has become the bottleneck.
The final difficulty is structural. For a feature map whose states behave like random states in a \(d=2^n\)-dimensional space, the squared overlap between two distinct encoded points behaves like \(X=\bigl|\langle\psi|\phi\rangle\bigr|^2\) with \(X\sim\text{Beta}(1,d-1)\). Hence
\[\mathbb E[X]=\frac1d,\qquad \operatorname{Var}[X]=\frac{d-1}{d^{3}}\approx\frac{1}{d^{2}},\]so the typical off-diagonal entry is \(1/d\) and its spread is also about \(1/d\). Two conclusions follow, and they point in opposite directions. In absolute terms the matrix approaches a constant: entries shrink towards zero, so the kernel's ability to distinguish pairs by their similarity fades. In relative terms the noise does not shrink at all: the fluctuations are as large as the mean, so every entry is a poor estimate unless the shot count grows exponentially.
This is the mechanism behind the exponential concentration results for quantum kernels. It is a statement about the model, not about hardware: a kernel whose entries all approach the same value can be reproduced by a trivial classifier, and no amount of shot precision restores the lost distinction.
Concentration rules out one kind of hope—that a richer feature map automatically gives better similarity—but not every quantum kernel is concentrated. This section states the conditions under which a kernel can help and the checks that a serious comparison needs.
To compare two kernels on the same data, Huang and colleagues introduce a quantity that measures how differently they organise the feature space:
\[g(K_1\|K_2)=\Bigl\|\sqrt{K_2}\,K_1^{-1}\sqrt{K_2}\Bigr\|_\infty ,\]where \(\infty\) is the spectral norm and the kernels are taken on the training set. A large \(g\) means the two kernels induce very different geometries. The relevant theorem, stated with its hypotheses, says roughly that if a quantum kernel can fit the target well, then either the classical kernel can too, or \(g\) is large; a provable advantage therefore requires both a large geometric difference and a target that the quantum geometry happens to match.
This is a useful discipline. It converts "our kernel is more expressive" into two checkable numbers: the geometric difference, and the alignment on training folds. Neither is decisive on its own, but a claimed advantage with a small \(g\) is in immediate trouble.
Take \(K_1=\operatorname{diag}(1,0.1)\) and \(K_2=I\) on two training points. Compute \(g(K_1\|K_2)\) and \(g(K_2\|K_1)\).
For the first, \(\sqrt{K_2}K_1^{-1}\sqrt{K_2}=\operatorname{diag}(1,10)\), whose spectral norm is \(10\). For the second, \(\sqrt{K_1}K_2^{-1}\sqrt{K_1}=\operatorname{diag}(1,0.1)\), with norm \(1\). So \(g\) is not symmetric: \(g(K_1\|K_2)=10\) but \(g(K_2\|K_1)=1\). The asymmetry is the point—the expression measures how far \(K_1\) stretches the geometry that \(K_2\) defines, and reversing the roles is a different question. Numerical care is needed too: with a near-singular \(K_1\) the inverse amplifies noise, which is why implementations regularise before inverting.
The best-known separation result for quantum kernels uses data whose labels are defined by a discrete logarithm, together with a feature map built from the same structure. For that construction, the quantum kernel provably generalises from a polynomial number of examples while any classical kernel needs exponentially many.
The result is real and worth understanding, and it is also the clearest example of why the three claim types of Chapter 1 matter. It establishes an existence separation: there is a task, a distribution, and a model with a stated access model that separates the two. It does not establish that the same separation survives on data anyone actually has, because the construction encodes the problem's structure into the feature map by hand—and if that structure is known, a classical algorithm can often be built from it too.
The honest reading is that separations tell us where to look. They identify the structural conditions—hard-to-compute inner products, a target aligned with them, no classical shortcut—that a practical demonstration would have to satisfy.
A paper reports a quantum kernel with 99% accuracy and a classical baseline with 60%. List three questions that must be answered before this counts as evidence of a separation.
First, what is the access model? If the quantum feature map uses structure that a classical algorithm could also exploit, the comparison is between a clever model and a naive one. Second, how was the baseline tuned, and was it given the same tuning budget as the quantum model? Third, how large is the geometric difference, and does the advantage persist when the classical model is allowed the same number of features? A separation claim needs all three; a single accuracy number answers none of them.
The chapter's content condenses into a short protocol. Running it before a training run saves weeks.
| Check | Why it matters |
|---|---|
| Is the encoding injective on the data range? | Periodic maps make distant points identical (Section 2.2.3) |
| Is the circuit classically simulable at this size? | If so, the classical simulator is the baseline |
| What is the typical off-diagonal entry, and its spread? | Concentration makes the classifier blind (Section 3.2.3) |
| How many shots per entry, and what is the resulting matrix error? | Shot noise propagates through \(K^{-1}\) |
| What is the condition number of \(K+\lambda I\)? | Ill-conditioning amplifies that noise |
| What is the geometric difference from the classical kernel? | A small value leaves no room for an advantage |
| Was the map fixed before the test set was opened? | Otherwise the comparison is leaking (Chapter 1) |
Chapter 4 turns to the other major family—variational models trained by a classical optimiser—and Chapter 6 shows that the trainability problems there are cousins of the concentration effect derived here.
These sources develop the kernel view, the concentration results, and the geometric comparison used in this chapter.
These exercises draw on the whole chapter. Attempt each question before opening a hint, explain your reasoning, then compare it with the worked solution.
State the representer theorem in one sentence.
What form does a minimiser take?
For a regularised empirical risk in a reproducing-kernel Hilbert space, a minimiser is a linear combination of kernel evaluations at the training points, f(x) = Σ α_i K(x, x_i), so the search is over N coefficients rather than a function space.
Compute the target alignment of K = I with y = (1,1,1,−1).
⟨I, yyᵀ⟩ = Σ y_i².
The inner product is 4, ‖I‖_F = 2, and ‖yyᵀ‖_F = 4, so the alignment is 4/(2·4) = 0.5.
Is K = [[1,2],[2,1]] a valid kernel matrix?
Compute its eigenvalues.
No. The eigenvalues are 3 and −1, so K is not positive semi-definite and the induced optimisation is not convex. A valid Gram matrix must have nonnegative eigenvalues.
For K = I, λ = 1, and y = (1,−1), solve the ridge system for α.
The system is (K + λI)α = y.
The matrix is 2I, so α = (0.5, −0.5). The prediction at a point with similarities (1,0) is 0.5.
An entry with K = 0.5 is estimated from 100 shots. Give the standard deviation and the number of shots needed to halve it.
Variance is K(1−K)/S.
Variance 0.25/100 = 0.0025, standard deviation 0.05. Halving it needs 400 shots, since the deviation scales as the inverse square root of the shot count.
How many shots give a 10% relative error for a kernel value of 10⁻⁴?
Use S ≈ (1 − K)/(0.01K).
S ≈ 1/(0.01·10⁻⁴) = 10^5 shots for that single entry. Every entry of the Gram matrix pays this cost separately.
Under the Haar concentration model with n = 8, give the mean and spread of an off-diagonal kernel entry.
Mean is 1/d and spread is about 1/d for d = 2^n.
With d = 256 the mean is 1/256 ≈ 0.0039 and the spread is √(255/256³) ≈ 0.0039. The two are equal, so entries are noise around a constant.
A Gram matrix has N = 1000 points and each entry needs 1000 shots. How many circuit executions, and how long at 1 microsecond per shot?
Square N and multiply by the shot count.
10^6 entries × 10^3 shots = 10^9 executions, about 1000 seconds. This excludes training, testing, and any repeated runs for error bars.
Compute g(K1‖K2) and g(K2‖K1) for K1 = diag(1, 0.5) and K2 = I.
The expression is ‖√K2 K1⁻¹ √K2‖_∞.
For the first, K1⁻¹ = diag(1, 2), so the spectral norm is 2. For the second, √K1 K2⁻¹ √K1 = diag(1, 0.5), with norm 1. The quantity is asymmetric by construction.
Design a three-step pre-flight check for a claimed quantum-kernel advantage on a new dataset.
Cover the estimator, the baseline, and the selection protocol.
First, estimate a few thousand off-diagonal entries and check that the spread is small relative to the mean at the planned shot budget; second, fit the strongest classical kernel available under the same tuning budget; third, fix the feature map and hyperparameters using training folds only, then report accuracy differences with uncertainty over splits. A claim that survives all three is worth pursuing; one that fails the first is not.