The kernel trick is one of the most elegant ideas in machine learning. Support vector machines find a separating hyperplane between two classes — but the hyperplane lives not in the original data space, where classes are often tangled together, but in a high-dimensional feature space reached by an explicit mapping φ(x)\varphi(x). The kernel trick bypasses the need to compute φ(x)\varphi(x) at all: it only requires the inner product ⟨φ(x),φ(x′)⟩\langle \varphi(x), \varphi(x') \rangle, which for many useful feature maps can be computed directly as a simple function of xx and x′x'. The feature space can be infinite-dimensional; the computation stays tractable.

Quantum computers introduce a new possibility. A quantum circuit U(x)U(x) acting on nn qubits maps classical data xx into a quantum state ∣φ(x)⟩|\varphi(x)\rangle in a Hilbert space of dimension 2n2^n — exponentially large in the number of qubits. Inner products in this space, ⟨φ(x′)∣φ(x)⟩\langle \varphi(x')|\varphi(x)\rangle, are the transition amplitudes of quantum circuits and can be estimated by running U†(x′)U(x)U^\dagger(x')U(x) on a quantum computer and measuring the probability of the all-zeros outcome. If this quantum inner product captures structure in the data that no efficiently computable classical kernel can, and if computing it classically is hard, there is a potential quantum advantage in machine learning.

Whether that potential translates into a practical advantage on any real dataset is the central open question in quantum kernel methods.

Key Concepts in This Article

Kernel Function

k(x, x') = ⟨φ(x), φ(x')⟩ — the inner product between feature maps of two data points. The kernel trick evaluates this without explicitly computing φ(x), making SVMs tractable even in infinite-dimensional feature spaces.

Quantum Feature Map

A parametrised quantum circuit U(x) that encodes classical data x as a quantum state |φ(x)⟩ = U(x)|0ⁿ⟩ in a 2ⁿ-dimensional Hilbert space. The quantum kernel is k_Q(x, x') = |⟨φ(x')|φ(x)⟩|².

Kernel Matrix

The n×n matrix K where Kᵢⱼ = k(xᵢ, xⱼ) over all training pairs. The SVM optimisation requires only K, not the individual feature vectors. For a quantum kernel, estimating K requires O(n²) quantum circuit executions.

Quantum Advantage Condition

Quantum kernel advantage requires two simultaneous conditions: the kernel must be hard to estimate classically, AND the data must have structure that the quantum kernel captures better than any efficiently computable classical kernel. Both are required.

Classical SVMs and the Kernel Trick

A support vector machine solves a binary classification task by finding the maximum-margin hyperplane separating two classes. When data is not linearly separable in the input space ℝᵈ, the kernel trick allows SVMs to operate in a much richer feature space without the computational cost of explicitly computing the feature vectors.

KERNEL TRICK — CLASSICAL vs QUANTUM CLASSICAL KERNEL not linearly separable Classical kernel: k(x,x') = ⟨φ(x),φ(x')⟩ RBF: exp(−||x−x'||²/2σ²) feature space: ∞-dimensional computed in O(d) time QUANTUM KERNEL U(x) encoding circuit n qubits |φ(x)⟩ ∈ ℋ dim = 2ⁿ k_Q(x,x') = |⟨φ(x')|φ(x)⟩|² = P(|0⟩ | U†(x')U(x)) feature space: 2ⁿ-dimensional estimated via quantum circuit
Figure 1 — Classical vs quantum kernel. A classical kernel (e.g., RBF) implicitly computes inner products in a potentially infinite-dimensional feature space in O(d) time. A quantum kernel maps data to a 2ⁿ-dimensional Hilbert space via an n-qubit encoding circuit U(x), and estimates the inner product |⟨φ(x')|φ(x)⟩|² by running the circuit U†(x')U(x) and measuring the all-zeros probability. The quantum feature space is exponentially larger, but estimating each kernel entry requires quantum circuit executions with finite shot noise.

The SVM dual problem depends only on the kernel matrix entries k(xi,xj)k(x_i, x_j): it never requires the feature vectors φ(xi)\varphi(x_i) explicitly. Once the kernel matrix KK is computed, the SVM optimisation is a classical quadratic programme — convex, efficiently solvable, and well-understood theoretically.

