Quiz: Quantum Kernels

Answers with explanations at the end.

1. Write the quantum kernel, and say why it can be computed without constructing the feature vector.

2. Which circuit computes it, and which number do you read off?

3. Give the two properties a Gram matrix must have that are one line each to check, and one more that matters.

4. Batching the Gram matrix gave what speedup, and why does it matter on hardware as well as on a simulator?

5. State the structural advantage of kernels over Chapter 33's variational classifier, in one sentence.

6. List four things the variational model needed that the kernel method does not.

7. What replaces them?

8. Feature-map tuning moved accuracy across what range, and how does that compare with the method-to-method differences in this chapter?

9. Across ten splits, how did the quantum kernel compare with the classical RBF kernel? Why is that comparison unusually clean?

10. How did it compare with Chapter 33's variational model, and what does that imply about the convexity advantage?

11. Define kernel concentration and give the measured collapse.

12. What was predicted to follow from concentration, and what actually happened?

13. Explain the discrepancy.

14. State the general rule that follows, in terms of information rather than qubits.

15. Why is the dangerous regime the one kernel methods are for?

16. How many unique kernel entries does a Gram matrix need for $n$ training points?

17. How many shots does each entry need, and what does that multiply with?

18. Compute the Gram bill at ten qubits for 201 samples.

19. How does the kernel method's cost scaling differ from Chapter 33's, and why does that matter at production size?

20. Summarize what the kernel argument establishes and what it does not.

Answers

1. $K(x, x') = \big|\langle\phi(x)|\phi(x')\rangle\big|^2 = \big|\langle 0|U^\dagger(x)U(x')|0\rangle\big|^2$. It can be computed without the feature vector because kernel methods only ever need inner products — the same reason a classical RBF kernel works in an infinite-dimensional space on a laptop.

2. Feature map on one point, then the adjoint of the feature map on the other, and you read $P(|0\dots0\rangle)$ — which is exactly that squared overlap.

3. Unit diagonal ($K(x,x)=1$, since it is an inner product with itself) and symmetry. The third is positive semi-definiteness, which is what makes the SVM dual convex — and an SVM will happily fit a matrix that fails all three.

4. Roughly 500× (51.3 s → 0.11 s for 40,401 entries; repeat runs gave 478× and 868×). It matters on hardware because batching becomes one job submission rather than 40,401.

5. Training is convex — one optimum, found exactly, in about two milliseconds, independent of initialization.

6. Any four of: a non-convex landscape; random initialization that matters; a learning rate; barren plateaus (Chapter 32 measured an 88× collapse); an optimum that is only whatever sixty steps found; seed-dependent reproducibility.

7. The feature map's structure, depth, entangling pattern and input scaling. The design problem moves; it does not vanish. "No hyperparameters to train" is not "no hyperparameters."

8. 0.6364 untuned to 0.8500 tuned — a swing larger than any method-to-method difference in this chapter, which is why a kernel result without a feature-map sweep is a result about one arbitrary feature map.

9. SVC(rbf) beat it by $+0.0576 \pm 0.0083$ — about seven standard errors. The comparison is unusually clean because both use the same SVM solver on the same data; the only difference between those two rows is which kernel function was used.

10. Statistically indistinguishable — $0.8313 \pm 0.0381$ against Chapter 33's $0.8343 \pm 0.0407$. It implies that the convexity advantage is real and did not produce a better classifier: it removed the optimization problem, and the optimization was not what limited the result.

11. As the feature map spreads states over more of Hilbert space, any two become nearly orthogonal, so $K(x,x') \to 0$ off the diagonal and the Gram matrix approaches the identity. Measured with one independent feature per qubit: 0.25147 at 2 qubits to 0.00088 at 10 — a several-hundred-fold collapse.

12. Predicted: the SVM would memorize the training set and generalize at chance, with every training point becoming a support vector. Measured: test accuracy ROSE from 0.7778 to 0.8889 across 2–12 qubits, the generalization gap stayed near 0.07, and support vectors grew only from 91 to 144 of 201. No memorization.

13. The two measurements used different feature dimensions. The concentration sweep used one independent feature per qubit, which genuinely spreads the state. The accuracy sweep used moons data with two features re-encoded redundantly over up to twelve qubits — adding expressive depth without spreading the state, so concentration was mild (about 11×) and the depth helped.

14. Concentration is driven by the dimension of the data the map sees, not by the qubit count. Extra qubits that carry no new information about $x$ cannot make $\phi(x)$ and $\phi(x')$ more distinguishable. A failure mode's mechanism can be right while your judgement about whether it applies is wrong.

15. Because kernel methods exist to handle high-dimensional data, and high-dimensional data is precisely what makes the map independent-feature-per-qubit — the severe regime.

16. $n(n+1)/2$ by symmetry: 20,301 for $n = 201$, against 40,401 in the full matrix.

17. $\mathcal{O}(1/K^2)$ shots, where $K$ is the kernel value (Chapter 24 §24.3). It multiplies with the $n^2$ entry count — so concentration and the shot budget multiply, exactly as barren plateaus and the shot budget did in Chapter 32 §32.5.

18. $K = 0.00078 \Rightarrow 1{,}643{,}655$ shots per entry, times 20,301 entries $= 3.34\times10^{10}$ shots $= 926.9$ QPU hours $=$ 38.6 QPU-days — for the Gram matrix alone, before any training, on 201 samples, for a kernel whose off-diagonal entries carry almost no information.

19. Chapter 33's variational cost was $(2p+1)\times\text{samples}\times\text{steps}$ — linear in the dataset. The kernel cost is quadratic. At demo size (201) that is invisible; at 20,100 samples it is 202 million entries, roughly ten thousand times the demo. Convexity removed the optimization, did not remove the shots, and introduced a quadratic.

20. Establishes: the mathematics is clean; the convex-training advantage is real and complete; and this is where QML's rigorous separations live — Liu, Arunachalam and Temme's proven advantage is a kernel result, and the fixed feature map is why the analysis is tractable. Does not establish: any practical advantage — it loses to a classical RBF kernel by seven standard errors on the same solver, ties with Chapter 33's variational model, and costs quadratically in the dataset and exponentially in the concentration.