Quantum Feature Maps and Kernel Methods

Kernel methods sit at the heart of classical machine learning: instead of working with raw data, you map each point $\mathbf{x}$ into a high-dimensional feature space via $\phi$ and learn a linear model there. The kernel trick is that a large family of algorithms — support vector machines chief among them — never touch the feature vectors, only their inner products $k(\mathbf{x},\mathbf{x}')=\langle\phi(\mathbf{x}),\phi(\mathbf{x}')\rangle$ . Quantum kernel methods add one remark: a quantum state is already a feature vector. A circuit $U(\mathbf{x})$ on $|0\rangle^{\otimes n}$ prepares $|\phi(\mathbf{x})\rangle$ in a $2^n$ -dimensional Hilbert space, and the computer estimates inner products in that exponentially large space. The payoff is a clean division of labour. The quantum device evaluates one object — the Gram matrix $K_{ij}=k(\mathbf{x}_i,\mathbf{x}_j)$ — and everything after is classical and convex: the SVM dual is a quadratic program with a unique optimum. With no non-convex landscape and no gradient estimation on the encoding circuit, kernel methods sidestep the barren-plateau pathology of variational classifiers. The prize would be a kernel provably hard to compute classically yet genuinely useful; the obstacle, established since 2019, is that raw expressibility is self-defeating — highly expressive embeddings make every off-diagonal entry collapse toward $2^{-n}$ , needing exponentially many shots to resolve. Designing a quantum kernel is therefore an exercise in inductive bias, not in covering Hilbert space.

Key takeaways