The power of the kernel trick is that k(x,x′)=(x⋅x′)2k(x, x') = (x \cdot x')^2 for the polynomial kernel of degree 2, for instance, implicitly computes inner products in a feature space of dimension O(d2)O(d^2) without ever constructing a d2d^2-dimensional vector. For the RBF kernel, the feature space is infinite-dimensional.

Quantum Feature Maps: Encoding Data Into Hilbert Space

A quantum feature map is a parametrised quantum circuit U(x) that encodes classical data x ∈ ℝᵈ as a quantum state:

∣φ(x)⟩=U(x)∣0n⟩|\varphi(x)\rangle = U(x)|0^n\rangle

The resulting state lives in a 2ⁿ-dimensional Hilbert space. For n = 20 qubits, this is over a million dimensions; for n = 50, it is a quadrillion. The appeal is obvious — and the danger is equally obvious, as we will see.

ZZ FEATURE MAP — DATA ENCODING CIRCUIT (n=3 QUBITS) |0⟩ |0⟩ |0⟩ H⊗³ uniform superpos. Pauli rotations Rz(2x₀) Rz(2x₁) Rz(2x₂) ZZ entangling Rzz(2φ₀₁) Rzz(2φ₁₂) φᵢⱼ = (π−xᵢ)(π−xⱼ) repeat L layers |φ(x)⟩ quantum state in 2ⁿ = 8 dimensions encodes non-linear correlations in x ① SUPERPOS. ② DATA ENCODING ③ ENTANGLEMENT
Figure 2 — The ZZ feature map used by Havlíček et al. (2019). Three stages: a Hadamard layer creates uniform superposition; data-dependent single-qubit Rz rotations encode each feature; ZZ two-qubit interactions encode pairwise products φᵢⱼ = (π−xᵢ)(π−xⱼ), creating non-linear correlations between features. Repeating L layers produces a state whose amplitude structure depends on x in a way that is believed to be classically hard to simulate for sufficiently entangled circuits.

The key design principle for quantum feature maps is non-linearity through entanglement. Single-qubit rotations alone (Rz(xᵢ) on qubit i) encode each feature independently — the resulting kernel is separable and can be computed efficiently classically. The entangling layers (ZZ interactions between qubit pairs) introduce correlations between features: the circuit encodes not just xᵢ but products like xᵢxⱼ, (xᵢ)²(xⱼ), and higher-order terms in the amplitudes. With L layers of such interactions, the feature map encodes polynomials of degree up to L·n in the original features — an exponentially rich function class.

Evaluating the Quantum Kernel

