Chapter 9: Quantum Support Vector Machines¶
The quantum support vector machine (QSVM) was one of the first QML algorithms to claim an exponential speedup over classical methods. This claim has since been refined, challenged by dequantization results, and recast in the quantum kernel framework. This chapter traces the full story: the original HHL-based QSVM, the quantum kernel SVM, and an honest accounting of when — and when not — to expect quantum advantage.
Learning Objectives
By the end of this chapter, you will be able to:
-
Explain the HHL-based QSVM and its assumptions
-
Implement a quantum kernel SVM using PennyLane
-
Apply multi-class QSVM strategies
-
Critically evaluate QSVM vs. classical SVM benchmarks
-
Understand dequantization results and their implications for QSVM
9.1 The HHL-Based QSVM (Rebentrost 2014)¶
Rebentrost, Mohseni, and Lloyd (2014) (Rebentrost et al. 2014) proposed using HHL to solve the SVM kernel equation:
Claimed complexity: \(O(\log(N) \kappa^2/\epsilon)\) for training (vs. \(O(N^2)\) classically).
Prediction: Quantum state \(|\boldsymbol{\alpha}\rangle\propto\sum_i\alpha_i|i\rangle\); classify new point \(|\mathbf{x}\rangle\) via inner product estimation.
Warning
Critical assumptions for HHL-QSVM speedup:
-
qRAM for loading classical data in \(O(\log N)\) time
-
Efficient quantum state tomography (contradicts quantum advantage)
-
Low condition number \(\kappa = O(\text{polylog}(N))\)
-
Only need the quantum state \(|\boldsymbol{\alpha}\rangle\), not all components
Assumption 1 requires hardware not yet available at scale. Assumption 2 is exponentially expensive. Most practical problems violate assumption 3.
9.2 Dequantization of QSVM¶
Tang (2019) (Tang 2019) showed that under the same \(\ell^2\)-norm sampling assumption used by HHL-QSVM:
A classical algorithm achieves the same asymptotic performance as HHL-QSVM up to polynomial factors in \(\kappa\) and \(\epsilon\).
The key insight: \(\ell^2\)-norm sampling (classical) mimics amplitude estimation (quantum). With qRAM, the quantum algorithm’s data loading advantage also provides a classical algorithm with fast sampling.
Research Highlight: Ewin Tang’s Dequantization (2019)
Ewin Tang, then an undergraduate at UT Austin, proved that quantum-inspired classical algorithms can achieve the same asymptotic runtime as the HHL-QSVM for recommendation systems (which maps to QSVM via kernel equation). This “dequantization” result was awarded the STOC 2022 Best Paper. It does not eliminate quantum advantage but forces a reassessment: quantum advantage requires problems where even \(\ell^2\)-norm sampling is difficult classically.
9.3 Quantum Kernel SVM (Practical Approach)¶
The practical QSVM (Havlíček et al. 2019): use a quantum device to compute \(k_Q(\mathbf{x}_i, \mathbf{x}_j)\) and solve the SVM optimization classically.
Algorithm:
Algorithm: Quantum Kernel SVM (QKSVM)
Input: Data \(\{(\mathbf{x}_i,y_i)\}_{i=1}^N\), feature map \(U_\phi\), cost \(C\).
Output: SVM classifier \(f(\mathbf{x}) = \text{sign}(\sum_i\alpha_iy_ik_Q(\mathbf{x},\mathbf{x}_i)+b)\).
-
Kernel evaluation (quantum): compute \(K_{ij} = k_Q(\mathbf{x}_i,\mathbf{x}_j)\) for all \(i,j\) using overlap circuits. Requires \(O(N^2)\) circuit runs.
-
SVM training (classical): solve the dual QP (4.6) with \(K_{ij}\) as the kernel matrix. Cost: \(O(N^3)\) (or \(O(N^2)\) via SMO).
-
Prediction: \(f(\mathbf{x}) = \text{sign}\bigl(\sum_i\alpha_iy_ik_Q(\mathbf{x},\mathbf{x}_i)+b\bigr)\) requires \(O(N)\) kernel evaluations.
Total complexity: \(O(N^2)\) quantum + \(O(N^3)\) classical.
Solved Example 9.1
Problem: Build a QKSVM for 4-point XOR-like data: \(\mathcal{D} = \{([0,0]^\top,{+1}),([1,1]^\top,{+1}),([0,1]^\top,{-1}),([1,0]^\top,{-1})\}\).
Solution: Use angle encoding on 2 qubits: \(|\phi(\mathbf{x})\rangle = R_y(x_1)|0\rangle \otimes R_y(x_2)|0\rangle\). Compute \(K_{ij}=k_Q(\mathbf{x}_i,\mathbf{x}_j)=\cos^2\!\big(\frac{x_1^i-x_1^j}{2}\big)\cos^2\!\big(\frac{x_2^i-x_2^j}{2}\big)\).
\(K = \begin{pmatrix}1 & K_{12} & K_{13} & K_{14}\\ & 1 & K_{23} & K_{24}\\ & & 1 & K_{34}\\ & & & 1\end{pmatrix}\)
\(K_{12} = \cos^2(0)\cos^2(0)=1\), \(K_{13}=\cos^2(0)\cos^2(0.5)=0.770\), \(K_{14}=\cos^2(0.5)\cos^2(0)=0.770\), \(K_{23}=0.770\), \(K_{24}=0.770\), \(K_{34}=1\).
This kernel doesn’t separate XOR — we need an entangling feature map (e.g., IQP) to achieve non-linear separation.
9.4 Multi-Class Quantum SVM¶
For \(C>2\) classes, extend via:
-
One-vs-All (OvA): Train \(C\) binary classifiers \(f_c(\mathbf{x}) = k_Q\)-SVM for class \(c\) vs. rest. Predict \(\hat{y} = \operatorname{argmax}_c f_c(\mathbf{x})\).
-
One-vs-One (OvO): Train \(\binom{C}{2}\) classifiers for each pair. Predict by majority vote.
-
Direct multi-class: Measure multi-outcome observable \(\hat{O}\) with \(C\) distinct eigenvalues; each class maps to one eigenvalue.
9.5 Benchmarking: Fair Comparison¶
Research Highlight: Bowles et al. (2024): Fair Benchmarking
A 2024 study (Bowles et al. 2024) systematically compared quantum kernel SVMs against classical methods on 12 datasets under fair conditions (same training data, same preprocessing, same computational budget). Key findings:
-
Quantum kernels do not outperform classical RBF-SVM on any real dataset
-
Performance gap grows with dataset size (classical scales better)
-
Quantum kernels perform comparably only on tiny datasets (\(N<100\))
-
Constructed datasets (not naturally occurring) show quantum kernel advantage
Implication: Real quantum advantage for natural datasets remains elusive. Practitioners should use quantum kernels as a research tool, not a production shortcut.
import pennylane as qml
import numpy as np
from sklearn.svm import SVC
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report
# IQP-style quantum kernel
n_qubits = 4
dev = qml.device("default.qubit", wires=n_qubits)
@qml.qnode(dev)
def iqp_kernel_circuit(x1, x2):
"""IQP feature map overlap circuit."""
def feature_map(x):
qml.broadcast(qml.Hadamard, wires=range(n_qubits), pattern="single")
for i in range(n_qubits):
qml.RZ(x[i], wires=i)
for i in range(n_qubits-1):
qml.IsingZZ((np.pi-x[i])*(np.pi-x[i+1]), wires=[i,i+1])
qml.broadcast(qml.Hadamard, wires=range(n_qubits), pattern="single")
feature_map(x1)
qml.adjoint(feature_map)(x2)
return qml.probs(wires=range(n_qubits))
def qsvm_kernel_matrix(X1, X2):
"""Full N1 x N2 quantum kernel matrix."""
K = np.zeros((len(X1), len(X2)))
for i, x1 in enumerate(X1):
for j, x2 in enumerate(X2):
K[i, j] = iqp_kernel_circuit(x1, x2)[0]
return K
# Load and prepare Iris (3-class, use first 2)
X, y = load_iris(return_X_y=True)
X, y = X[y < 2, :4], y[y < 2] # binary subset
scaler = StandardScaler()
X = scaler.fit_transform(X)
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.3, random_state=42)
# Quantum kernel SVM
print("Computing quantum kernel matrices...")
K_train = qsvm_kernel_matrix(X_train[:20], X_train[:20]) # demo subset
K_test = qsvm_kernel_matrix(X_test[:10], X_train[:20])
qsvm = SVC(kernel='precomputed', C=1.0)
qsvm.fit(K_train, y_train[:20])
preds = qsvm.predict(K_test)
print(f"QSVM Accuracy: {np.mean(preds == y_test[:10]):.3f}")
# Classical baseline
from sklearn.svm import SVC as ClassicalSVC
classical_svm = ClassicalSVC(kernel='rbf', C=1.0)
classical_svm.fit(X_train[:20], y_train[:20])
print(f"Classical SVM: {classical_svm.score(X_test[:10], y_test[:10]):.3f}")
9.6 Chapter Summary¶
Chapter Summary
-
HHL-QSVM: Exponential speedup claim (Rebentrost 2014) requires qRAM and low condition number. Practical relevance limited.
-
Dequantization: Tang (2019) showed classical algorithms can match HHL-QSVM under the same \(\ell^2\)-norm sampling assumption.
-
QKSVM (practical): Quantum kernel \(\to\) classical SVM optimization. No classical subroutine in the quantum part; \(O(N^2)\) circuit evaluations needed.
-
Multi-class: OvA/OvO strategies standard; direct multi-class via multi-outcome measurements is also possible.
-
Benchmarking: Fair comparisons (Bowles 2024) show no quantum advantage on real datasets. Advantage exists on constructed problems.
Exercises
Exercise . Write out the kernel equation (9.1) for \(N=3\) training points. Identify which matrices appear and their sizes.
Exercise . Show that the quantum kernel SVM decision function \(f(\mathbf{x}) = \sum_i\alpha_iy_ik_Q(\mathbf{x},\mathbf{x}_i)+b\) lies in the RKHS of the kernel \(k_Q\) (representer theorem).
Exercise . Under what conditions does the condition number \(\kappa\) of the SVM kernel matrix grow with \(N\)? Argue why this is problematic for the HHL-QSVM speedup.
Exercise . Compare QKSVM, classical RBF-SVM, and polynomial-kernel SVM on the Breast Cancer Wisconsin dataset. Report accuracy, training time, and kernel matrix condition number.
Further Reading
-
Rebentrost, Mohseni & Lloyd (2014) (Rebentrost et al. 2014) — HHL-QSVM
-
Havlíček et al. (2019) (Havlíček et al. 2019) — quantum kernel SVM on IBM hardware
-
Tang (2019) (Tang 2019) — dequantization of quantum recommendation systems
-
Bowles et al. (2024) (Bowles et al. 2024) — fair benchmarking of quantum classifiers