A quantum feature map encodes a point $\mathbf{x}$ into a state $|\phi(\mathbf{x})\rangle=U(\mathbf{x})|0\rangle^{\otimes n}$ in a $2^n$ -dimensional Hilbert space — the quantum analogue of a classical feature map.
The induced kernel is the overlap $k=|\langle\phi(\mathbf{x})|\phi(\mathbf{x}')\rangle|^2=\mathrm{Tr}[\rho(\mathbf{x})\rho(\mathbf{x}')]$ , positive-semidefinite and estimable by a swap-free overlap test.
Learning factorizes: the quantum device builds the Gram matrix, a classical convex SVM does the rest — no barren plateaus, as the encoding has no trainable parameters.
A rigorous exponential advantage exists (the discrete-log kernel of Liu, Arrasmith, Cerezo et al.), but it is the exception — most embeddings offer no proven separation.
The dominant failure mode is exponential concentration: expressive embeddings pin off-diagonal values at $2^{-n}$ (variance $\sim 2^{-2n}$ ), so distinguishing them costs $\gtrsim 2^n$ shots and the model predicts the mean.
Key idea: a circuit $U(\mathbf{x})$ defines a feature map $\mathbf{x}\mapsto\rho(\mathbf{x})=U(\mathbf{x})|0\rangle\langle0|U(\mathbf{x})^\dagger$ ; the quantum kernel $k=\mathrm{Tr}[\rho(\mathbf{x})\rho(\mathbf{x}')]$ is positive-definite and quantum-estimable, and every step of learning afterwards is convex and classical.

The core insight

A quantum circuit $U(\mathbf{x})$ defines a feature map $\mathbf{x}\mapsto\rho(\mathbf{x})=U(\mathbf{x})|0\rangle\langle0|U(\mathbf{x})^\dagger$ ; the quantum kernel $k(\mathbf{x},\mathbf{x}')=\mathrm{Tr}[\rho(\mathbf{x})\rho(\mathbf{x}')]$ is a positive-definite kernel estimable by a quantum computer, and all subsequent learning is convex and classical.

Where this lives today

Quantum kernels are the most experimentally mature corner of quantum machine learning because they demand so little of the hardware: a fixed encoding, an overlap test, and a classical SVM. The Havlíček demonstration ran on IBM superconducting qubits; classifiers have since been benchmarked on trapped-ion and photonic platforms, and the projected quantum kernel of Huang et al. (2021) was studied at dozens of qubits, showing reduced-density-matrix kernels resist concentration far better than fidelity kernels. The theoretical frontier is inductive bias by construction: equivariant and geometric kernels bake data symmetries directly into $U(\mathbf{x})$ , and bandwidth tuning rescales the encoding angles to interpolate between the trivial ( $k\to1$ ) and concentrated ( $k\to2^{-n}$ ) regimes. The open problem is stark: outside the discrete-log construction there is no proven advantage for a natural learning problem, and concentration suggests generic embeddings never will. Whether a data-tailored quantum kernel can beat the best classical kernel on a problem people actually care about — rather than a cryptographically engineered one — is the field's central unanswered question.

The physical picture

A quantum kernel answers one question: how similar are two data points after the quantum computer has looked at them? Encode $\mathbf{x}$ and $\mathbf{x}'$ as states; the probability they pass an overlap test is their similarity. Because the states live in $2^n$ dimensions this can encode correlations no efficient classical measure reproduces — yet you never build the feature vector, only estimate its overlaps. The first figure makes "similarity = overlap" one picture: a compute-uncompute circuit whose all-zeros probability is the kernel entry, with the geometric view of two feature states at an angle.

Figure

Estimating one kernel entry with the swap-free overlap test: prepare the compute-uncompute circuit U†(x) U(x′) on the all-zeros register, then the probability of measuring 0ⁿ equals the squared overlap of the two feature states. For a single-qubit R_Y encoding the kernel is cos²((x−x′)/2); at x = 0 and x′ = π/2 it equals 0.50

Two regimes bracket the design space. A weak, low-expressibility embedding gives an essentially classical similarity and no advantage. A maximally expressive one makes the encoded states behave like independent Haar-random vectors, so for $\mathbf{x}\neq\mathbf{x}'$ the overlap collapses toward $2^{-n}$ : the Gram matrix becomes a scaled identity and the SVM memorizes rather than generalizes. The collapse is exponential in qubit count — the kernel sibling of the barren plateau. The punchline figure plots the mean off-diagonal value against qubit number, putting real numbers on the cliff.

Figure

The punchline: for an expressive (2-design) embedding the mean off-diagonal kernel value falls as 2⁻ⁿ, plotted on a log axis against qubit number n. By n = 10 the value is 9.8×10⁻⁴, by n = 20 it is 9.5×10⁻⁷, and by n = 30 it is 9.3×10⁻¹⁰ — indistinguishable from zero under any realistic shot budget, which is exponential concentration

The core equations

A fixed unitary $U(\mathbf{x})$ maps a classical vector to a quantum state; its outer product is the density matrix that serves as feature vector in operator space.

|\phi(\mathbf{x})\rangle = U(\mathbf{x})\,|0\rangle^{\otimes n}, \qquad \rho(\mathbf{x}) = |\phi(\mathbf{x})\rangle\langle\phi(\mathbf{x})| \qquad (1)

where: $\mathbf{x}$ — classical data point, $\mathbf{x}\in\mathbb{R}^d$ ; $U(\mathbf{x})$ — data-encoding unitary, parameters fixed to functions of the data; $n$ — qubit count, feature-space dimension $2^n$ ; $\rho(\mathbf{x})$ — pure-state density matrix. Reading: the data enter only through $U$ , once, with nothing to train. The kernel is the overlap of two feature states; as a Hilbert–Schmidt inner product of density matrices it is a genuine positive-definite kernel.

k(\mathbf{x},\mathbf{x}') = |\langle\phi(\mathbf{x})|\phi(\mathbf{x}')\rangle|^2 = \mathrm{Tr}\big[\rho(\mathbf{x})\,\rho(\mathbf{x}')\big] \qquad (2)

where: $k$ — symmetric, positive-semidefinite kernel in $[0,1]$ ; $\mathrm{Tr}$ — trace over the $n$ -qubit Hilbert space. Reading: this is the fidelity of the two pure states — $k=1$ when they coincide, $k=0$ when orthogonal. A quantum computer estimates equation (2) with no swap test and no ancilla: run $U(\mathbf{x}')$ , then the inverse $U^\dagger(\mathbf{x})$ , and read the register.

k(\mathbf{x},\mathbf{x}') = \big|\langle 0|U^\dagger(\mathbf{x})\,U(\mathbf{x}')|0\rangle\big|^2 = \Pr\big[\text{measure } 0^n\big] \qquad (3)

where: $U^\dagger(\mathbf{x})U(\mathbf{x}')$ — compute-uncompute circuit on $|0\rangle^{\otimes n}$ ; $\Pr[0^n]$ — probability every qubit returns to $|0\rangle$ . Reading: the kernel is an outcome probability, so it inherits binomial shot statistics. Each shot is a Bernoulli trial, so one Gram entry has a binomial estimator whose variance sets the cost.

\hat{k} = \frac{1}{M}\sum_{m=1}^{M}\mathbb{1}[\text{outcome}_m = 0^n], \qquad \mathrm{Var}(\hat{k}) = \frac{k(1-k)}{M} \le \frac{1}{4M} \qquad (4)

where: $M$ — shots per entry; $\hat{k}$ — empirical estimate. Reading: precision $\epsilon$ costs $M=O(\epsilon^{-2}\log\delta^{-1})$ per entry, and a Gram matrix has $O(N^2)$ entries. With the Gram matrix $K_{ij}=k(\mathbf{x}_i,\mathbf{x}_j)$ in hand, learning is the ordinary soft-margin SVM dual — a convex quadratic program the quantum device never touches.

\min_{\boldsymbol{\alpha}} \; \tfrac{1}{2}\sum_{i,j}\alpha_i\alpha_j\,y_i y_j\,K_{ij} - \sum_i \alpha_i \quad \text{s.t. } 0\le\alpha_i\le C,\; \sum_i\alpha_i y_i=0 \qquad (5)

where: $\alpha_i$ — dual variables (support-vector weights); $y_i\in\{\pm1\}$ — labels; $C$ — soft-margin regularization. Reading: because $K\succeq 0$ this is convex with a unique optimum; the decision function is $f(\mathbf{x})=\mathrm{sign}\!\big(\sum_{i}\alpha_i y_i\,k(\mathbf{x}_i,\mathbf{x})+b\big)$ . The failure mode dominating practice is a moment calculation: when the embedding forms an approximate unitary 2-design, the off-diagonal kernel concentrates with exponentially small variance.

\mathbb{E}[k] = \frac{1}{2^n}, \qquad \mathrm{Var}[k]=\frac{2^n-1}{2^n(2^n+1)}\;\xrightarrow{\;n\to\infty\;}\;\frac{1}{2^{2n}}, \qquad \mathrm{Var}[k]\le\frac{1}{2^n+1} \qquad (6)

where: $\mathbb{E},\mathrm{Var}$ — mean and variance over the input distribution. Reading: the mean off-diagonal value and the standard deviation both scale as $2^{-n}$ , the variance as $2^{-2n}$ ; resolving the structure costs $M\gtrsim 2^n$ shots. A representative conjectured-hard embedding is the Havlíček ZZ feature map: Hadamards followed by data-dependent diagonal phases coupling qubits.

U_\Phi(\mathbf{x})=\exp\!\Big(i\!\sum_{S}\phi_S(\mathbf{x})\!\prod_{j\in S}\!Z_j\Big)\,H^{\otimes n}, \qquad \phi_{\{i,j\}}(\mathbf{x})=(\pi-x_i)(\pi-x_j) \qquad (7)

where: $\phi_S(\mathbf{x})$ — data-dependent angle on qubit subset $S$ ; $Z_j$ — Pauli- $Z$ ; $H^{\otimes n}$ — Hadamard layer. Reading: the nonlinear products $\phi_S(\mathbf{x})$ imprint data correlations; estimating the kernel is conjectured (not proven) hard classically. Separately, any fixed-encoding variational model $f_{\text{var}}(\mathbf{x})=\langle\rho(\mathbf{x}),M_{\boldsymbol{\theta}}\rangle_{\mathrm{HS}}$ is linear in the feature state, hence a kernel model — developed in Derivation 3.

Derivation AFrom the kernel trick to the quantum Gram matrix

The goal is to prove the swap-free overlap test of equation (3) really estimates a positive-semidefinite kernel, so the SVM dual (5) is a legitimate convex program and not a heuristic. We connect three layers — the feature map into operator space, the Hilbert–Schmidt inner product that makes it an inner-product space, and the measurement frequency the hardware returns — then show the Gram matrix is automatically PSD, which licenses every downstream claim of convexity.

Step 1. Define the feature map $\Phi:\mathbf{x}\mapsto\rho(\mathbf{x})=U(\mathbf{x})|0\rangle\langle0|U^\dagger(\mathbf{x})$ into the real vector space of $2^n\times 2^n$ Hermitian operators with inner product $\langle A,B\rangle_{\mathrm{HS}}=\mathrm{Tr}[A^\dagger B]$ . Why: a function is a valid kernel exactly when it is an inner product in some feature space, so name that space — here operator space, not state space.

Step 2. Evaluate the overlap. Since $\rho(\mathbf{x}_i)=U_i|0\rangle\langle0|U_i^\dagger$ , the cyclic trace gives $\mathrm{Tr}[\rho_i\rho_j]=\langle0|U_i^\dagger U_j|0\rangle\langle0|U_j^\dagger U_i|0\rangle=|\langle0|U_i^\dagger U_j|0\rangle|^2$ , real and non-negative. Why: this turns an abstract operator overlap into the squared amplitude of a single transition — what a computational-basis measurement reports.

Step 3. Read that amplitude off the hardware. Preparing $U^\dagger(\mathbf{x}_i)U(\mathbf{x}_j)|0\rangle^{\otimes n}$ and measuring yields $0^n$ with probability exactly $|\langle0|U_i^\dagger U_j|0\rangle|^2=K_{ij}$ , estimated by the all-zeros frequency over $M$ shots. Why: it collapses overlap estimation into one circuit and one bit-pattern count, making the protocol NISQ-friendly.

Step 4. Establish positive semidefiniteness. For any real $\mathbf{v}$ , $\mathbf{v}^\top K\mathbf{v}=\big\|\sum_i v_i\rho(\mathbf{x}_i)\big\|_{\mathrm{HS}}^2\ge 0$ , a squared operator norm. Why: a Gram matrix of vectors in an inner-product space is PSD by construction, so the SVM dual is convex however exotic the feature space — convexity is inherited, not assumed. *Verified: cyclic-trace identity and Gram-matrix positivity are standard (Nielsen & Chuang ch. 2); the single-qubit $R_Y$ check $k=\cos^2((x-x')/2)=0.50$ confirms the overlap-test value.*

Go deeper · Derivation B · 1 minExponential concentration from Haar-random embeddings

Derivation BExponential concentration from Haar-random embeddings

The goal is to show quantitatively why maximizing expressibility is self-defeating: when the ensemble $\{U(\mathbf{x})\}$ approximates a unitary 2-design, the kernel goes statistically flat — off-diagonal entries pinned near one value with an exponentially small spread — so resolving the structure a classifier needs costs exponentially many measurements. We compute the mean and variance from the 2-design moments, then translate the variance into a shot budget — the calculation that earns concentration its name as the kernel analogue of barren plateaus.

Step 2. First moment: $\mathbb{E}\,|\langle\psi|\varphi\rangle|^2=1/D$ . Why: two independent random unit vectors in $D$ dimensions have expected squared overlap $1/D$ — the value every off-diagonal entry is dragged toward.

Step 3. Second moment (Weingarten): $\mathbb{E}\,|\langle\psi|\varphi\rangle|^4=2/[D(D+1)]$ , so $\mathrm{Var}[k]=\dfrac{2}{D(D+1)}-\dfrac{1}{D^2}=\dfrac{D-1}{D^2(D+1)}$ . Why: this exact expression is what the asymptotics rest on — getting the exponent right is the whole point.

Step 4. Asymptotics: for large $D=2^n$ , $\mathrm{Var}[k]\to 1/D^2=2^{-2n}$ , so $\mathrm{std}[k]\sim 1/D=2^{-n}$ — the same scale as the mean; a loose bound is $\mathrm{Var}[k]\le 1/(2^n+1)$ . Why: mean and fluctuation shrink at the same rate, burying the contrast at scale $2^{-n}$ — note variance goes as $2^{-2n}$ , not $2^{-n}$ , which the thin migrated draft stated loosely.

Step 5. Shot budget: an off-diagonal $k\approx2^{-n}$ has estimator variance $\approx 2^{-n}/M$ , so standard error $2^{-n/2}/\sqrt{M}$ ; resolving $\mathrm{std}[k]\sim 2^{-n}$ needs $M\gtrsim 2^{n}$ . Why: below this the estimated Gram matrix is indistinguishable from a scaled identity and the model predicts the class mean — inductive bias, not expressibility, is the target. *Verified numerically: at $n=10,20,30$ , $\mathbb{E}[k]=9.77\times10^{-4},\,9.54\times10^{-7},\,9.31\times10^{-10}$ and $\mathrm{Var}[k]\cdot D^2\to1$ , confirming $\mathrm{Var}[k]\sim2^{-2n}$ ; matches Thanasilp et al. (2024) and Watrous ch. 7.*

Go deeper · Derivation C · 1 minWhy a variational quantum classifier is secretly a kernel machine

Derivation CWhy a variational quantum classifier is secretly a kernel machine

The goal is to establish Schuld's structural theorem — that every variational quantum model whose data enter only through a fixed feature map is at most as powerful as the kernel method built from that map — and so explain why the kernel is the theoretical ceiling of fixed-encoding quantum machine learning. The argument identifies the variational output as linear in the feature state, then invokes the representer theorem to collapse the optimal operator onto the span of the training data.

Step 1. Write the variational output as an inner product. A fixed-encoding classifier applies a trainable $W(\boldsymbol{\theta})$ and measures a fixed $O$ , giving $f_{\text{var}}(\mathbf{x})=\mathrm{Tr}[\rho(\mathbf{x})\,M_{\boldsymbol{\theta}}]=\langle\rho(\mathbf{x}),M_{\boldsymbol{\theta}}\rangle_{\mathrm{HS}}$ with $M_{\boldsymbol{\theta}}=W^\dagger(\boldsymbol{\theta})\,O\,W(\boldsymbol{\theta})$ . Why: this exposes the model as strictly linear in the feature state — all nonlinearity lives in the fixed encoding, none in the readout.

Step 2. Apply the representer theorem. Minimizing any regularized empirical risk over $M$ forces the optimum into the span of the training states, $M^\star=\sum_i\beta_i\,\rho(\mathbf{x}_i)$ , so $f_{\text{var}}(\mathbf{x})=\sum_i\beta_i\,k(\mathbf{x}_i,\mathbf{x})$ . Why: the component of $M$ orthogonal to the training states only raises the regularizer, so it is discarded — the classical representer argument in operator space.

Step 3. Draw the consequence. The best fixed-encoding variational model coincides with a kernel model on the same embedding, so the kernel upper-bounds it — kernels are the best case for a given feature map. Why: a fixed-encoding model can only approach the kernel it already implies, so effort should go into the embedding, not a fancier readout. *Verified: linearity of $f_{\text{var}}$ in $\rho(\mathbf{x})$ is immediate from the trace; the representer step is standard (Schölkopf & Smola ch. 4), and the conclusion is Schuld, arXiv:2101.11020 (2021).*

Limiting cases

Case	Result	Meaning
Identical inputs	$k(\mathbf{x},\mathbf{x})=\|\langle\phi(\mathbf{x})\|\phi(\mathbf{x})\rangle\|^2=1$	the fidelity kernel's diagonal is always one, fixing the Gram-matrix scale
Maximally expressive (2-design) embedding	$\mathbb{E}\,k\to 2^{-n},\ \mathrm{Var}\,k\sim 2^{-2n}$	off-diagonals concentrate exponentially; resolving them needs $\gtrsim 2^n$ shots — the barren-plateau analogue
Product (separable) embedding	$k(\mathbf{x},\mathbf{x}')=\prod_{j=1}^{n}\|\langle\phi_j(x_j)\|\phi_j(x_j')\rangle\|^2$	factorizable, classically efficient — no entanglement, no advantage, but no concentration
Single-qubit $R_Y$ encoding	$k(x,x')=\cos^2\!\big(\tfrac{x-x'}{2}\big)=\tfrac12(1+\cos(x-x'))$	a smooth classical shift-invariant kernel — a shallow map is trivially classical
Projected / classical-shadow kernel	$k_{\mathrm{P}}(\mathbf{x},\mathbf{x}')=\exp\!\big(-\gamma\sum_j\\|\rho_j(\mathbf{x})-\rho_j(\mathbf{x}')\\|_{\mathrm{HS}}^2\big)$	one-qubit marginals restore an $O(1)$ scale, mitigating concentration (Huang et al. 2021)

Common trapMore expressibility makes a better quantum kernel

It does the opposite. Covering Hilbert space uniformly — "using all $2^n$ dimensions" — is exactly wrong, because an ensemble approaching a unitary 2-design forces every off-diagonal value to $2^{-n}$ with variance $\sim 2^{-2n}$ . Under any finite shot budget the off-diagonal entries then become statistically indistinguishable from one another and from zero, the matrix looks like a scaled identity, and the SVM degenerates to predicting the majority class. A useful quantum kernel must be deliberately restricted by problem-relevant inductive bias — symmetry, locality, a matched group structure — so similar points stay measurably more similar than dissimilar ones. Expressibility is a cost to spend sparingly; the discrete-log kernel is powerful because its structure is tailored to one problem, not because it fills Hilbert space.

Worked examples

1 · A single-qubit kernel worked out by hand (confidence builder)

Encode a scalar $x$ with $U(x)=R_Y(x)$ . Find the kernel $k(x,x')$ in closed form, evaluate it at $x=0,\ x'=\pi/2$ , and say why this embedding offers no advantage.

Step 1. Feature state: $|\phi(x)\rangle=R_Y(x)|0\rangle=\cos\frac{x}{2}\,|0\rangle+\sin\frac{x}{2}\,|1\rangle$ , tracing a great circle of the Bloch sphere as $x$ runs over $[0,2\pi)$ .

Step 2. Overlap: $\langle\phi(x)|\phi(x')\rangle=\cos\frac{x}{2}\cos\frac{x'}{2}+\sin\frac{x}{2}\sin\frac{x'}{2}=\cos\!\big(\tfrac{x-x'}{2}\big)$ , hence $k(x,x')=\cos^2\!\big(\tfrac{x-x'}{2}\big)=\tfrac12\big(1+\cos(x-x')\big)$ — a smooth, shift-invariant classical kernel a pocket calculator matches.

Step 3. Evaluate. At $x=0,\ x'=\pi/2$ : $k=\cos^2(\pi/4)=\mathbf{0.50}$ , confirmed by the overlap test $R_Y^\dagger(0)R_Y(\pi/2)=R_Y(\pi/2)$ giving $\Pr[0]=0.50$ . A single qubit (and any tensor-product encoding) yields a factorizable kernel computable in $O(n)$ classical operations, so there is no advantage — that requires entangling encodings whose overlaps resist classical evaluation. $k(x,x')=\cos^2((x-x')/2)=0.50$ at the quarter-turn separation, classically trivial.

2 · Shot budget for one Gram matrix (fully numeric)

Target each off-diagonal entry to precision $\epsilon=0.01$ at 95% confidence, on $N=100$ points. How many shots per entry, and how many total?

Step 1. Per-entry shots from Hoeffding: $\Pr[|\hat k-k|\ge\epsilon]\le 2e^{-2M\epsilon^2}\le\delta$ gives $M\ge\ln(2/\delta)/(2\epsilon^2)$ . With $\delta=0.05$ : $M\ge\ln40/(2\times10^{-4})\approx\mathbf{1.84\times10^{4}}$ .

Step 2. The Gram matrix is symmetric with unit diagonal, so only $\binom{N}{2}=\mathbf{4950}$ off-diagonal entries need measuring.

Step 3. Total: $4950\times 1.84\times10^{4}\approx\mathbf{9.1\times10^{7}}$ shots. At $10^4$ circuits/s that is $\approx$ 2.5 hours of quantum time, scaling as $N^2$ — the wall the method hits on large datasets. Kernel methods trade the barren-plateau training problem for a quadratic-in- $N$ sampling one; if the embedding is also expressive, concentration adds an exponential factor (at $n=30$ the signal $2^{-30}\approx 9.3\times10^{-10}$ needs $\gtrsim 10^{9}$ shots per entry, so it is unlearnable).

Physics of the portrait

A young idea with deep roots: the quantum feature map grafts the kernel trick onto the state space of a quantum computer, inheriting its convex guarantees and a failure mode all its own.

Origins · 1 minquantum feature map and how this was discovered

quantum feature map

the embedding x ↦ ρ(x) of data into a 2ⁿ-dimensional Hilbert space · quantum machine learning

The quantum feature map arrived almost fully formed in 2019 from two directions. Maria Schuld and Nathan Killoran argued that a state-preparation circuit is a feature map into a "feature Hilbert space"; the same year, Vojtěch Havlíček and collaborators at IBM ran both a variational and a kernel-estimation classifier on superconducting hardware and conjectured their ZZ embedding yields classically hard kernels. The abstraction rests on older machinery — the kernel trick of Aizerman, Braverman and Rozonoer (1964) and the support vector machine of Boser, Guyon and Vapnik (1992) — with quantum information adding a feature space of dimension $2^n$ reachable by a device that never writes the feature vector down. Two 2021 results set the field's shape: Liu, Arrasmith, Cerezo and co-workers gave the first — and essentially only — rigorous exponential separation, whose classical solution would break the discrete-logarithm assumption; and Schuld proved every fixed-encoding variational model is a kernel method in disguise. The counter-melody, definitively from Thanasilp, Wang, Cerezo and Holmes (2024), is that expressive embeddings suffer exponential concentration, so the design problem is one of inductive bias, not raw quantum reach — the map that began as an optimistic analogy is now a delicate instrument.

History

1964

— Aizerman, Braverman and Rozonoer introduce the kernel trick as the method of potential functions

1992

— Boser, Guyon and Vapnik build the support vector machine on kernels

2019

— Schuld and Killoran, and Havlíček et al., define quantum feature maps and quantum kernels

2021

— Liu, Arrasmith, Cerezo et al. prove a discrete-log exponential speedup; Schuld shows fixed-encoding models are kernel methods

2024

— Thanasilp, Wang, Cerezo and Holmes formalize exponential concentration in quantum kernels

Going further

Texts and papers. Havlíček et al., "Supervised learning with quantum-enhanced feature spaces", Nature 567, 209 (2019) · Schuld & Killoran, "Quantum machine learning in feature Hilbert spaces", PRL 122, 040504 (2019) · Liu, Arrasmith, Cerezo et al., "A rigorous and robust quantum speed-up in supervised machine learning", Nature Physics 17, 1013 (2021) · Schuld, "Supervised quantum machine learning models are kernel methods", arXiv:2101.11020 (2021) · Huang et al., "Power of data in quantum machine learning", Nature Communications 12, 2631 (2021) · Kübler, Buchholz & Schölkopf, "The inductive bias of quantum kernels", NeurIPS (2021) · Thanasilp, Wang, Cerezo & Holmes, "Exponential concentration in quantum kernel methods", Nature Communications 15, 5200 (2024) · Schölkopf & Smola, Learning with Kernels (MIT Press, 2002) · Nielsen & Chuang, Quantum Computation and Quantum Information (10th anniv. ed.); Watrous, The Theory of Quantum Information, ch. 7 (Haar/Weingarten calculus).

Provenance. A verifier should recompute: (1) the cyclic-trace identity $\mathrm{Tr}[\rho_i\rho_j]=|\langle\phi_i|\phi_j\rangle|^2$ and Gram-matrix PSD-ness (Nielsen & Chuang ch. 2); (2) the Haar moments $\mathbb{E}|\langle\psi|\varphi\rangle|^2=1/D$ , $\mathbb{E}|\langle\psi|\varphi\rangle|^4=2/[D(D+1)]$ , giving $\mathrm{Var}[k]=(D-1)/[D^2(D+1)]\to 2^{-2n}$ with $\mathrm{std}[k]\sim 2^{-n}$ — note variance goes as $2^{-2n}$ , not $2^{-n}$ (Watrous ch. 7; Thanasilp et al. 2024); (3) the Hoeffding budget $M\ge\ln(2/\delta)/(2\epsilon^2)\approx1.84\times10^4$ at $\epsilon=0.01,\delta=0.05$ ; (4) the $R_Y$ kernel $\cos^2((x-x')/2)=0.50$ at $x=0,x'=\pi/2$ . Structural claims about the ZZ map, the discrete-log separation, and concentration are cited from the primary sources; no experimental numbers are fabricated.

Prerequisites. Quantum Machine Learning Models · Parameterized Quantum Circuits and Ansatz Design · Cost-Function and Measurement Estimation · Expressibility and Trainability Trade-offs. Leads to. Variational Quantum Eigensolver · Barren Plateaus · Mitigating Barren Plateaus.

Ask the tutor: Ask me to walk through why a maximally expressive embedding concentrates to $2^{-n}$ , or to derive the single-qubit kernel $\cos^2((x-x')/2)$ from scratch.

Is a quantum kernel just a fancy classical kernel, or something genuinely different?

Formally it is an ordinary positive-definite kernel — that is the appeal, because it plugs straight into a classical SVM with the convexity intact. Only the cost of computing it can differ. A shallow or product embedding has a closed classical form (Worked Example 1), so no advantage; the hope is an entangling embedding whose overlaps are classically intractable, of which the discrete-log kernel is a proven case. A quantum kernel is not a new kind of similarity — just a possibly-hard-to-evaluate instance of a familiar one.

Why do kernel methods avoid barren plateaus when variational classifiers do not?

Because the encoding circuit $U(\mathbf{x})$ carries no trainable parameters. Barren plateaus are about gradients of a trainable circuit vanishing across a non-convex landscape; a kernel method has no such landscape — the device only does forward overlap estimations, and the sole optimization is the convex SVM dual. But the difficulty does not vanish, it moves: exponential concentration is the kernel sibling of the barren plateau — a flat kernel and unresolvable Gram entries.

What actually is the exponential concentration problem, in one paragraph?

For an expressive embedding behaving like a unitary 2-design, every off-diagonal entry is dragged toward $2^{-n}$ , with spread across data pairs of standard deviation only $\sim 2^{-n}$ (variance $\sim 2^{-2n}$ ). So the contrast a classifier lives on is exponentially small. Seeing it above shot noise takes $\gtrsim 2^n$ shots per entry; below that the estimated Gram matrix is a scaled identity and the SVM predicts the class mean. It is why "use all of Hilbert space" is a trap.

Is there a proven quantum advantage for kernel methods, or just hope?

Exactly one clean proof, and much hope. Liu, Arrasmith, Cerezo et al. (2021) built a problem whose labels depend on the discrete logarithm of the input; a feature map from modular-exponentiation circuits yields a kernel an efficient quantum SVM learns well, while any classical learner beating chance would give an efficient discrete-log solver, contradicting a standard cryptographic assumption. That is a rigorous exponential separation — but engineered around a problem chosen to be hard, not a dataset anyone needs classified. For natural problems no proven advantage exists: it is possible in principle, unproven in practice.

How is a quantum kernel estimated without a swap test?

You use the compute-uncompute (inversion) test. For $k(\mathbf{x}_i,\mathbf{x}_j)$ , prepare $|0\rangle^{\otimes n}$ , apply $U(\mathbf{x}_j)$ , then the inverse $U^\dagger(\mathbf{x}_i)$ , and measure. The all-zeros probability is exactly $|\langle0|U^\dagger(\mathbf{x}_i)U(\mathbf{x}_j)|0\rangle|^2=k(\mathbf{x}_i,\mathbf{x}_j)$ , estimated by the frequency over $M$ shots. No ancilla and no controlled-SWAP, so it roughly halves qubit count and depth versus a swap test — the NISQ default. The catch: it needs a clean $U^\dagger$ , and any coherent error in the inverse degrades the estimate.

If expressibility is bad, why not just use a trivial low-expressibility encoding?

Because a trivial encoding gives a trivial, classically computable kernel with no chance of advantage — the two failure modes bracket a narrow useful window. Too little expressibility and the kernel is a plain classical similarity (Worked Example 1); too much and it concentrates to uselessness (Derivation 2). The art is structured expressibility: rich enough that overlaps are classically hard, yet restricted by inductive bias — symmetry, locality, tuned bandwidth — so similar data stay measurably more similar, the classical lesson that the right kernel encodes prior knowledge.