QUANTUM KERNEL EVALUATION — k_Q(x, x') = P(|000⟩) |0⟩ |0⟩ |0⟩ U(x) encode x → |φ(x)⟩ U†(x') inverse encode x' uncompute |φ(x')⟩ Measure P(|000...0⟩) = k_Q(x,x') WHY THIS WORKS State after U†(x')U(x)|0ⁿ⟩: = U†(x') |φ(x)⟩ P(|0ⁿ⟩) = |⟨0ⁿ|U†(x')U(x)|0ⁿ⟩|² = |⟨φ(x')|φ(x)⟩|² = k_Q(x, x') Estimated with T shots → precision O(1/√T)
Figure 3 — Quantum kernel evaluation circuit. To compute k_Q(x, x'), first apply U(x) to |0ⁿ⟩ to prepare |φ(x)⟩, then apply the inverse circuit U†(x'). The probability of measuring the all-zeros outcome |0ⁿ⟩ is exactly |⟨φ(x')|φ(x)⟩|² — the squared inner product between the two feature states. Each kernel entry requires T circuit shots for precision 1/√T; for n training samples, the full kernel matrix needs O(n²T) total shots.

The elegance of this evaluation is that no ancilla qubits or SWAP tests are required. The circuit U†(x’)U(x) acting on |0ⁿ⟩ prepares a state whose all-zeros projection is exactly the desired inner product. Running this circuit T times and counting |0ⁿ⟩ outcomes estimates the kernel entry with statistical error O(1/√T).

Once the kernel matrix K is fully estimated — requiring O(n²) such circuits for n training points — a classical SVM solver minimises the dual objective:

max⁡α∑iαi−12∑i,jαiαjyiyj K(xi,xj)\max_\alpha \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j\, K(x_i, x_j)

subject to 0≤αi≤C0 \leq \alpha_i \leq C and ∑iαiyi=0\sum_i \alpha_i y_i = 0, where yi∈{±1}y_i \in \{\pm 1\} are class labels and CC is the regularisation parameter. This is a standard quadratic programme solved by well-established classical software. The quantum contribution is entirely in the kernel matrix entries; the learning is classical.

New test points xtestx_{\text{test}} are classified by computing kQ(xtest,xi)k_Q(x_{\text{test}}, x_i) for each support vector xix_i and evaluating the sign of ∑iαiyi kQ(xtest,xi)\sum_i \alpha_i y_i\, k_Q(x_{\text{test}}, x_i). This again requires O(∣SVs∣)O(|SVs|) quantum kernel evaluations per test point.

The Rigorous Quantum Advantage: Liu et al. 2021

In 2021, Yunchao Liu, Srinivasa Raghu, and colleagues published a paper in Nature Physics that provided the first rigorous, unconditional quantum advantage for a supervised learning task using quantum kernels.

The key construction: they defined a classification problem based on a variant of the discrete logarithm problem — a problem related to Simon’s algorithm and Shor’s algorithm. They proved two things simultaneously:

  1. Classical hardness: any classical machine learning algorithm (not just SVMs) requires an exponential number of training samples to learn the classification with better than random accuracy, assuming the learning with errors (LWE) hardness conjecture.

  2. Quantum efficiency: a quantum kernel SVM using the appropriate quantum feature map learns the same classification task with a polynomial number of training samples.

This is a genuine, unconditional quantum advantage for machine learning — the quantum algorithm solves a learning problem that classical algorithms cannot, under well-established cryptographic assumptions.

The critical qualification: the learning problem is artificial. It is constructed to have quantum structure by design — its hardness for classical learners comes directly from a cryptographic assumption, and the quantum advantage arises because the feature map is essentially implementing a quantum algorithm that breaks the underlying hardness. No natural real-world dataset has this structure.

The Hilbert Space Trap: More Dimensions Are Not Always Better

In the same year, Huang, Broughton, Cotler, and colleagues published a complementary negative result in Nature Communications: for generic datasets, quantum models do not outperform classical kernel methods, and the key predictor of advantage is the alignment between the quantum kernel and the data structure — not the dimensionality of the feature space.

The central theorem: if a quantum kernel k_Q(x, x’) can be approximated efficiently classically — even if the quantum feature space is exponentially large — then a classical SVM with that approximated kernel achieves the same classification accuracy. The exponential Hilbert space only provides advantage if it contains structure that is simultaneously:

  1. Hard to access classically (the kernel circuit cannot be efficiently simulated)
  2. Genuinely predictive for the target classification task

The problem: random quantum circuits satisfy condition 1 (they are hard to simulate classically for large n) but not condition 2 (their output has no particular alignment with the structure of real datasets — images, tabular data, time series). A high-dimensional feature space that is random with respect to your data is not useful; it is noise.

This is the Hilbert space trap: the temptation to assume that more dimensions automatically yield better classification. Classical kernels like the RBF kernel work well on most datasets precisely because they are designed with geometric intuition about what distances mean for natural data. Quantum feature maps, designed for their classical hardness rather than their geometric relevance, often perform no better than or worse than RBF SVMs on standard benchmarks.

Quantum vs Classical: When Does the Quantum Kernel Win?

QUANTUM KERNEL ADVANTAGE — WHEN AND WHERE DATA / PROBLEM TYPE CLASSICAL KERNEL SUFFICIENT? QUANTUM ADVANTAGE? STATUS Generic (images, tabular, NLP) Usually yes Not demonstrated No evidence Algebraically structured (Liu et al.) No (needs exp. samples) Yes (provably) Proved Quantum simulation output data Likely no Likely yes (natural fit) Plausible Molecule property prediction Uncertain at large scale Unproven but plausible Investigated Quantum advantage in machine learning requires: (1) kernel hard to estimate classically AND (2) data has structure the quantum kernel captures better than any efficient classical kernel. Both conditions must hold simultaneously.
Figure 4 — Summary of quantum kernel advantage conditions. Provable quantum advantage exists only for artificially constructed datasets with quantum algebraic structure. For natural datasets in computer vision, NLP, or finance, classical kernels consistently match or outperform quantum kernels in published benchmarks. The most promising near-term target is quantum simulation output data — where the data itself has quantum mechanical origin and quantum feature maps are a natural choice.

The Computational Cost Problem

Quantum kernel SVMs face a practical overhead that is easy to overlook. For n training points:

Classical RBF and polynomial kernels compute each kernel entry in O(d) floating-point operations. For d=100 and n=1000: 10⁸ classical operations for the full matrix — still much cheaper per entry than quantum circuit execution plus measurement.

This overhead means quantum kernel SVMs are currently slower than classical SVMs even for problems where the quantum kernel is theoretically better. The crossover — where the quantum kernel’s higher accuracy justifies the overhead — requires either datasets where classical kernels fail fundamentally (as in Liu et al.’s constructed problem) or quantum hardware fast enough to close the circuit execution gap.

What Has Actually Been Demonstrated

Havlíček et al. (2019) demonstrated quantum kernel classification and a linear classification method (quantum variational classifier) on a 2-qubit IBM processor using an artificially constructed dataset that was designed to be separable by the quantum kernel but not by a linear classical classifier. The demonstration showed the algorithm works on real hardware; it did not demonstrate advantage over classical SVM with a classical kernel on a real-world problem.

Subsequent benchmarks on standard datasets — UCI repository, financial data, molecular properties — have consistently found that classical kernel methods (RBF SVM, gradient boosting, neural networks) match or outperform quantum kernel SVMs. The quantum kernel sometimes achieves competitive accuracy, but the training costs are substantially higher and the accuracy advantage is not systematic.

One area with genuine promise: quantum data. When the data being classified is the output of quantum simulations — measurement outcomes from quantum circuits, molecular electronic states, or other quantum-mechanical systems — a quantum feature map is a natural choice, and classical feature maps may struggle to represent the relevant quantum structure efficiently. This niche does not exist on today’s classical datasets but becomes relevant as quantum computers are used as scientific instruments generating quantum data for analysis.

The Honest Assessment

Quantum kernel SVMs occupy an interesting theoretical position: the Liu et al. result proves that quantum machine learning advantage exists — the question is not whether quantum kernels can outperform classical learning, but whether they do so on problems that matter.

The field needs one of two things to progress. Either a dataset arising from a natural scientific or engineering problem where quantum structure genuinely drives hardness for classical methods — and where quantum kernels provably or empirically provide better generalisation. Or a theoretical argument that some class of practically important problems has the algebraic structure needed for quantum advantage.

What the field currently has: a rigorous proof of existence for an artificial problem, competitive-but-not-superior performance on real datasets, and an exponentially large feature space that is expensive to use and often no better than a carefully tuned RBF kernel.

That is a genuine scientific result. It is not yet a practical advantage. The difference matters, and the quantum machine learning community has become increasingly candid about it — which is itself a sign of a maturing field.

Sources & Further Reading

  1. Vojtěch Havlíček, Antonio D. Córcoles, et al.. Supervised Learning with Quantum-Enhanced Feature Spaces. Nature 567, 209; arXiv:1804.11326 (2019)
  2. Maria Schuld, Nathan Killoran. Quantum Machine Learning in Feature Hilbert Spaces. Physical Review Letters 122, 040504; arXiv:1803.07128 (2019)
  3. Yunchao Liu, Srinivasan Arunachalam, Kristan Temme. A Rigorous and Robust Quantum Speed-Up in Supervised Machine Learning. Nature Physics 17, 1013; arXiv:2010.02174 (2021)
  4. Hsin-Yuan Huang, Michael Broughton, et al.. Power of Data in Quantum Machine Learning. Nature Communications 12, 2631; arXiv:2011.01938 (2021)
More in AI Integrations
Tags#quantum kernels#QSVM#quantum machine learning#support vector machines#quantum feature maps#AI integrations#quantum advantage

Discussion

← All articles