Skip to content

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:

  1. Recall the SVM primal and dual problems and the kernel trick.
  2. Define the quantum kernel and describe the two circuits that estimate it.
  3. Assemble the complete QSVM pipeline and count its circuit executions.
  4. Analyse the \(O(M^2)\) kernel-matrix cost and the shot-noise requirement.
  5. 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).

\[ \min_{\vec w, b, \xi} \ \frac12\|\vec w\|^2 + C\sum_{i=1}^{M}\xi_i \]
\[ \text{s.t. } y_i(\vec w\cdot\vec x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0 \]

Dual.

\[ \max_{\vec\alpha}\ \sum_{i=1}^{M}\alpha_i - \frac12\sum_{i,j=1}^{M}\alpha_i\alpha_j y_iy_j\, \underbrace{\vec x_i\cdot\vec x_j}_{\text{only via inner products}} \]
\[ \text{s.t. } 0\le\alpha_i\le C, \quad \sum_i\alpha_iy_i = 0 \]

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.

\[ f(\vec x) = \mathrm{sign}\left(\sum_{i=1}^{M}\alpha_iy_i\,k(\vec x_i,\vec x) + b\right) \]

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}\),

\[ \boxed{\ k_Q(\vec x,\vec x') = \big|\langle\phi(\vec x)|\phi(\vec x')\rangle\big|^{2} = \big|\langle0|U_{\phi}^{\dagger}(\vec x)\,U_{\phi}(\vec x')|0\rangle\big|^{2}\ } \]

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
\[ \Pr[0^n] = \big|\langle0|U_\phi^\dagger(\vec x)U_\phi(\vec x')|0\rangle\big|^{2} = k_Q(\vec x,\vec x') \]

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)
\[ \Pr[\text{ancilla}=0] = \frac{1 + |\langle\phi(\vec x)|\phi(\vec x')\rangle|^{2}}{2} = \frac{1 + k_Q}{2} \]
\[ \Longrightarrow\quad k_Q = 2\Pr[0] - 1 \]

Derivation. After the first \(H\) and the controlled SWAP:

\[ \tfrac12\Big[|0\rangle\big(|\phi\rangle|\phi'\rangle + |\phi'\rangle|\phi\rangle\big) + |1\rangle\big(|\phi\rangle|\phi'\rangle - |\phi'\rangle|\phi\rangle\big)\Big] \]

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.

\[ \boxed{\ \textbf{The } O(M^2) \textbf{ kernel-matrix cost is the practical ceiling on QSVM.}\ } \]

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.

  1. 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.
  2. 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.

\[ \text{too simple} \Rightarrow \text{classically simulable}; \qquad \text{too expressive} \Rightarrow \text{kernel concentrates, no generalisation} \]

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.

\[ |\phi(0)\rangle = R_y(0)|0\rangle = |0\rangle \]
\[ |\phi(\pi/2)\rangle = R_y(\pi/2)|0\rangle = \cos\tfrac{\pi}{4}|0\rangle + \sin\tfrac{\pi}{4}|1\rangle = |+\rangle \]
\[ \langle\phi(0)|\phi(\pi/2)\rangle = \langle0|+\rangle = \tfrac{1}{\sqrt2} \]
\[ k_Q = \left|\tfrac{1}{\sqrt2}\right|^{2} = \mathbf{0.5} \]

Check with the general formula \(k_Q = \cos^2\!\big(\frac{x-x'}{2}\big)\):

\[ \cos^2\!\left(\frac{0 - \pi/2}{2}\right) = \cos^2\!\left(-\frac{\pi}{4}\right) = \frac12 \ \checkmark \]

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)\):

\[ k_{11}=k_{22}=k_{33}=1 \]
\[ k_{12} = \cos^2(\pi/4) = 0.5, \qquad k_{23} = \cos^2(-\pi/4) = 0.5 \]
\[ k_{13} = \cos^2(-\pi/2) = 0 \]
\[ K = \begin{pmatrix} 1 & 0.5 & 0 \\ 0.5 & 1 & 0.5 \\ 0 & 0.5 & 1\end{pmatrix} \]

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\):

\[ \lambda = 1 + \cos\tfrac{\pi}{4},\ 1 + \cos\tfrac{\pi}{2},\ 1+\cos\tfrac{3\pi}{4} = 1.7071,\ 1.0,\ 0.2929 \]

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):

\[ \frac{M(M-1)}{2} = \frac{200\times199}{2} = 19{,}900 \ \text{entries} \]
\[ 19{,}900\times4096 = 8.15\times10^{7}\ \text{shots} \]

Test kernel:

\[ 50\times200 = 10{,}000 \ \text{entries} \ \Longrightarrow\ 10{,}000\times4096 = 4.10\times10^{7}\ \text{shots} \]

Total:

\[ 8.15\times10^{7} + 4.10\times10^{7} = \mathbf{1.22\times10^{8}\ \text{shots}} \]

Runtime:

\[ t = \frac{1.22\times10^{8}}{5000} = 24{,}500\ \mathrm{s} = \mathbf{6.8\ \text{hours}} \]

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.

\[ \boxed{\ \text{QSVM is limited to a few hundred samples on current hardware.}\ } \]

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:

\[ 2\sqrt{\frac{k_1}{S}} \le \Delta \ \Longrightarrow\ S \ge \frac{4k_1}{\Delta^{2}} = \frac{4\times9.54\times10^{-7}}{(9.54\times10^{-7})^{2}} \]
\[ S \ge \frac{3.82\times10^{-6}}{9.10\times10^{-13}} = \mathbf{4.2\times10^{6}\ \text{shots per entry}} \]

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

\[ b < 0,\quad w_1+w_2+b<0,\quad w_2+b>0,\quad w_1+b>0 . \]

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

\[ k(\vec x,\vec x') = \prod_{j=1}^{2}\cos^{2}\!\left(\frac{\pi(x_j - x'_j)}{2}\right) = \prod_j \begin{cases}1 & x_j = x'_j\\ 0 & x_j\ne x'_j\end{cases} \]

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

\[ U_{\phi}(\vec x) = \exp\Big(i\,\phi_{12}(\vec x)\,Z_1Z_2\Big)\,\exp\Big(i\sum_j x_jZ_j\Big)H^{\otimes2}, \qquad \phi_{12} = (\pi-x_1)(\pi-x_2) . \]

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

\[ K \approx \begin{pmatrix} 1 & \cdot & \cdot & \cdot\\ \cdot & 1 & \cdot & \cdot \\ \cdot&\cdot&1&\cdot\\ \cdot&\cdot&\cdot&1\end{pmatrix} \ \text{with large within-class entries and small across-class entries,} \]

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

  1. Compute \(k_Q(0, \pi)\) for single-qubit \(R_y\) encoding. [Ans: 0]
  2. Show that \(K_{ij} = \mathrm{Tr}(\rho_i\rho_j)\) is always PSD.
  3. Total shots for \(M=50\) training, 4096 shots/entry? [Ans: \(\approx5.0\times10^{6}\)]
  4. Derive \(\Pr[\text{ancilla}=0] = \frac{1+|\langle\phi|\phi'\rangle|^2}{2}\) for the swap test.
  5. Why does a product feature map give no quantum advantage? Answer in two sentences.
  6. Given noisy \(K\) with eigenvalues \((2.1, 0.8, -0.03)\), describe two repairs.
  7. 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.