Lesson 27: Quantum Kernel Methods and the Quantum Support Vector Machine¶
27.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Recall the SVM primal and dual problems and the kernel trick.
- Define the quantum kernel and describe the two circuits that estimate it.
- Assemble the complete QSVM pipeline and count its circuit executions.
- Analyse the \(O(M^2)\) kernel-matrix cost and the shot-noise requirement.
- State honestly where quantum kernels can and cannot give an advantage.
27.2 Classical SVM Recap¶
The maximum-margin classifier¶
Given labelled data \(\{(\vec x_i, y_i)\}_{i=1}^{M}\) with \(y_i\in\{-1,+1\}\), find the hyperplane \(\vec w\cdot\vec x + b = 0\) maximising the margin.
Primal (soft margin).
Dual.
Crucially, the data enters only through inner products \(\vec x_i \cdot \vec x_j\).
The kernel trick¶
Replace \(\vec x_i\cdot\vec x_j\) by \(k(\vec x_i,\vec x_j) = \langle\phi(\vec x_i),\phi(\vec x_j)\rangle\) for some feature map \(\phi\) into a (possibly infinite-dimensional) space. You never need to compute \(\phi\) explicitly — only the kernel values.
Prediction.
Mercer's condition. \(k\) is a valid kernel iff the Gram matrix \(K_{ij} = k(\vec x_i,\vec x_j)\) is symmetric positive semi-definite for every finite dataset.
Classical kernels.
| Kernel | Formula |
|---|---|
| Linear | \(\vec x\cdot\vec x'\) |
| Polynomial | \((\vec x\cdot\vec x' + c)^{d}\) |
| RBF (Gaussian) | \(\exp\big(-\gamma\Vert \vec x-\vec x'\Vert ^2\big)\) |
| Sigmoid | \(\tanh(\kappa\,\vec x\cdot\vec x' + c)\) |
27.3 The Quantum Kernel¶
Definition. With a quantum feature map \(|\phi(\vec x)\rangle = U_{\phi}(\vec x)|0\rangle^{\otimes n}\),
Valid kernel? Yes: \(K_{ij} = |\langle\phi_i|\phi_j\rangle|^2 = \mathrm{Tr}(\rho_i\rho_j)\) with \(\rho_i = |\phi_i\rangle\langle\phi_i|\), which is a Gram matrix of density matrices under the Hilbert–Schmidt inner product and is therefore PSD ✓.
Properties. \(k_Q(\vec x,\vec x) = 1\); \(0\le k_Q\le 1\); symmetric.
The strategic idea. The feature space is \(\mathbb{C}^{2^n}\) — exponentially large in the qubit count. If \(U_\phi\) is chosen so that the induced kernel is hard to evaluate classically, the quantum computer provides a kernel no classical machine can compute. That is the QSVM advantage argument.
Circuit 1 — the compute–uncompute (fidelity) method¶
|0>^n --[ U_phi(x') ]--[ U_phi(x)^dagger ]--[M]^n--> count outcome 0^n
Estimate: run \(S\) shots, count how often all-zeros appears, divide by \(S\).
| Property | Value |
|---|---|
| Qubits | \(n\) |
| Depth | \(2\times\) depth of \(U_\phi\) |
| Statistical error | \(\sqrt{k(1-k)/S}\) |
The standard method — implemented as FidelityQuantumKernel in Qiskit.
Circuit 2 — the swap test¶
ancilla |0> --[H]--------*--------[H]--[M]
|
register |phi(x)> -------x--------
|
register |phi(x')> -------x-------- (controlled SWAP = Fredkin)
Derivation. After the first \(H\) and the controlled SWAP:
The \(|0\rangle\) branch has squared norm \(\frac{1}{4}\cdot 2(1 + |\langle\phi|\phi'\rangle|^2)\), giving the stated probability. \(\blacksquare\)
| Compute–uncompute | Swap test | |
|---|---|---|
| Qubits | \(n\) | \(2n+1\) |
| Depth | \(2\times\) | \(1\times\) + \(n\) Fredkins |
| Readout | \(n\)-bit all-zeros | 1 ancilla bit |
| Preferred on NISQ | yes (fewer qubits) | when depth is the constraint |
27.4 The QSVM Pipeline¶
1. Choose feature map U_phi (e.g. ZZFeatureMap, reps=2)
2. Build the training kernel matrix:
K_ij = k_Q(x_i, x_j) for all i <= j -> M(M+1)/2 circuits
3. Feed K into a CLASSICAL SVM solver (e.g. libsvm) -> alpha, b
4. Build the test kernel: K'_ij = k_Q(x_test_i, x_train_j) -> M_test * M circuits
5. Predict: f(x) = sign( sum_i alpha_i y_i K'(x, x_i) + b )
Only step 2 and step 4 are quantum. The optimisation itself is entirely classical and convex — QSVM has no barren-plateau problem and no local minima, which is a genuine advantage over variational methods (L28, L29).
Cost¶
| Stage | Circuit evaluations |
|---|---|
| Training kernel | \(\frac{M(M+1)}{2}\times S\) shots |
| Test kernel | \(M_{\text{test}}\times M\times S\) shots |
For \(M = 100\), \(S = 8192\): \(5050 \times 8192 \approx 4.1\times10^{7}\) shots. At \(10^{4}\) shots/second on cloud hardware, that is over an hour — and this is only 100 training points.
Classical SVMs also form \(O(M^2)\) kernel entries, but each costs nanoseconds rather than seconds.
Shot noise and kernel-matrix integrity¶
Each \(K_{ij}\) carries statistical error \(\epsilon \approx \sqrt{k(1-k)/S}\). With \(S = 8192\) and \(k\approx0.5\), \(\epsilon \approx 0.0055\).
Two consequences.
- Noise can destroy positive semi-definiteness. A noisy \(K\) may have small negative eigenvalues, which breaks the convexity the SVM solver relies on. Fix: project onto the PSD cone by clipping negative eigenvalues to zero, or add \(\delta I\) to the diagonal.
- Precision requirement scales with \(M\). To keep the solution stable, \(\epsilon = O(1/M)\) is needed, so \(S = O(M^2)\) shots per entry, giving \(O(M^4)\) total shots. This is the strongest scaling objection to QSVM.
27.5 Does It Actually Help? An Honest Assessment¶
The positive result (Liu, Arunachalam, Temme, 2021). There exists a constructed classification problem, based on the discrete logarithm, for which a quantum kernel gives a provable exponential advantage over any classical learner. Existence is settled.
The negative results.
- Product feature maps are classically simulable. The kernel factorises into \(\prod_j\cos^2\!\big(\frac{x_j-x_j'}{2}\big)\) (L26, Problem 2) — computable in \(O(d)\) classically. Entanglement in \(U_\phi\) is necessary.
- Exponential concentration. For expressive random feature maps, \(k_Q(\vec x,\vec x')\) concentrates around a constant \(\sim2^{-n}\) for all \(\vec x\ne\vec x'\): the kernel matrix approaches the identity, and the model memorises the training set and generalises terribly. Distinguishing entries then requires \(S = O(2^{n})\) shots. This is the kernel-method analogue of barren plateaus.
- Huang et al. (2021). Given the same data-access assumptions, classical ML models match quantum kernel methods on most practical datasets.
The design tension, stated plainly.
Useful quantum kernels must sit in a narrow band, and finding that band for real problems is an open research question. Present QSVM to students as scientifically interesting and pedagogically essential, not as a deployed technology.
27.6 Solved Problems¶
Problem 1 — Computing a quantum kernel by hand¶
Using single-qubit \(R_y\) angle encoding, compute \(k_Q(x,x')\) for \(x = 0\), \(x' = \pi/2\). Verify with the fidelity circuit.
Solution.
Check with the general formula \(k_Q = \cos^2\!\big(\frac{x-x'}{2}\big)\):
Fidelity circuit. Apply \(R_y(\pi/2)\) then \(R_y(0)^\dagger = I\), giving \(|+\rangle\); measuring gives \(0\) with probability \(\frac12\) ✓.
Problem 2 — Building and checking a 3×3 kernel matrix¶
Three 1-D data points \(x_1 = 0\), \(x_2 = \pi/2\), \(x_3 = \pi\) with \(R_y\) encoding. Build \(K\), check PSD, and comment on separability.
Solution.
Using \(k(x,x') = \cos^2\!\big(\frac{x-x'}{2}\big)\):
PSD check. Eigenvalues of this symmetric tridiagonal matrix: the pattern \(\mathrm{tridiag}(0.5,1,0.5)\) of size 3 has eigenvalues \(1 + 2(0.5)\cos\frac{k\pi}{4}\) for \(k = 1,2,3\):
All positive ⟹ positive definite ✓, so \(K\) is a valid kernel matrix.
Separability comment. \(x_1\) and \(x_3\) are orthogonal (\(k_{13} = 0\)) — the encoding maps them to \(|0\rangle\) and \(|1\rangle\), antipodal on the Bloch sphere. \(x_2\) sits exactly between them. So the encoding maps the interval \([0,\pi]\) onto a great arc of the Bloch sphere, preserving the geometry faithfully. This kernel is essentially a squared-cosine similarity — smooth, well-behaved, and entirely classical.
Problem 3 — Shot budget and wall-clock time¶
A QSVM has 200 training and 50 test samples, 4096 shots per kernel entry, and the device runs 5000 shots/second. Compute the total shots and runtime.
Solution.
Training kernel (symmetric, diagonal known to be 1):
Test kernel:
Total:
Runtime:
Plus queueing. On shared cloud hardware, job latency typically dominates: 30 000 separate circuit jobs at even 1 second of overhead each adds another 8 hours.
Scaling. Doubling to 400 training samples quadruples the training kernel cost to 27 hours.
Mitigations in use: kernel-matrix sparsification (compute only near-neighbour entries), Nyström low-rank approximation, and batched circuit submission.
Problem 4 — Kernel concentration, quantified¶
For a random \(n\)-qubit feature map, \(\mathbb{E}[k_Q] \approx 2^{-n}\) for distinct points. How many shots are needed to distinguish \(k = 2^{-n}\) from \(k = 2\times2^{-n}\) at \(n = 20\)? Interpret.
Solution.
At \(n=20\): \(k_1 = 2^{-20} = 9.54\times10^{-7}\), \(k_2 = 1.91\times10^{-6}\).
Difference: \(\Delta = 9.54\times10^{-7}\).
For a Bernoulli estimate with tiny \(p\), \(\mathrm{SE} \approx \sqrt{p/S}\). To resolve \(\Delta\) at 2 standard errors:
Per kernel entry. For a 100-sample dataset that is \(4950\times4.2\times10^{6} = 2\times10^{10}\) shots — over 60 years at 10 kHz.
Interpretation: exponential concentration is fatal. The kernel matrix becomes \(K \approx I\), meaning:
- Every point is "orthogonal" to every other in feature space.
- The SVM can fit the training data perfectly (\(\alpha_i\) nonzero for all \(i\)) but has learned nothing generalisable — the model is pure memorisation.
- Test predictions default to \(\mathrm{sign}(b)\), i.e. the majority class.
Design response. Restrict the feature map's expressivity: shallow circuits, limited entanglement, problem-informed structure. Concentration is the kernel-method form of the barren plateau (L29), and it comes from the same source — the exponential dimension of Hilbert space.
Problem 5 — Comparing quantum and classical kernels on XOR¶
The XOR dataset: \((0,0)\to-1\), \((1,1)\to-1\), \((0,1)\to+1\), \((1,0)\to+1\). Show that (a) a linear kernel fails, (b) a product angle-encoding quantum kernel also fails, (c) a ZZ feature map succeeds.
Solution.
(a) Linear kernel. XOR is the textbook non-linearly-separable problem: no hyperplane \(w_1x_1+w_2x_2+b\) separates \(\{(0,0),(1,1)\}\) from \(\{(0,1),(1,0)\}\). Attempting it gives the contradictory system
Adding the last two: \(w_1+w_2+2b > 0\); the second gives \(w_1+w_2+b<0\), so \(b > 0\) — contradicting the first. Fails. ✗
(b) Product angle encoding. Scale inputs by \(\pi\) so \(0\to0\) and \(1\to\pi\). The kernel is
So \(K = I\) — every distinct pair is orthogonal. The SVM memorises the four points but has no structure to generalise from; a fifth point would be classified arbitrarily.
More fundamentally, the feature map is a product, so the model is a sum of independent per-feature terms. XOR requires the interaction term \(x_1x_2\), which a product map cannot represent. ✗
(c) ZZ feature map. Add the entangling term
The \(Z_1Z_2\) term makes the state's phase depend on the product of the features. Concretely, the relative phase acquired distinguishes the "same" pairs \(\{(0,0),(1,1)\}\) from the "different" pairs \(\{(0,1),(1,0)\}\), exactly the XOR structure.
The resulting kernel matrix has the block structure
which is separable in feature space. Succeeds. ✓
The lesson, in one sentence. Entanglement in the feature map is what lets a quantum kernel represent feature interactions — precisely analogous to how the classical polynomial kernel \((\vec x\cdot\vec x'+1)^2\) solves XOR by introducing the \(x_1x_2\) monomial.
Honest footnote: the classical RBF or degree-2 polynomial kernel also solves XOR, instantly. The quantum kernel is not better here — it is a demonstration that entangling maps have the right kind of expressivity.
27.7 Practice Problems¶
- Compute \(k_Q(0, \pi)\) for single-qubit \(R_y\) encoding. [Ans: 0]
- Show that \(K_{ij} = \mathrm{Tr}(\rho_i\rho_j)\) is always PSD.
- Total shots for \(M=50\) training, 4096 shots/entry? [Ans: \(\approx5.0\times10^{6}\)]
- Derive \(\Pr[\text{ancilla}=0] = \frac{1+|\langle\phi|\phi'\rangle|^2}{2}\) for the swap test.
- Why does a product feature map give no quantum advantage? Answer in two sentences.
- Given noisy \(K\) with eigenvalues \((2.1, 0.8, -0.03)\), describe two repairs.
- Compute the qubit and depth cost of the swap test versus compute–uncompute for \(n=8\).
27.8 Summary¶
- SVMs depend on data only through inner products, so any PSD kernel can be substituted (the kernel trick).
- Quantum kernel: \(k_Q(\vec x,\vec x') = |\langle\phi(\vec x)|\phi(\vec x')\rangle|^2\), always a valid Mercer kernel, with an exponentially large feature space \(\mathbb{C}^{2^n}\).
- Two estimation circuits: compute–uncompute (measure \(\Pr[0^n]\), \(n\) qubits, double depth) and the swap test (\(2n+1\) qubits, one ancilla bit).
- QSVM = quantum kernel matrix + classical convex SVM solver. No barren plateaus, no local minima — a real structural advantage over variational models.
- Cost is \(O(M^2)\) kernel entries and, for stability, \(O(M^4)\) total shots — limiting QSVM to a few hundred samples on current hardware.
- Honest verdict: a provable exponential advantage exists for a constructed problem, but product maps are classically simulable and highly expressive maps suffer exponential kernel concentration (\(k\to2^{-n}\), \(K\to I\), no generalisation). Useful kernels live in a narrow band that is still being mapped.
Next lesson: L28 — The Variational Quantum Classifier.
Practise now: unit3-qml-lab.html → Kernel Lab: choose a feature map and dataset, build the
kernel matrix, view its heat map and eigenvalues, and watch the decision boundary form.