QuantumCore

Lesson 39 · 110 min · advanced

Quantum Kernels & Fidelity Kernels

Loading progress…

A quantum feature map x↦∣ϕ(x)⟩=U(x)∣0n⟩x\mapsto\lvert\phi(x)\rangle=U(x)\lvert0^n\rangle defines the fidelity kernel K(x,x′)=∣⟨ϕ(x)∣ϕ(x′)⟩∣2K(x,x')=\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2. This lesson proves via the cyclicity of the trace that K(x,x′)=Tr(ρ(x)ρ(x′))K(x,x')=\mathrm{Tr}\big(\rho(x)\rho(x')\big), proves that every quantum kernel matrix is positive semidefinite because ∑ijcicjK(xi,xj)=∥∑iciρ(xi)∥HS2\sum_{ij}c_ic_jK(x_i,x_j)=\lVert\sum_ic_i\rho(x_i)\rVert_{HS}^2, identifies KK as the linear kernel of the Hilbert–Schmidt feature space of density operators and its RKHS as the expectation values Tr(Oρ(x))\mathrm{Tr}\big(O\rho(x)\big), derives the closed form ∏jcos⁡2xj−xj′2\prod_j\cos^2\frac{x_j-x'_j}{2} for product encodings, proves exponential concentration (E[K]=2−n\mathbb E[K]=2^{-n}, Var[K]=(3/8)n−4−n\mathrm{Var}[K]=(3/8)^n-4^{-n}), shows that the projected quantum kernel is positive definite and keeps an nn-independent scale, and counts the shots needed to estimate a whole Gram matrix.

Prerequisites: RKHS, Representer & Mercer's Theorem, Angle & Phase Encoding

Objectives and key results

  • Derive ∣⟨ϕ(x)∣ϕ(x′)⟩∣2=Tr(ρ(x)ρ(x′))\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2=\mathrm{Tr}\big(\rho(x)\rho(x')\big) from the cyclicity of the trace and relate it to the inversion test.

  • Prove that every quantum kernel matrix is positive semidefinite and that it is the Gram matrix of the vectors vec ρ(xi)\mathrm{vec}\,\rho(x_i), i.e. the linear kernel in the Hilbert–Schmidt feature space.

  • Describe the RKHS of a fidelity kernel as the functions x↦Tr(Oρ(x))x\mapsto\mathrm{Tr}\big(O\rho(x)\big) and connect it to the representer theorem of the previous module.

  • Compute the fidelity kernel of RXR_X, RYR_Y and phase product encodings in closed form, K(x,x′)=∏jcos⁡2xj−xj′2K(x,x')=\prod_j\cos^2\frac{x_j-x'_j}{2}.

  • Prove E[K]=2−n\mathbb E[K]=2^{-n} and Var[K]=(3/8)n−4−n\mathrm{Var}[K]=(3/8)^n-4^{-n} for uniformly distributed data, and explain why exponentially many shots are then needed.

  • Prove that the projected quantum kernel exp⁡(−γ∑j∥ρj(x)−ρj(x′)∥F2)\exp\big(-\gamma\sum_j\lVert\rho_j(x)-\rho_j(x')\rVert_F^2\big) is positive definite and compute its mean, (e−γI0(γ))n(e^{-\gamma}I_0(\gamma))^n, for product encodings.

  • Bound the number of shots per kernel entry (O(1/ε2)O(1/\varepsilon^2)) and the number of circuits for a Gram matrix (M(M−1)/2M(M-1)/2).

identity · Fidelity kernel as a Hilbert–Schmidt inner product
K(x,x′)=∣⟨ϕ(x)∣ϕ(x′)⟩∣2=Tr(ρ(x)ρ(x′))=vec(ρ(x))†vec(ρ(x′))K(x,x')=\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2=\mathrm{Tr}\big(\rho(x)\rho(x')\big)=\mathrm{vec}\big(\rho(x)\big)^\dagger\mathrm{vec}\big(\rho(x')\big)
theorem · Quantum kernel matrices are positive semidefinite
∑i,j=1McicjK(xi,xj)=Tr(A2)=∥A∥HS2≥0,A=∑i=1Mciρ(xi)=A†\sum_{i,j=1}^Mc_ic_jK(x_i,x_j)=\mathrm{Tr}(A^2)=\lVert A\rVert_{HS}^2\ge0,\qquad A=\sum_{i=1}^Mc_i\rho(x_i)=A^\dagger
formula · Product-encoding kernel
U(x)=⨂jRX(xj) ⇒ K(x,x′)=∏j=0n−1cos⁡2xj−xj′2=∏j=0n−11+cos⁡(xj−xj′)2U(x)=\bigotimes_{j}R_{X}(x_j)\ \Rightarrow\ K(x,x')=\prod_{j=0}^{n-1}\cos^2\frac{x_j-x'_j}{2}=\prod_{j=0}^{n-1}\frac{1+\cos(x_j-x'_j)}{2}
theorem · Exponential concentration
xj,xj′∼i.i.d.U[0,2π):E[K]=2−n,Var[K]=(38)n−4−nx_j,x'_j\overset{\text{i.i.d.}}{\sim}U[0,2\pi):\qquad\mathbb E[K]=2^{-n},\qquad\mathrm{Var}[K]=\Big(\frac38\Big)^n-4^{-n}
definition · Projected quantum kernel
kPQ(x,x′)=exp⁡(−γ∑j=0n−1∥ρj(x)−ρj(x′)∥F2),∥ρ−ρ′∥F2=12∣r⃗−r⃗ ′∣2k^{PQ}(x,x')=\exp\Big(-\gamma\sum_{j=0}^{n-1}\lVert\rho_j(x)-\rho_j(x')\rVert_F^2\Big),\qquad\lVert\rho-\rho'\rVert_F^2=\tfrac12\lvert\vec r-\vec r\,'\rvert^2
formula · Shot cost of a Gram matrix
N≥ln⁡(2/δ)2ε2 shots per entry,M(M−1)2 entriesN\ge\frac{\ln(2/\delta)}{2\varepsilon^2}\ \text{shots per entry},\qquad\frac{M(M-1)}{2}\ \text{entries}

Quantum feature maps and the fidelity kernel#

The previous module ended with a proposition: if data are encoded into quantum states ∣ψ(x)⟩\lvert\psi(x)\rangle, the fidelity ∣⟨ψ(x)∣ψ(x′)⟩∣2\lvert\langle\psi(x)\vert\psi(x')\rangle\rvert^2 is a positive-definite kernel whose feature vectors are the density matrices ρ(x)\rho(x). The encoding lessons of Module 3.2 built the circuits that produce such states. This lesson turns the observation into a learning method. A quantum kernel method splits the work between two machines: a quantum computer estimates the entries K(xi,xj)K(x_i,x_j) of the Gram matrix, and a classical computer solves the convex training problem of a support vector machine or of kernel ridge regression exactly as in the kernel-methods lesson, with a model of the form f(x)=∑iαiK(x,xi)+bf(x)=\sum_i\alpha_iK(x,x_i)+b guaranteed by the representer theorem. We first make the kernel precise and prove its basic identities, then describe its feature space and RKHS, compute it in closed form for product encodings, and finally confront the two quantities that decide whether the method is usable at scale: the typical size of the kernel values and the number of measurements needed to estimate them.

Definition

Quantum feature map and encoded density operator

Let X⊆Rd\mathcal X\subseteq\mathbb R^d be the data domain. A quantum feature map on nn qubits is a map x↦U(x)x\mapsto U(x) from X\mathcal X to the unitary 2n×2n2^n\times2^n matrices, realised by a parameter-free circuit for each xx. It produces the feature state and the encoded density operator ∣ϕ(x)⟩=U(x)∣0n⟩∈C2n,ρ(x)=∣ϕ(x)⟩⟨ϕ(x)∣.\lvert\phi(x)\rangle=U(x)\lvert0^n\rangle\in\mathbb C^{2^n},\qquad\rho(x)=\lvert\phi(x)\rangle\langle\phi(x)\rvert . Since U(x)U(x) is unitary, ⟨ϕ(x)∣ϕ(x)⟩=⟨0n∣U(x)†U(x)∣0n⟩=1\langle\phi(x)\vert\phi(x)\rangle=\langle0^n\vert U(x)^\dagger U(x)\vert0^n\rangle=1, so ρ(x)\rho(x) is a rank-one orthogonal projector: ρ(x)†=ρ(x)\rho(x)^\dagger=\rho(x), ρ(x)2=ρ(x)\rho(x)^2=\rho(x), Tr ρ(x)=1\mathrm{Tr}\,\rho(x)=1. Multiplying ∣ϕ(x)⟩\lvert\phi(x)\rangle by a global phase eiαe^{i\alpha} leaves ρ(x)\rho(x) unchanged.

Definition

Fidelity kernel and quantum kernel matrix

The fidelity (quantum) kernel of a quantum feature map is K(x,x′)=∣⟨ϕ(x)∣ϕ(x′)⟩∣2,x,x′∈X.K(x,x')=\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2,\qquad x,x'\in\mathcal X . For training inputs x1,…,xMx_1,\dots,x_M the quantum kernel matrix (Gram matrix) is the real M×MM\times M matrix Kij=K(xi,xj)K_{ij}=K(x_i,x_j). For test inputs x1∗,…,xMt∗x^\ast_1,\dots,x^\ast_{M_t} the test kernel is the Mt×MM_t\times M matrix K(xa∗,xi)K(x^\ast_a,x_i).

Theorem

The fidelity kernel is a trace of a product of density operators

For all x,x′∈Xx,x'\in\mathcal X, K(x,x′)=Tr(ρ(x)ρ(x′)).K(x,x')=\mathrm{Tr}\big(\rho(x)\rho(x')\big). Moreover K(x,x′)=K(x′,x)K(x,x')=K(x',x), 0≤K(x,x′)≤10\le K(x,x')\le1, K(x,x)=1K(x,x)=1, with K(x,x′)=1K(x,x')=1 if and only if ∣ϕ(x′)⟩=eiα∣ϕ(x)⟩\lvert\phi(x')\rangle=e^{i\alpha}\lvert\phi(x)\rangle for some α∈R\alpha\in\mathbb R; and KK does not change when the feature states are multiplied by data-dependent global phases.

Proof (7 steps)
  1. Step 1:
    Tr(AB)=∑i=1p∑k=1qAikBki=∑k=1q∑i=1pBkiAik=Tr(BA),A∈Cp×q, B∈Cq×p\mathrm{Tr}(AB)=\sum_{i=1}^{p}\sum_{k=1}^{q}A_{ik}B_{ki}=\sum_{k=1}^{q}\sum_{i=1}^{p}B_{ki}A_{ik}=\mathrm{Tr}(BA),\qquad A\in\mathbb C^{p\times q},\ B\in\mathbb C^{q\times p}
    Cyclicity of the trace, valid also for rectangular factors: write out the diagonal entries of ABAB, exchange the two finite sums, and recognise the diagonal entries of BABA.
  2. Step 2:
    ρ(x)ρ(x′)=∣ϕ⟩(⟨ϕ∣ϕ′⟩)⟨ϕ′∣=⟨ϕ∣ϕ′⟩  ∣ϕ⟩⟨ϕ′∣\rho(x)\rho(x')=\lvert\phi\rangle\big(\langle\phi\vert\phi'\rangle\big)\langle\phi'\rvert=\langle\phi\vert\phi'\rangle\;\lvert\phi\rangle\langle\phi'\rvert
    Abbreviate ϕ=ϕ(x)\phi=\phi(x), ϕ′=ϕ(x′)\phi'=\phi(x'). Matrix multiplication is associative, and the middle factor ⟨ϕ∣ϕ′⟩\langle\phi\vert\phi'\rangle is a 1×11\times1 matrix, i.e. a scalar that can be moved to the front.
  3. Step 3:
    Tr(∣ϕ⟩⟨ϕ′∣)=Tr(⟨ϕ′∣ϕ⟩)=⟨ϕ′∣ϕ⟩\mathrm{Tr}\big(\lvert\phi\rangle\langle\phi'\rvert\big)=\mathrm{Tr}\big(\langle\phi'\vert\phi\rangle\big)=\langle\phi'\vert\phi\rangle
    Cyclicity with the column A=∣ϕ⟩∈C2n×1A=\lvert\phi\rangle\in\mathbb C^{2^n\times1} and the row B=⟨ϕ′∣∈C1×2nB=\langle\phi'\rvert\in\mathbb C^{1\times2^n}: BABA is the 1×11\times1 matrix ⟨ϕ′∣ϕ⟩\langle\phi'\vert\phi\rangle, whose trace is its only entry.
  4. Step 4:
    Tr(ρ(x)ρ(x′))=⟨ϕ∣ϕ′⟩ ⟨ϕ′∣ϕ⟩=⟨ϕ∣ϕ′⟩ ⟨ϕ∣ϕ′⟩‾=∣⟨ϕ∣ϕ′⟩∣2=K(x,x′)\mathrm{Tr}\big(\rho(x)\rho(x')\big)=\langle\phi\vert\phi'\rangle\,\langle\phi'\vert\phi\rangle=\langle\phi\vert\phi'\rangle\,\overline{\langle\phi\vert\phi'\rangle}=\lvert\langle\phi\vert\phi'\rangle\rvert^2=K(x,x')
    Linearity of the trace pulls out the scalar; conjugate symmetry of the inner product gives ⟨ϕ′∣ϕ⟩=⟨ϕ∣ϕ′⟩‾\langle\phi'\vert\phi\rangle=\overline{\langle\phi\vert\phi'\rangle}, and zzˉ=∣z∣2z\bar z=\lvert z\rvert^2.
  5. Step 5:
    K(x′,x)=Tr(ρ(x′)ρ(x))=Tr(ρ(x)ρ(x′))=K(x,x′)K(x',x)=\mathrm{Tr}\big(\rho(x')\rho(x)\big)=\mathrm{Tr}\big(\rho(x)\rho(x')\big)=K(x,x')
    Symmetry is cyclicity once more (or ∣zˉ∣=∣z∣\lvert\bar z\rvert=\lvert z\rvert).
  6. Step 6:
    0≤∣⟨ϕ∣ϕ′⟩∣2≤⟨ϕ∣ϕ⟩ ⟨ϕ′∣ϕ′⟩=1⋅1=10\le\lvert\langle\phi\vert\phi'\rangle\rvert^2\le\langle\phi\vert\phi\rangle\,\langle\phi'\vert\phi'\rangle=1\cdot1=1
    Cauchy–Schwarz inequality for the unit vectors ϕ,ϕ′\phi,\phi'; equality holds exactly when ϕ′\phi' is a scalar multiple c ϕc\,\phi, and ∥ϕ′∥=1\lVert\phi'\rVert=1 forces ∣c∣=1\lvert c\rvert=1, i.e. c=eiαc=e^{i\alpha}. In particular K(x,x)=1K(x,x)=1.
  7. Step 7:
    ∣⟨eiα(x)ϕ∣eiα(x′)ϕ′⟩∣2=∣ei(α(x′)−α(x))∣2∣⟨ϕ∣ϕ′⟩∣2=∣⟨ϕ∣ϕ′⟩∣2\big\lvert\langle e^{i\alpha(x)}\phi\vert e^{i\alpha(x')}\phi'\rangle\big\rvert^2=\big\lvert e^{i(\alpha(x')-\alpha(x))}\big\rvert^2\lvert\langle\phi\vert\phi'\rangle\rvert^2=\lvert\langle\phi\vert\phi'\rangle\rvert^2
    The bra conjugates its phase; a unimodular factor drops out of the modulus. Equivalently, ρ(x)\rho(x) itself is phase-free, so the right-hand side Tr(ρρ′)\mathrm{Tr}(\rho\rho') cannot depend on the phases.

∎

Derivation

Reading a kernel entry off a circuit

  1. Step 1:
    U(x′)†U(x)∣0n⟩ → measure  P(0n)=∣⟨0n∣U(x′)†U(x)∣0n⟩∣2U(x')^\dagger U(x)\lvert0^n\rangle\ \xrightarrow{\ \text{measure}\ }\ P(0^n)=\big\lvert\langle0^n\vert U(x')^\dagger U(x)\vert0^n\rangle\big\rvert^2
    Inversion (compute–uncompute) test: prepare ∣ϕ(x)⟩\lvert\phi(x)\rangle, apply the inverse circuit of x′x', measure all qubits; the Born rule gives the probability of the all-zero outcome.
  2. Step 2:
    ⟨0n∣U(x′)†=(U(x′)∣0n⟩)†=⟨ϕ(x′)∣ ⇒ P(0n)=∣⟨ϕ(x′)∣ϕ(x)⟩∣2=K(x,x′)\langle0^n\vert U(x')^\dagger=\big(U(x')\lvert0^n\rangle\big)^\dagger=\langle\phi(x')\rvert\ \Rightarrow\ P(0^n)=\lvert\langle\phi(x')\vert\phi(x)\rangle\rvert^2=K(x,x')
    (AB)†=B†A†(AB)^\dagger=B^\dagger A^\dagger; the all-zero probability is the kernel entry. It uses nn qubits and twice the depth of UU (lesson The Inversion Test).
  3. Step 3:
    SWAP test on ∣0⟩∣ϕ(x)⟩∣ϕ(x′)⟩:P(0)=12(1+K(x,x′)) ⇒ K=2P(0)−1\text{SWAP test on }\lvert0\rangle\lvert\phi(x)\rangle\lvert\phi(x')\rangle:\quad P(0)=\tfrac12\big(1+K(x,x')\big)\ \Rightarrow\ K=2P(0)-1
    The SWAP test (lesson The SWAP Test) needs 2n+12n+1 qubits and nn controlled-SWAP gates but no inverse circuit; it also works for states whose preparation is unknown.

Result

K(x,x′)=Pinversion(0n)=2PSWAP(0)−1\boxed{K(x,x')=P_{\text{inversion}}(0^n)=2P_{\text{SWAP}}(0)-1}

Quick check

The inversion-test circuit U(x′)†U(x)U(x')^\dagger U(x) is run NN times and the outcome 0⋯00\cdots0 appears N0N_0 times. Which quantity does N0/NN_0/N estimate?

Select one answer

Positive semidefiniteness and the Hilbert–Schmidt feature space#

Definition

Hilbert–Schmidt inner product on Hermitian matrices

Let Herm(d)={A∈Cd×d:A†=A}\mathrm{Herm}(d)=\{A\in\mathbb C^{d\times d}:A^\dagger=A\}, a real vector space of dimension d2d^2 (dd real diagonal entries and a real and an imaginary part for each of the d(d−1)/2d(d-1)/2 entries above the diagonal). The Hilbert–Schmidt inner product and norm are ⟨A,B⟩HS=Tr(A†B)=Tr(AB),∥A∥HS=Tr(A2)=(∑a,b∣Aab∣2)1/2=∥A∥F.\langle A,B\rangle_{HS}=\mathrm{Tr}(A^\dagger B)=\mathrm{Tr}(AB),\qquad\lVert A\rVert_{HS}=\sqrt{\mathrm{Tr}(A^2)}=\Big(\sum_{a,b}\lvert A_{ab}\rvert^2\Big)^{1/2}=\lVert A\rVert_F . The RKHS lesson showed that Tr(AB)\mathrm{Tr}(AB) is real for Hermitian A,BA,B and that it is a real inner product on Herm(d)\mathrm{Herm}(d). For nn qubits d=2nd=2^n and dim⁡RHerm(2n)=4n\dim_{\mathbb R}\mathrm{Herm}(2^n)=4^n.

Theorem

Every quantum kernel matrix is positive semidefinite

For every M∈NM\in\mathbb N, all inputs x1,…,xM∈Xx_1,\dots,x_M\in\mathcal X and all c∈RMc\in\mathbb R^M, ∑i,j=1Mcicj K(xi,xj)=Tr(A2)=∥A∥HS2 ≥ 0,A=∑i=1Mci ρ(xi).\sum_{i,j=1}^Mc_ic_j\,K(x_i,x_j)=\mathrm{Tr}(A^2)=\lVert A\rVert_{HS}^2\ \ge\ 0,\qquad A=\sum_{i=1}^Mc_i\,\rho(x_i). Hence every quantum kernel matrix is symmetric positive semidefinite, KK is a positive-definite (Mercer) kernel, and K(x,x′)=⟨ρ(x),ρ(x′)⟩HSK(x,x')=\langle\rho(x),\rho(x')\rangle_{HS} is the linear kernel of the feature space (Herm(2n),⟨⋅,⋅⟩HS)(\mathrm{Herm}(2^n),\langle\cdot,\cdot\rangle_{HS}) with feature map x↦ρ(x)x\mapsto\rho(x).

Proof (7 steps)
  1. Step 1:
    A†=∑ici‾ ρ(xi)†=∑ici ρ(xi)=AA^\dagger=\sum_i\overline{c_i}\,\rho(x_i)^\dagger=\sum_ic_i\,\rho(x_i)=A
    The coefficients are real and every ρ(xi)\rho(x_i) is Hermitian, so AA is Hermitian.
  2. Step 2:
    ∑i,jcicj K(xi,xj)=∑i,jcicj Tr(ρ(xi)ρ(xj))\sum_{i,j}c_ic_j\,K(x_i,x_j)=\sum_{i,j}c_ic_j\,\mathrm{Tr}\big(\rho(x_i)\rho(x_j)\big)
    Replace every kernel value by the trace identity of the previous theorem.
  3. Step 3:
    =Tr((∑iciρ(xi))(∑jcjρ(xj)))=Tr(A2)=\mathrm{Tr}\Big(\Big(\sum_ic_i\rho(x_i)\Big)\Big(\sum_jc_j\rho(x_j)\Big)\Big)=\mathrm{Tr}(A^2)
    The trace is linear and the matrix product is bilinear, so the double sum can be moved inside as a product of two finite sums.
  4. Step 4:
    Tr(A2)=Tr(A†A)=∑b∑aAab‾ Aab=∑a,b∣Aab∣2=∥A∥HS2≥0\mathrm{Tr}(A^2)=\mathrm{Tr}(A^\dagger A)=\sum_{b}\sum_{a}\overline{A_{ab}}\,A_{ab}=\sum_{a,b}\lvert A_{ab}\rvert^2=\lVert A\rVert_{HS}^2\ge0
    Use A=A†A=A^\dagger; the diagonal entry (A†A)bb=∑aAab‾Aab(A^\dagger A)_{bb}=\sum_a\overline{A_{ab}}A_{ab} is a sum of squared moduli, and so is the trace. It vanishes only for A=0A=0.
  5. Step 5:
    Kij=Kji,c⊤Kc≥0  ∀c∈RM ⇒ K⪰0K_{ij}=K_{ji},\quad c^\top Kc\ge0\ \ \forall c\in\mathbb R^M\ \Rightarrow\ K\succeq0
    Symmetry was proved before; together with the nonnegative quadratic form this is the definition of a positive-definite kernel from the RKHS lesson.
  6. Step 6:
    K(x,x′)=⟨ρ(x),ρ(x′)⟩HS ⇒ ∃ HK,f∗(x)=∑i=1MαiK(x,xi)K(x,x')=\langle\rho(x),\rho(x')\rangle_{HS}\ \Rightarrow\ \exists\,\mathcal H_K,\quad f^\ast(x)=\sum_{i=1}^M\alpha_iK(x,x_i)
    By the Moore–Aronszajn construction KK has a unique RKHS, and the representer theorem reduces training in it to MM coefficients αi\alpha_i.
  7. Step 7:
    ρ(x)=∑kpk(x)∣ϕk(x)⟩⟨ϕk(x)∣ ⇒ ∑i,jcicj Tr(ρ(xi)ρ(xj))=∥A∥HS2≥0\rho(x)=\sum_kp_k(x)\lvert\phi_k(x)\rangle\langle\phi_k(x)\rvert\ \Rightarrow\ \sum_{i,j}c_ic_j\,\mathrm{Tr}\big(\rho(x_i)\rho(x_j)\big)=\lVert A\rVert_{HS}^2\ge0
    The proof used only that each ρ(xi)\rho(x_i) is Hermitian, so Tr(ρ(x)ρ(x′))\mathrm{Tr}\big(\rho(x)\rho(x')\big) remains a valid kernel when noise turns the encoded states into mixed states (it is then no longer equal to the fidelity, and K(x,x)=Tr ρ(x)2<1K(x,x)=\mathrm{Tr}\,\rho(x)^2<1).

∎

Proposition

The quantum kernel matrix is a Gram matrix of vectorised density operators

Let vec(A)∈Cd2\mathrm{vec}(A)\in\mathbb C^{d^2} list the entries of A∈Cd×dA\in\mathbb C^{d\times d}. Then K(x,x′)=vec(ρ(x))†vec(ρ(x′))K(x,x')=\mathrm{vec}\big(\rho(x)\big)^\dagger\mathrm{vec}\big(\rho(x')\big), so K=V†V,V=[vec ρ(x1) ∣ ⋯ ∣ vec ρ(xM)]∈C4n×M,rank K≤min⁡(M,4n).K=V^\dagger V,\qquad V=\big[\mathrm{vec}\,\rho(x_1)\ \big\vert\ \cdots\ \big\vert\ \mathrm{vec}\,\rho(x_M)\big]\in\mathbb C^{4^n\times M},\qquad\mathrm{rank}\,K\le\min(M,4^n). In real coordinates: with the 4n4^n Pauli strings PP and cP(x)=Tr(Pρ(x))∈[−1,1]c_P(x)=\mathrm{Tr}\big(P\rho(x)\big)\in[-1,1], ρ(x)=2−n∑PcP(x) P,K(x,x′)=2−n∑PcP(x) cP(x′),\rho(x)=2^{-n}\sum_Pc_P(x)\,P,\qquad K(x,x')=2^{-n}\sum_Pc_P(x)\,c_P(x'), the Euclidean Gram matrix of the real feature vectors 2−n/2(cP(x))P∈R4n2^{-n/2}\big(c_P(x)\big)_P\in\mathbb R^{4^n}. For one qubit this reads K=12(1+r⃗⋅r⃗ ′)K=\tfrac12(1+\vec r\cdot\vec r\,') with the Bloch vectors r⃗,r⃗ ′\vec r,\vec r\,'.

Proof (7 steps)
  1. Step 1:
    vec(A)†vec(B)=∑a,bAab‾ Bab=∑b∑a(A†)baBab=∑b(A†B)bb=Tr(A†B)\mathrm{vec}(A)^\dagger\mathrm{vec}(B)=\sum_{a,b}\overline{A_{ab}}\,B_{ab}=\sum_{b}\sum_{a}(A^\dagger)_{ba}B_{ab}=\sum_b(A^\dagger B)_{bb}=\mathrm{Tr}(A^\dagger B)
    The standard inner product of the vectorised matrices is the Hilbert–Schmidt inner product: (A†)ba=Aab‾(A^\dagger)_{ba}=\overline{A_{ab}}.
  2. Step 2:
    vec(ρ(x))†vec(ρ(x′))=Tr(ρ(x)ρ(x′))=K(x,x′),(V†V)ij=Kij\mathrm{vec}\big(\rho(x)\big)^\dagger\mathrm{vec}\big(\rho(x')\big)=\mathrm{Tr}\big(\rho(x)\rho(x')\big)=K(x,x'),\qquad(V^\dagger V)_{ij}=K_{ij}
    Insert A=ρ(x)=A†A=\rho(x)=A^\dagger, B=ρ(x′)B=\rho(x') and use the trace identity; entry (i,j)(i,j) of V†VV^\dagger V is the inner product of columns ii and jj.
  3. Step 3:
    c⊤Kc=c⊤V†Vc=(Vc)†(Vc)=∥Vc∥2≥0,rank(V†V)=rank V≤min⁡(M,4n)c^\top K c=c^\top V^\dagger Vc=(Vc)^\dagger(Vc)=\lVert Vc\rVert^2\ge0,\qquad\mathrm{rank}(V^\dagger V)=\mathrm{rank}\,V\le\min(M,4^n)
    A second proof of positive semidefiniteness (for real cc, c⊤=c†c^\top=c^\dagger). V†Vc=0V^\dagger Vc=0 implies ∥Vc∥2=0\lVert Vc\rVert^2=0, so V†VV^\dagger V and VV have the same kernel and the same rank; VV has MM columns and 4n4^n rows.
  4. Step 4:
    P=σa1⊗⋯⊗σan,Tr(PQ)=∏k=1nTr(σakσbk)=∏k=1n2δakbk=2nδPQP=\sigma_{a_1}\otimes\cdots\otimes\sigma_{a_n},\quad\mathrm{Tr}(PQ)=\prod_{k=1}^n\mathrm{Tr}\big(\sigma_{a_k}\sigma_{b_k}\big)=\prod_{k=1}^n2\delta_{a_kb_k}=2^n\delta_{PQ}
    Pauli strings with σ0=I\sigma_0=I, σ1,2,3=X,Y,Z\sigma_{1,2,3}=X,Y,Z. The mixed-product rule and Tr(A⊗B)=TrA TrB\mathrm{Tr}(A\otimes B)=\mathrm{Tr}A\,\mathrm{Tr}B reduce the trace to one qubit, where Tr(σaσb)=2δab\mathrm{Tr}(\sigma_a\sigma_b)=2\delta_{ab} (σa2=I\sigma_a^2=I, and σaσb=±iσc\sigma_a\sigma_b=\pm i\sigma_c is traceless for distinct non-identity indices, as is each σa\sigma_a with a≥1a\ge1).
  5. Step 5:
    {P} orthogonal, #{P}=4n=dim⁡RHerm(2n) ⇒ ρ=∑PwPP,Tr(Qρ)=2nwQ\{P\}\ \text{orthogonal},\ \#\{P\}=4^n=\dim_{\mathbb R}\mathrm{Herm}(2^n)\ \Rightarrow\ \rho=\sum_Pw_PP,\quad\mathrm{Tr}(Q\rho)=2^nw_Q
    The 4n4^n Hermitian Pauli strings are pairwise orthogonal, hence linearly independent, hence a basis of Herm(2n)\mathrm{Herm}(2^n). Multiplying the expansion by QQ and taking the trace isolates one coefficient, so wQ=2−ncQ(x)w_Q=2^{-n}c_Q(x). Each cPc_P is real (an inner product of Hermitian matrices) and ∣cP∣≤1\lvert c_P\rvert\le1 because it is the expectation value of an observable with eigenvalues ±1\pm1.
  6. Step 6:
    Tr(ρ(x)ρ(x′))=2−2n∑P,QcP(x)cQ(x′) Tr(PQ)=2−n∑PcP(x) cP(x′)\mathrm{Tr}\big(\rho(x)\rho(x')\big)=2^{-2n}\sum_{P,Q}c_P(x)c_Q(x')\,\mathrm{Tr}(PQ)=2^{-n}\sum_Pc_P(x)\,c_P(x')
    Insert both expansions and use Tr(PQ)=2nδPQ\mathrm{Tr}(PQ)=2^n\delta_{PQ}.
  7. Step 7:
    n=1: (cI,cX,cY,cZ)=(1,rx,ry,rz) ⇒ K=12(1+r⃗⋅r⃗ ′)n=1:\ \big(c_I,c_X,c_Y,c_Z\big)=(1,r_x,r_y,r_z)\ \Rightarrow\ K=\tfrac12\big(1+\vec r\cdot\vec r\,'\big)
    cI=Tr ρ=1c_I=\mathrm{Tr}\,\rho=1 and (cX,cY,cZ)(c_X,c_Y,c_Z) is the Bloch vector, so the single-qubit fidelity kernel is an affine function of the Euclidean inner product of Bloch vectors.

∎

Proposition

The RKHS of a fidelity kernel consists of expectation values

Let S=spanR{ρ(x):x∈X}⊆Herm(2n)\mathcal S=\mathrm{span}_{\mathbb R}\{\rho(x):x\in\mathcal X\}\subseteq\mathrm{Herm}(2^n) and fO(x)=Tr(Oρ(x))=⟨ϕ(x)∣O∣ϕ(x)⟩f_O(x)=\mathrm{Tr}\big(O\rho(x)\big)=\langle\phi(x)\vert O\vert\phi(x)\rangle. Then HK={fO:O∈S},⟨fO,fO′⟩HK=Tr(OO′),∥fO∥HK=∥O∥HS,\mathcal H_K=\{f_O:O\in\mathcal S\},\qquad\langle f_O,f_{O'}\rangle_{\mathcal H_K}=\mathrm{Tr}(OO'),\qquad\lVert f_O\rVert_{\mathcal H_K}=\lVert O\rVert_{HS}, dim⁡HK=dim⁡S≤4n\dim\mathcal H_K=\dim\mathcal S\le4^n, and every Hermitian observable OO defines a function fO∈HKf_O\in\mathcal H_K. The trained kernel model is the expectation value of the observable O∗=∑iαiρ(xi)O^\ast=\sum_i\alpha_i\rho(x_i).

Proof (7 steps)
  1. Step 1:
    K(⋅,x)=Tr(ρ(x)ρ(⋅))=fρ(x)K(\cdot,x)=\mathrm{Tr}\big(\rho(x)\rho(\cdot)\big)=f_{\rho(x)}
    Every kernel section is the expectation value of the observable ρ(x)∈S\rho(x)\in\mathcal S.
  2. Step 2:
    ∑iaiK(⋅,xi)=fA,A=∑iaiρ(xi)∈S;H0={fO:O∈S}\sum_ia_iK(\cdot,x_i)=f_A,\quad A=\sum_ia_i\rho(x_i)\in\mathcal S;\qquad\mathcal H_0=\{f_O:O\in\mathcal S\}
    Linearity of O↦fOO\mapsto f_O. Conversely every O∈SO\in\mathcal S is a finite real combination of encoded states, so the pre-Hilbert space H0\mathcal H_0 of finite kernel combinations from the RKHS lesson is exactly {fO:O∈S}\{f_O:O\in\mathcal S\}.
  3. Step 3:
    ⟨∑iaiK(⋅,xi),∑jbjK(⋅,yj)⟩=∑i,jaibj Tr(ρ(xi)ρ(yj))=Tr(AB)\Big\langle\sum_ia_iK(\cdot,x_i),\sum_jb_jK(\cdot,y_j)\Big\rangle=\sum_{i,j}a_ib_j\,\mathrm{Tr}\big(\rho(x_i)\rho(y_j)\big)=\mathrm{Tr}(AB)
    The Moore–Aronszajn inner product ∑ijaibjk(xi,yj)\sum_{ij}a_ib_jk(x_i,y_j) with the trace identity and bilinearity, where B=∑jbjρ(yj)B=\sum_jb_j\rho(y_j).
  4. Step 4:
    O=∑iciρ(xi)∈S, fO≡0 ⇒ Tr(O2)=∑ici Tr(Oρ(xi))=∑icifO(xi)=0 ⇒ O=0O=\sum_ic_i\rho(x_i)\in\mathcal S,\ f_O\equiv0\ \Rightarrow\ \mathrm{Tr}(O^2)=\sum_ic_i\,\mathrm{Tr}\big(O\rho(x_i)\big)=\sum_ic_if_O(x_i)=0\ \Rightarrow\ O=0
    O↦fOO\mapsto f_O is injective on S\mathcal S, so the norm ∥fO∥=∥O∥HS\lVert f_O\rVert=\lVert O\rVert_{HS} is well defined and O↦fOO\mapsto f_O is an isometric isomorphism S→H0\mathcal S\to\mathcal H_0.
  5. Step 5:
    dim⁡H0=dim⁡S≤dim⁡RHerm(2n)=4n<∞ ⇒ HK=H0\dim\mathcal H_0=\dim\mathcal S\le\dim_{\mathbb R}\mathrm{Herm}(2^n)=4^n<\infty\ \Rightarrow\ \mathcal H_K=\mathcal H_0
    A finite-dimensional inner-product space is complete, so the completion step of the construction adds nothing.
  6. Step 6:
    O∈Herm(2n), O=OS+O⊥, O⊥⊥HSS ⇒ fO(x)=Tr(OSρ(x))+Tr(O⊥ρ(x))⏟=0=fOS(x)O\in\mathrm{Herm}(2^n),\ O=O_{\mathcal S}+O_\perp,\ O_\perp\perp_{HS}\mathcal S\ \Rightarrow\ f_O(x)=\mathrm{Tr}\big(O_{\mathcal S}\rho(x)\big)+\underbrace{\mathrm{Tr}\big(O_\perp\rho(x)\big)}_{=0}=f_{O_{\mathcal S}}(x)
    Orthogonal decomposition in the finite-dimensional space Herm(2n)\mathrm{Herm}(2^n); ρ(x)∈S\rho(x)\in\mathcal S is orthogonal to O⊥O_\perp. So any measured observable gives a function in HK\mathcal H_K, with norm ∥OS∥HS≤∥O∥HS\lVert O_{\mathcal S}\rVert_{HS}\le\lVert O\rVert_{HS}.
  7. Step 7:
    f∗(x)=∑iαiK(x,xi)=Tr(O∗ρ(x)),O∗=∑iαiρ(xi),∥f∗∥HK2=α⊤Kαf^\ast(x)=\sum_i\alpha_iK(x,x_i)=\mathrm{Tr}\big(O^\ast\rho(x)\big),\quad O^\ast=\sum_i\alpha_i\rho(x_i),\quad\lVert f^\ast\rVert_{\mathcal H_K}^2=\alpha^\top K\alpha
    The representer form is the expectation value of one optimal observable, and the regulariser of kernel ridge regression or the SVM is its squared Hilbert–Schmidt norm. A variational classifier that measures W(θ)†HW(θ)W(\theta)^\dagger HW(\theta) after the same encoding searches a subset of these functions (Stage 4).

∎

Quick check

A quantum kernel matrix is estimated on hardware with 200200 shots per entry, and its smallest eigenvalue comes out as −0.03-0.03. What is the correct conclusion?

Select one answer

Closed form for product encodings#

For a general entangling feature map the kernel has no simple formula and must be simulated or measured. For the product (angle) encodings of the lesson Angle & Phase Encoding, in which feature xjx_j is written into qubit jj by one rotation, the kernel factorises and can be computed exactly. The closed form is the basis of the lab and of the concentration analysis in the next section.

Theorem

Fidelity kernel of a product encoding

Let U(x)=⨂j=0n−1RP(s xj)U(x)=\bigotimes_{j=0}^{n-1}R_P(s\,x_j) with P∈{X,Y}P\in\{X,Y\} and a scale s>0s>0 (qubit jj carries feature xjx_j). Then ⟨ϕ(x)∣ϕ(x′)⟩=∏j=0n−1cos⁡s(xj′−xj)2,K(x,x′)=∏j=0n−1cos⁡2s(xj−xj′)2=∏j=0n−11+cos⁡(s(xj−xj′))2.\langle\phi(x)\vert\phi(x')\rangle=\prod_{j=0}^{n-1}\cos\frac{s(x'_j-x_j)}{2},\qquad K(x,x')=\prod_{j=0}^{n-1}\cos^2\frac{s(x_j-x'_j)}{2}=\prod_{j=0}^{n-1}\frac{1+\cos\big(s(x_j-x'_j)\big)}{2}. The same kernel is obtained for the phase encoding U(x)=⨂jRZ(s xj)HU(x)=\bigotimes_jR_Z(s\,x_j)H. It has the explicit real feature map ψ(x)=⨂j2−1/2(1,cos⁡sxj,sin⁡sxj)∈R3n\psi(x)=\bigotimes_j2^{-1/2}\big(1,\cos sx_j,\sin sx_j\big)\in\mathbb R^{3^n}, so every product-encoding Gram matrix has rank at most min⁡(M,3n)\min(M,3^n), below the general bound 4n4^n.

Proof (9 steps)
  1. Step 1:
    RP(θ)=e−iθP/2=∑k≥0(−iθ/2)kk!Pk=cos⁡θ2 I−isin⁡θ2 PR_P(\theta)=e^{-i\theta P/2}=\sum_{k\ge0}\frac{(-i\theta/2)^k}{k!}P^k=\cos\frac\theta2\,I-i\sin\frac\theta2\,P
    Exponential series; since P2=IP^2=I, the even powers are II and the odd powers are PP, which sum to the cosine and sine series.
  2. Step 2:
    RP(a)†RP(b)=eiaP/2e−ibP/2=e−i(b−a)P/2=RP(b−a)R_P(a)^\dagger R_P(b)=e^{iaP/2}e^{-ibP/2}=e^{-i(b-a)P/2}=R_P(b-a)
    Exponentials of multiples of the same operator commute, so their exponents add; RP(a)†=RP(−a)R_P(a)^\dagger=R_P(-a).
  3. Step 3:
    ⟨0∣RP(θ)∣0⟩=cos⁡θ2−isin⁡θ2 ⟨0∣P∣0⟩=cos⁡θ2\langle0\vert R_P(\theta)\vert0\rangle=\cos\frac\theta2-i\sin\frac\theta2\,\langle0\vert P\vert0\rangle=\cos\frac\theta2
    X∣0⟩=∣1⟩X\lvert0\rangle=\lvert1\rangle and Y∣0⟩=i∣1⟩Y\lvert0\rangle=i\lvert1\rangle are orthogonal to ∣0⟩\lvert0\rangle, so ⟨0∣X∣0⟩=⟨0∣Y∣0⟩=0\langle0\vert X\vert0\rangle=\langle0\vert Y\vert0\rangle=0.
  4. Step 4:
    ⟨ϕ(x)∣ϕ(x′)⟩=⟨0n∣⨂jRP(sxj)†⨂jRP(sxj′)∣0n⟩=∏j=0n−1⟨0∣RP(sxj)†RP(sxj′)∣0⟩\langle\phi(x)\vert\phi(x')\rangle=\langle0^n\vert\bigotimes_jR_P(sx_j)^\dagger\bigotimes_jR_P(sx'_j)\vert0^n\rangle=\prod_{j=0}^{n-1}\langle0\vert R_P(sx_j)^\dagger R_P(sx'_j)\vert0\rangle
    (⨂jAj)†=⨂jAj†(\bigotimes_jA_j)^\dagger=\bigotimes_jA_j^\dagger, the mixed-product rule (⨂jAj)(⨂jBj)=⨂jAjBj(\bigotimes_jA_j)(\bigotimes_jB_j)=\bigotimes_jA_jB_j, and the factorisation of inner products of product vectors.
  5. Step 5:
    =∏j=0n−1⟨0∣RP(s(xj′−xj))∣0⟩=∏j=0n−1cos⁡s(xj′−xj)2=\prod_{j=0}^{n-1}\langle0\vert R_P\big(s(x'_j-x_j)\big)\vert0\rangle=\prod_{j=0}^{n-1}\cos\frac{s(x'_j-x_j)}{2}
    The second and third steps, factor by factor.
  6. Step 6:
    K(x,x′)=∏jcos⁡2s(xj′−xj)2=∏jcos⁡2s(xj−xj′)2=∏j1+cos⁡(s(xj−xj′))2K(x,x')=\prod_{j}\cos^2\frac{s(x'_j-x_j)}{2}=\prod_{j}\cos^2\frac{s(x_j-x'_j)}{2}=\prod_j\frac{1+\cos\big(s(x_j-x'_j)\big)}{2}
    The overlap is real, so its squared modulus is its square; cosine is even; cos⁡2u=1+cos⁡2u2\cos^2u=\frac{1+\cos2u}{2}.
  7. Step 7:
    ⟨+∣RZ(θ)∣+⟩=cos⁡θ2−isin⁡θ2 ⟨+∣Z∣+⟩=cos⁡θ2\langle+\vert R_Z(\theta)\vert+\rangle=\cos\frac\theta2-i\sin\frac\theta2\,\langle+\vert Z\vert+\rangle=\cos\frac\theta2
    Phase encoding: the same argument with ∣0⟩\lvert0\rangle replaced by ∣+⟩=H∣0⟩\lvert+\rangle=H\lvert0\rangle and P=ZP=Z, since Z∣+⟩=∣−⟩⊥∣+⟩Z\lvert+\rangle=\lvert-\rangle\perp\lvert+\rangle.
  8. Step 8:
    1+cos⁡(u−u′)2=12(1+cos⁡ucos⁡u′+sin⁡usin⁡u′)=ψ1(u)⊤ψ1(u′),ψ1(u)=12(1,cos⁡u,sin⁡u)\frac{1+\cos(u-u')}{2}=\tfrac12\big(1+\cos u\cos u'+\sin u\sin u'\big)=\psi_1(u)^\top\psi_1(u'),\qquad\psi_1(u)=\tfrac1{\sqrt2}(1,\cos u,\sin u)
    Addition theorem: each one-qubit factor is the inner product of three-dimensional real feature vectors.
  9. Step 9:
    K(x,x′)=∏jψ1(sxj)⊤ψ1(sxj′)=(⨂jψ1(sxj))⊤(⨂jψ1(sxj′)),rank K≤min⁡(M,3n)K(x,x')=\prod_j\psi_1(sx_j)^\top\psi_1(sx'_j)=\Big(\bigotimes_j\psi_1(sx_j)\Big)^\top\Big(\bigotimes_j\psi_1(sx'_j)\Big),\qquad\mathrm{rank}\,K\le\min(M,3^n)
    (a⊗b)⊤(c⊗d)=(a⊤c)(b⊤d)(a\otimes b)^\top(c\otimes d)=(a^\top c)(b^\top d); the Gram matrix is Ψ⊤Ψ\Psi^\top\Psi with Ψ∈R3n×M\Psi\in\mathbb R^{3^n\times M}, whose rank is at most its number of rows. For two features and 2424 random points the Gram matrix has exactly 99 nonzero eigenvalues.

∎

Derivation

Cross-check with Bloch vectors (one qubit)

  1. Step 1:
    RX(x)∣0⟩=cos⁡x2∣0⟩−isin⁡x2∣1⟩=α∣0⟩+β∣1⟩R_X(x)\lvert0\rangle=\cos\frac x2\lvert0\rangle-i\sin\frac x2\lvert1\rangle=\alpha\lvert0\rangle+\beta\lvert1\rangle
    First column of RX(x)=(cos⁡x2−isin⁡x2−isin⁡x2cos⁡x2)R_X(x)=\begin{pmatrix}\cos\frac x2&-i\sin\frac x2\\-i\sin\frac x2&\cos\frac x2\end{pmatrix}.
  2. Step 2:
    r⃗=(2 Re(αˉβ), 2 Im(αˉβ), ∣α∣2−∣β∣2)=(0, −sin⁡x, cos⁡x)\vec r=\big(2\,\mathrm{Re}(\bar\alpha\beta),\ 2\,\mathrm{Im}(\bar\alpha\beta),\ \lvert\alpha\rvert^2-\lvert\beta\rvert^2\big)=(0,\ -\sin x,\ \cos x)
    αˉβ=−icos⁡x2sin⁡x2=−i2sin⁡x\bar\alpha\beta=-i\cos\frac x2\sin\frac x2=-\frac i2\sin x and cos⁡2x2−sin⁡2x2=cos⁡x\cos^2\frac x2-\sin^2\frac x2=\cos x: RXR_X moves the Bloch vector on the great circle of the yzyz-plane.
  3. Step 3:
    K(x,x′)=12(1+r⃗⋅r⃗ ′)=12(1+sin⁡xsin⁡x′+cos⁡xcos⁡x′)=12(1+cos⁡(x−x′))=cos⁡2x−x′2K(x,x')=\tfrac12\big(1+\vec r\cdot\vec r\,'\big)=\tfrac12\big(1+\sin x\sin x'+\cos x\cos x'\big)=\tfrac12\big(1+\cos(x-x')\big)=\cos^2\frac{x-x'}2
    The Pauli-coordinate formula for one qubit, the addition theorem for the cosine, and the half-angle identity: the same result as the theorem with n=1n=1, s=1s=1. Geometrically, x−x′x-x' is the angle between the two Bloch vectors.
Derivation

Worked example: x = (0.3, 1.2), x′ = (1.0, 0.4) with the R_X encoding

  1. Step 1:
    x−x′=(0.3−1.0, 1.2−0.4)=(−0.7, 0.8),12(x−x′)=(−0.35, 0.4)x-x'=(0.3-1.0,\ 1.2-0.4)=(-0.7,\ 0.8),\qquad\tfrac12(x-x')=(-0.35,\ 0.4)
    Feature-wise differences and their halves (scale s=1s=1).
  2. Step 2:
    ∣ϕ(x)⟩=(cos⁡0.15−isin⁡0.15)⊗(cos⁡0.6−isin⁡0.6)≈(0.81607−0.55830 i−0.12334 i−0.08438)\lvert\phi(x)\rangle=\begin{pmatrix}\cos0.15\\-i\sin0.15\end{pmatrix}\otimes\begin{pmatrix}\cos0.6\\-i\sin0.6\end{pmatrix}\approx\begin{pmatrix}0.81607\\-0.55830\,i\\-0.12334\,i\\-0.08438\end{pmatrix}
    The encoded state of xx as a Kronecker product (qubit 00 is the left factor): cos⁡0.15cos⁡0.6\cos0.15\cos0.6, −icos⁡0.15sin⁡0.6-i\cos0.15\sin0.6, −isin⁡0.15cos⁡0.6-i\sin0.15\cos0.6, (−i)2sin⁡0.15sin⁡0.6(-i)^2\sin0.15\sin0.6.
  3. Step 3:
    ∣ϕ(x′)⟩=(cos⁡0.5−isin⁡0.5)⊗(cos⁡0.2−isin⁡0.2)≈(0.86009−0.17435 i−0.46987 i−0.09525)\lvert\phi(x')\rangle=\begin{pmatrix}\cos0.5\\-i\sin0.5\end{pmatrix}\otimes\begin{pmatrix}\cos0.2\\-i\sin0.2\end{pmatrix}\approx\begin{pmatrix}0.86009\\-0.17435\,i\\-0.46987\,i\\-0.09525\end{pmatrix}
    The same for x′=(1.0,0.4)x'=(1.0,0.4).
  4. Step 4:
    ⟨ϕ(x)∣ϕ(x′)⟩≈0.81607⋅0.86009+0.55830⋅0.17435+0.12334⋅0.46987+0.08438⋅0.09525≈0.86522\langle\phi(x)\vert\phi(x')\rangle\approx0.81607\cdot0.86009+0.55830\cdot0.17435+0.12334\cdot0.46987+0.08438\cdot0.09525\approx0.86522
    Direct inner product: conjugating the bra turns −i-i into +i+i, and (+i)(−i)=1(+i)(-i)=1, so all four terms are positive.
  5. Step 5:
    cos⁡(0.35)cos⁡(0.4)=0.939373×0.921061=0.865220\cos(0.35)\cos(0.4)=0.939373\times0.921061=0.865220
    The closed form gives the same overlap without writing any state vector.
  6. Step 6:
    K(x,x′)=cos⁡2(0.35)cos⁡2(0.4)=0.882421×0.848353=0.748605K(x,x')=\cos^2(0.35)\cos^2(0.4)=0.882421\times0.848353=0.748605
    Square the overlap. On hardware, 10001000 inversion-test shots would return 0000 about 749749 times, with standard deviation 1000⋅0.7486⋅0.2514≈13.7\sqrt{1000\cdot0.7486\cdot0.2514}\approx13.7.

Result

K((0.3,1.2),(1.0,0.4))=cos⁡2(0.35)cos⁡2(0.4)=0.7486048950…\boxed{K\big((0.3,1.2),(1.0,0.4)\big)=\cos^2(0.35)\cos^2(0.4)=0.7486048950\ldots}

Circuit · 2 qubits

Quantum circuit on 2 qubitsRX(0.30) on q0; RX(1.20) on q1q0q1RX(0.30)RX(1.20)

The RXR_X product encoding of x=(0.3,1.2)x=(0.3,1.2): RX(0.3)R_X(0.3) on qubit 00 and RX(1.2)R_X(1.2) on qubit 11. The statevector is the product state ∣ϕ(x)⟩\lvert\phi(x)\rangle of the worked example.

∣ψ⟩=0.8161∣00⟩−0.5583i∣01⟩−0.1233i∣10⟩−0.0844∣11⟩\lvert\psi\rangle = 0.8161\lvert 00\rangle - 0.5583i\lvert 01\rangle - 0.1233i\lvert 10\rangle - 0.0844\lvert 11\rangle
U(x)=RX(0.3)⊗RX(1.2)=(c0c1−ic0s1−is0c1−s0s1−ic0s1c0c1−s0s1−is0c1−is0c1−s0s1c0c1−ic0s1−s0s1−is0c1−ic0s1c0c1),c0=cos⁡0.15, s0=sin⁡0.15, c1=cos⁡0.6, s1=sin⁡0.6U(x)=R_X(0.3)\otimes R_X(1.2)=\begin{pmatrix}c_0c_1&-ic_0s_1&-is_0c_1&-s_0s_1\\-ic_0s_1&c_0c_1&-s_0s_1&-is_0c_1\\-is_0c_1&-s_0s_1&c_0c_1&-ic_0s_1\\-s_0s_1&-is_0c_1&-ic_0s_1&c_0c_1\end{pmatrix},\quad c_0=\cos0.15,\ s_0=\sin0.15,\ c_1=\cos0.6,\ s_1=\sin0.6
U(x) = R_X(0.3) ⊗ R_X(1.2)4×4

Unitary verified: U†U=IU^\dagger U = I (max deviation 1.4e-17)

The heatmap shows the Gram matrix of 1616 points of the two-circles dataset (features min–max scaled to [0,π][0,\pi]) under the RXR_X product encoding, together with its eigenvalues. Because the kernel depends only on the differences xj−xj′x_j-x'_j, it is a translation-invariant kernel, a product of nn one-dimensional cosine kernels; nearby points have entries close to 11. Switch the encoding to the ZZ feature map below: its entangling Z⊗ZZ\otimes Z phases make the kernel depend on products of features, the block structure changes, and no closed form is available.

Quick check

Two features are encoded with RYR_Y rotations (scale s=1s=1). What is K(x,x′)K(x,x') for x=(0,0)x=(0,0) and x′=(π/2,π/3)x'=(\pi/2,\pi/3)?

tolerance ±0.000001

Exponential concentration#

Definition

Exponential concentration of a kernel

Let KnK_n be a family of quantum kernels on nn qubits and let x,x′x,x' be drawn independently from data distributions Dn\mathcal D_n. The family is exponentially concentrated (towards μn\mu_n) if there is b>1b>1 with Varx,x′[Kn(x,x′)]∈O(b−n).\mathrm{Var}_{x,x'}\big[K_n(x,x')\big]\in O(b^{-n}). By Chebyshev's inequality, for every fixed t>0t>0 the probability P(∣Kn(x,x′)−μn∣≥t)P\big(\lvert K_n(x,x')-\mu_n\rvert\ge t\big), μn=E[Kn]\mu_n=\mathbb E[K_n], is then O(b−n)O(b^{-n}): almost every pair of inputs has essentially the same kernel value (Thanasilp et al. 2024).

Lemma

The difference of a uniform angle and any independent angle is uniform

Let x,x′∈[0,2π)x,x'\in[0,2\pi) be independent with xx uniform. Then δ=(x−x′) mod 2π\delta=(x-x')\bmod2\pi is uniform on [0,2π)[0,2\pi) and independent of x′x', and for every 2π2\pi-periodic integrable gg, E[g(x−x′)]=12π∫02πg(δ) dδ.\mathbb E\big[g(x-x')\big]=\frac1{2\pi}\int_0^{2\pi}g(\delta)\,\mathrm d\delta .

Proof (4 steps)
  1. Step 1:
    τx′:[0,2π)→[0,2π),τx′(x)=(x−x′) mod 2π\tau_{x'}:[0,2\pi)\to[0,2\pi),\quad\tau_{x'}(x)=(x-x')\bmod2\pi
    For fixed x′x', τx′\tau_{x'} is a rotation of the circle R/2πZ\mathbb R/2\pi\mathbb Z: a bijection that maps every interval to an interval (or a union of two intervals) of the same total length.
  2. Step 2:
    P(δ∈B∣x′)=P(x∈τx′−1(B))=∣τx′−1(B)∣2π=∣B∣2πP\big(\delta\in B\mid x'\big)=P\big(x\in\tau_{x'}^{-1}(B)\big)=\frac{\lvert\tau_{x'}^{-1}(B)\rvert}{2\pi}=\frac{\lvert B\rvert}{2\pi}
    xx is uniform and independent of x′x', and τx′−1\tau_{x'}^{-1} preserves length (translation invariance of length on the circle), for every interval B⊆[0,2π)B\subseteq[0,2\pi).
  3. Step 3:
    P(δ∈B∣x′)=∣B∣2π  ∀x′ ⇒ δ∼U[0,2π),  δ⊥x′P(\delta\in B\mid x')=\tfrac{\lvert B\rvert}{2\pi}\ \ \forall x'\ \Rightarrow\ \delta\sim U[0,2\pi),\ \ \delta\perp x'
    The conditional law does not depend on x′x', so it is also the unconditional law, and δ\delta is independent of x′x'. Note that x′x' need not be uniform.
  4. Step 4:
    g(x−x′)=g(δ) ⇒ E[g(x−x′)]=E[g(δ)]=12π∫02πg(δ) dδg(x-x')=g(\delta)\ \Rightarrow\ \mathbb E\big[g(x-x')\big]=\mathbb E[g(\delta)]=\frac1{2\pi}\int_0^{2\pi}g(\delta)\,\mathrm d\delta
    x−x′x-x' and δ\delta differ by a multiple of 2π2\pi, which a 2π2\pi-periodic function does not see.

∎

Theorem

Mean and variance of the product-encoding kernel

Let K(x,x′)=∏j=0n−1cos⁡2xj−xj′2K(x,x')=\prod_{j=0}^{n-1}\cos^2\frac{x_j-x'_j}{2} (the RXR_X or RYR_Y product encoding with s=1s=1), and let all 2n2n coordinates of x,x′x,x' be independent and uniform on [0,2π)[0,2\pi). Then E[K]=2−n,E[K2]=(38)n,Var[K]=(38)n−4−n.\mathbb E[K]=2^{-n},\qquad\mathbb E[K^2]=\Big(\frac38\Big)^n,\qquad\mathrm{Var}[K]=\Big(\frac38\Big)^n-4^{-n}. In particular the kernel is exponentially concentrated with b=8/3b=8/3, and its standard deviation is below (3/8)n/2≈0.612n(3/8)^{n/2}\approx0.612^n.

Proof (7 steps)
  1. Step 1:
    E[cos⁡2xj−xj′2]=12π∫02πcos⁡2δ2 dδ\mathbb E\Big[\cos^2\frac{x_j-x'_j}2\Big]=\frac1{2\pi}\int_0^{2\pi}\cos^2\frac\delta2\,\mathrm d\delta
    cos⁡2δ2=1+cos⁡δ2\cos^2\frac\delta2=\frac{1+\cos\delta}2 is 2π2\pi-periodic; apply the lemma.
  2. Step 2:
    =12π∫02π1+cos⁡δ2 dδ=12π(π+12[sin⁡δ]02π)=12=\frac1{2\pi}\int_0^{2\pi}\frac{1+\cos\delta}{2}\,\mathrm d\delta=\frac1{2\pi}\Big(\pi+\tfrac12\big[\sin\delta\big]_0^{2\pi}\Big)=\frac12
    Half-angle identity; the cosine integrates to zero over a full period.
  3. Step 3:
    cos⁡4δ2=(1+cos⁡δ2)2=14(1+2cos⁡δ+1+cos⁡2δ2)=38+12cos⁡δ+18cos⁡2δ\cos^4\frac\delta2=\Big(\frac{1+\cos\delta}2\Big)^2=\frac14\Big(1+2\cos\delta+\frac{1+\cos2\delta}{2}\Big)=\frac38+\frac12\cos\delta+\frac18\cos2\delta
    Square the half-angle form and use cos⁡2δ=1+cos⁡2δ2\cos^2\delta=\frac{1+\cos2\delta}2 once more.
  4. Step 4:
    E[cos⁡4xj−xj′2]=12π∫02π(38+12cos⁡δ+18cos⁡2δ)dδ=38\mathbb E\Big[\cos^4\frac{x_j-x'_j}2\Big]=\frac1{2\pi}\int_0^{2\pi}\Big(\frac38+\frac12\cos\delta+\frac18\cos2\delta\Big)\mathrm d\delta=\frac38
    The lemma again; ∫02πcos⁡(kδ) dδ=0\int_0^{2\pi}\cos(k\delta)\,\mathrm d\delta=0 for k=1,2k=1,2.
  5. Step 5:
    Δj=xj−xj′ independent across j ⇒ E[∏jf(Δj)]=∏jE[f(Δj)]\Delta_j=x_j-x'_j\ \text{independent across }j\ \Rightarrow\ \mathbb E\Big[\prod_jf(\Delta_j)\Big]=\prod_j\mathbb E\big[f(\Delta_j)\big]
    The pairs (xj,xj′)(x_j,x'_j) are independent for different jj, hence so are functions of them, and the expectation of a product of independent bounded variables is the product of the expectations.
  6. Step 6:
    E[K]=∏j=0n−112=2−n,E[K2]=∏j=0n−1E[cos⁡4Δj2]=(38)n\mathbb E[K]=\prod_{j=0}^{n-1}\frac12=2^{-n},\qquad\mathbb E[K^2]=\prod_{j=0}^{n-1}\mathbb E\Big[\cos^4\frac{\Delta_j}2\Big]=\Big(\frac38\Big)^n
    Apply the factorisation to f=cos⁡2(⋅/2)f=\cos^2(\cdot/2) and to f=cos⁡4(⋅/2)f=\cos^4(\cdot/2), using K2=∏jcos⁡4Δj2K^2=\prod_j\cos^4\frac{\Delta_j}2.
  7. Step 7:
    Var[K]=E[K2]−E[K]2=(38)n−(14)n≤(38)n=(83)−n\mathrm{Var}[K]=\mathbb E[K^2]-\mathbb E[K]^2=\Big(\frac38\Big)^n-\Big(\frac14\Big)^n\le\Big(\frac38\Big)^n=\Big(\frac83\Big)^{-n}
    Definition of the variance; the bound gives the concentration rate b=8/3b=8/3 of the definition.

∎

Corollary

Tail bounds and the typical kernel value

Under the assumptions of the theorem, for every t>0t>0: P(K≥t)≤2−ntP(K\ge t)\le\frac{2^{-n}}{t} and P(∣K−2−n∣≥t)≤(3/8)n−4−nt2P\big(\lvert K-2^{-n}\rvert\ge t\big)\le\frac{(3/8)^n-4^{-n}}{t^2}. Moreover 1nln⁡K→−2ln⁡2\frac1n\ln K\to-2\ln2 almost surely, i.e. a typical off-diagonal entry is K=4−n(1+o(1))K=4^{-n(1+o(1))}, even smaller than the mean 2−n2^{-n}.

Proof (6 steps)
  1. Step 1:
    E[K]≥E[K 1K≥t]≥t P(K≥t) ⇒ P(K≥t)≤E[K]t=2−nt\mathbb E[K]\ge\mathbb E\big[K\,\mathbf 1_{K\ge t}\big]\ge t\,P(K\ge t)\ \Rightarrow\ P(K\ge t)\le\frac{\mathbb E[K]}{t}=\frac{2^{-n}}t
    Markov's inequality for the nonnegative variable KK.
  2. Step 2:
    P(∣K−μ∣≥t)=P((K−μ)2≥t2)≤E[(K−μ)2]t2=(3/8)n−4−nt2P\big(\lvert K-\mu\rvert\ge t\big)=P\big((K-\mu)^2\ge t^2\big)\le\frac{\mathbb E\big[(K-\mu)^2\big]}{t^2}=\frac{(3/8)^n-4^{-n}}{t^2}
    Chebyshev's inequality: Markov applied to (K−μ)2(K-\mu)^2 with μ=2−n\mu=2^{-n}.
  3. Step 3:
    n=20, t=0.01:P(K≥0.01)≤2−200.01≈9.5×10−5,P(∣K−2−20∣≥0.01)≤3.0×10−5n=20,\ t=0.01:\quad P(K\ge0.01)\le\frac{2^{-20}}{0.01}\approx9.5\times10^{-5},\qquad P\big(\lvert K-2^{-20}\rvert\ge0.01\big)\le3.0\times10^{-5}
    With 2020 features, fewer than one pair in ten thousand has a kernel value above 0.010.01: the Gram matrix is numerically the identity matrix.
  4. Step 4:
    I=∫0π/2ln⁡sin⁡u du=∫0π/2ln⁡cos⁡u du,2I=∫0π/2ln⁡(sin⁡2u2)du=−π2ln⁡2+II=\int_0^{\pi/2}\ln\sin u\,\mathrm du=\int_0^{\pi/2}\ln\cos u\,\mathrm du,\qquad2I=\int_0^{\pi/2}\ln\Big(\frac{\sin2u}{2}\Big)\mathrm du=-\frac\pi2\ln2+I
    The substitution u↦π2−uu\mapsto\frac\pi2-u swaps sine and cosine. Adding the two forms and using sin⁡ucos⁡u=12sin⁡2u\sin u\cos u=\frac12\sin2u; the substitution v=2uv=2u and the symmetry of sin⁡\sin about π2\frac\pi2 give ∫0π/2ln⁡sin⁡2u du=12∫0πln⁡sin⁡v dv=I\int_0^{\pi/2}\ln\sin2u\,\mathrm du=\frac12\int_0^\pi\ln\sin v\,\mathrm dv=I. Hence I=−π2ln⁡2I=-\frac\pi2\ln2.
  5. Step 5:
    E[ln⁡cos⁡2Δj2]=12π∫02πln⁡cos⁡2δ2 dδ=2π∫0πln⁡∣cos⁡u∣ du=2π⋅2I=−2ln⁡2\mathbb E\Big[\ln\cos^2\frac{\Delta_j}2\Big]=\frac1{2\pi}\int_0^{2\pi}\ln\cos^2\frac\delta2\,\mathrm d\delta=\frac2\pi\int_0^{\pi}\ln\lvert\cos u\rvert\,\mathrm du=\frac2\pi\cdot2I=-2\ln2
    The lemma, the substitution u=δ/2u=\delta/2, and ∫0πln⁡∣cos⁡u∣ du=2∫0π/2ln⁡cos⁡u du\int_0^\pi\ln\lvert\cos u\rvert\,\mathrm du=2\int_0^{\pi/2}\ln\cos u\,\mathrm du by symmetry about π2\frac\pi2.
  6. Step 6:
    1nln⁡K=1n∑j=0n−1ln⁡cos⁡2Δj2 → a.s.  −2ln⁡2 ⇒ K=e−2nln⁡2 (1+o(1))=4−n(1+o(1))\frac1n\ln K=\frac1n\sum_{j=0}^{n-1}\ln\cos^2\frac{\Delta_j}2\ \xrightarrow{\ \text{a.s.}\ }\ -2\ln2\ \Rightarrow\ K=e^{-2n\ln2\,(1+o(1))}=4^{-n(1+o(1))}
    ln⁡K\ln K is a sum of nn i.i.d. integrable terms, so the strong law of large numbers applies. The mean 2−n2^{-n} is dominated by rare pairs with unusually large values.

∎

The uniform dataset draws 2424 points i.i.d. on [0,2π)6[0,2\pi)^6. With n=6n=6 features the off-diagonal entries cluster near 2−6≈0.0162^{-6}\approx0.016 (most of them far below it), the heatmap is a bright diagonal on a dark background, and the eigenvalues bunch around 11 (roughly between 0.40.4 and 1.81.8 for 2424 points, against a few large eigenvalues and many zeros for the two-dimensional datasets): the Gram matrix approaches the identity IMI_M, and does so faster as nn grows. In the basis-encoding lesson we proved that a kernel with K=IMK=I_M makes kernel ridge regression predict a constant at every unseen input; exponential concentration drives a continuous encoding into the same failure mode. Reduce the number of features to 11 or 22 and the structure returns.

Proposition

A small bandwidth prevents concentration

Suppose ∣xj−xj′∣≤R\lvert x_j-x'_j\rvert\le R for all jj and the scale is s=cRns=\frac{c}{R\sqrt n} with 0<c≤20<c\le2. Then for the product encoding K(x,x′) ≥ 1−s24∑j=0n−1(xj−xj′)2 ≥ 1−c24K(x,x')\ \ge\ 1-\frac{s^2}{4}\sum_{j=0}^{n-1}(x_j-x'_j)^2\ \ge\ 1-\frac{c^2}{4} for every pair of inputs, independently of nn.

Proof (4 steps)
  1. Step 1:
    cos⁡2u=1−sin⁡2u≥1−u2\cos^2u=1-\sin^2u\ge1-u^2
    ∣sin⁡u∣≤∣u∣\lvert\sin u\rvert\le\lvert u\rvert for all real uu.
  2. Step 2:
    aj:=s2(xj−xj′)24≤c2R24R2n=c24n≤1a_j:=\frac{s^2(x_j-x'_j)^2}{4}\le\frac{c^2R^2}{4R^2n}=\frac{c^2}{4n}\le1
    The assumptions on RR, ss and c≤2c\le2.
  3. Step 3:
    ∏j=0n−1(1−aj)≥1−∑j=0n−1aj(aj∈[0,1])\prod_{j=0}^{n-1}(1-a_j)\ge1-\sum_{j=0}^{n-1}a_j\qquad(a_j\in[0,1])
    Weierstrass product inequality, by induction: (1−A)(1−a)=1−A−a+Aa≥1−(A+a)(1-A)(1-a)=1-A-a+Aa\ge1-(A+a) whenever A≤1A\le1 and a∈[0,1]a\in[0,1] (if A>1A>1 the right-hand side is negative and the left-hand side is nonnegative).
  4. Step 4:
    K=∏jcos⁡2s(xj−xj′)2≥∏j(1−aj)≥1−∑jaj≥1−n⋅c24n=1−c24K=\prod_j\cos^2\frac{s(x_j-x'_j)}2\ge\prod_j(1-a_j)\ge1-\sum_ja_j\ge1-n\cdot\frac{c^2}{4n}=1-\frac{c^2}4
    Combine the three lines. Choosing the bandwidth s∝1/ns\propto1/\sqrt n keeps every kernel value of order one (Shaydulin and Wild 2022). In the heatmap widget the parameter scale\mathtt{scale} is the range [0,scale][0,\mathtt{scale}] onto which each feature of the two-dimensional datasets is scaled, which plays exactly this role.

∎

Quick check

Ten features with i.i.d. uniform values on [0,2π)[0,2\pi) are encoded with RXR_X rotations, one qubit per feature. What is the expected value E[K(x,x′)]\mathbb E[K(x,x')] of the fidelity kernel for two independent inputs?

tolerance ±0.000001

Projected quantum kernels#

Definition

Projected quantum kernel

For a quantum feature map on nn qubits let ρj(x)=Tr{0,…,n−1}∖{j}ρ(x)\rho_j(x)=\mathrm{Tr}_{\{0,\dots,n-1\}\setminus\{j\}}\rho(x) be the reduced density matrix of qubit jj (a 2×22\times2 density matrix, mixed when qubit jj is entangled with the others). For γ>0\gamma>0 the projected quantum kernel of Huang et al. (2021) is kPQ(x,x′)=exp⁡(−γ∑j=0n−1∥ρj(x)−ρj(x′)∥F2),∥A∥F2=Tr(A†A).k^{PQ}(x,x')=\exp\Big(-\gamma\sum_{j=0}^{n-1}\big\lVert\rho_j(x)-\rho_j(x')\big\rVert_F^2\Big),\qquad\lVert A\rVert_F^2=\mathrm{Tr}(A^\dagger A). Instead of comparing the full 2n2^n-dimensional states, it compares their one-qubit marginals and turns the summed distance into a similarity with a Gaussian of rate γ\gamma.

Lemma

Frobenius distance of qubit states in Bloch coordinates

For one-qubit density matrices ρ=12(I+r⃗⋅σ⃗)\rho=\frac12(I+\vec r\cdot\vec\sigma) and ρ′=12(I+r⃗ ′⋅σ⃗)\rho'=\frac12(I+\vec r\,'\cdot\vec\sigma) with Bloch vectors r⃗,r⃗ ′∈R3\vec r,\vec r\,'\in\mathbb R^3, ∣r⃗∣,∣r⃗ ′∣≤1\lvert\vec r\rvert,\lvert\vec r\,'\rvert\le1: ∥ρ−ρ′∥F2=12 ∣r⃗−r⃗ ′∣2,Tr(ρρ′)=12(1+r⃗⋅r⃗ ′).\lVert\rho-\rho'\rVert_F^2=\tfrac12\,\lvert\vec r-\vec r\,'\rvert^2,\qquad\mathrm{Tr}(\rho\rho')=\tfrac12\big(1+\vec r\cdot\vec r\,'\big).

Proof (6 steps)
  1. Step 1:
    ρ−ρ′=12(r⃗−r⃗ ′)⋅σ⃗=12∑a=13Δra σa,Δr⃗=r⃗−r⃗ ′\rho-\rho'=\tfrac12\big(\vec r-\vec r\,'\big)\cdot\vec\sigma=\tfrac12\sum_{a=1}^3\Delta r_a\,\sigma_a,\qquad\Delta\vec r=\vec r-\vec r\,'
    The identity parts cancel.
  2. Step 2:
    ∥ρ−ρ′∥F2=Tr((ρ−ρ′)†(ρ−ρ′))=Tr((ρ−ρ′)2)=14∑a,bΔraΔrb Tr(σaσb)\lVert\rho-\rho'\rVert_F^2=\mathrm{Tr}\big((\rho-\rho')^\dagger(\rho-\rho')\big)=\mathrm{Tr}\big((\rho-\rho')^2\big)=\tfrac14\sum_{a,b}\Delta r_a\Delta r_b\,\mathrm{Tr}(\sigma_a\sigma_b)
    ρ−ρ′\rho-\rho' is Hermitian; expand the square bilinearly and use linearity of the trace.
  3. Step 3:
    Tr(σaσb)=2δab\mathrm{Tr}(\sigma_a\sigma_b)=2\delta_{ab}
    σa2=I\sigma_a^2=I has trace 22; for a≠ba\ne b, σaσb=iεabcσc\sigma_a\sigma_b=i\varepsilon_{abc}\sigma_c is traceless.
  4. Step 4:
    ∥ρ−ρ′∥F2=14⋅2∑aΔra2=12∣Δr⃗∣2\lVert\rho-\rho'\rVert_F^2=\tfrac14\cdot2\sum_a\Delta r_a^2=\tfrac12\lvert\Delta\vec r\rvert^2
    Only the diagonal terms a=ba=b survive.
  5. Step 5:
    Tr(ρρ′)=14Tr(I+r⃗⋅σ⃗+r⃗ ′⋅σ⃗+(r⃗⋅σ⃗)(r⃗ ′⋅σ⃗))=14(2+0+0+2 r⃗⋅r⃗ ′)=12(1+r⃗⋅r⃗ ′)\mathrm{Tr}(\rho\rho')=\tfrac14\mathrm{Tr}\big(I+\vec r\cdot\vec\sigma+\vec r\,'\cdot\vec\sigma+(\vec r\cdot\vec\sigma)(\vec r\,'\cdot\vec\sigma)\big)=\tfrac14\big(2+0+0+2\,\vec r\cdot\vec r\,'\big)=\tfrac12\big(1+\vec r\cdot\vec r\,'\big)
    Expand the product; the Pauli matrices are traceless and Tr((r⃗⋅σ⃗)(r⃗ ′⋅σ⃗))=∑abrarb′ 2δab\mathrm{Tr}\big((\vec r\cdot\vec\sigma)(\vec r\,'\cdot\vec\sigma)\big)=\sum_{ab}r_ar'_b\,2\delta_{ab}.
  6. Step 6:
    ∣r⃗∣=∣r⃗ ′∣=1:∥ρ−ρ′∥F2=1−r⃗⋅r⃗ ′=2(1−Tr(ρρ′))\lvert\vec r\rvert=\lvert\vec r\,'\rvert=1:\quad\lVert\rho-\rho'\rVert_F^2=1-\vec r\cdot\vec r\,'=2\big(1-\mathrm{Tr}(\rho\rho')\big)
    For pure qubit states, 12∣Δr⃗∣2=12(2−2r⃗⋅r⃗ ′)\tfrac12\lvert\Delta\vec r\rvert^2=\tfrac12(2-2\vec r\cdot\vec r\,'); the Frobenius distance and the one-qubit fidelity kernel carry the same information.

∎

Lemma

Gaussian kernels on feature vectors are positive definite

For γ>0\gamma>0, g(u,v)=exp⁡(−γ∥u−v∥2)g(u,v)=\exp\big(-\gamma\lVert u-v\rVert^2\big) is a positive-definite kernel on Rm\mathbb R^m, and for any map ψ:X→Rm\psi:\mathcal X\to\mathbb R^m the kernel g(ψ(x),ψ(x′))g\big(\psi(x),\psi(x')\big) is positive definite on X\mathcal X.

Proof (6 steps)
  1. Step 1:
    ∥u−v∥2=∥u∥2−2u⊤v+∥v∥2 ⇒ g(u,v)=e−γ∥u∥2 e2γu⊤v e−γ∥v∥2\lVert u-v\rVert^2=\lVert u\rVert^2-2u^\top v+\lVert v\rVert^2\ \Rightarrow\ g(u,v)=e^{-\gamma\lVert u\rVert^2}\,e^{2\gamma u^\top v}\,e^{-\gamma\lVert v\rVert^2}
    Expand the squared distance and split the exponential.
  2. Step 2:
    (u⊤v)k is PD for every k∈N0(u^\top v)^k\ \text{is PD for every }k\in\mathbb N_0
    u⊤vu^\top v is the linear kernel with feature ϕ(u)=u\phi(u)=u; the product rule of the RKHS lesson (Schur product theorem) applied k−1k-1 times; for k=0k=0 the constant 11 has feature ϕ(u)=1\phi(u)=1.
  3. Step 3:
    eL(u,v)=∑k=0L(2γ)kk!(u⊤v)k is PDe_L(u,v)=\sum_{k=0}^{L}\frac{(2\gamma)^k}{k!}(u^\top v)^k\ \text{is PD}
    A sum of positive-definite kernels with nonnegative coefficients (sum and scaling rules).
  4. Step 4:
    ∑i,jcicj e2γui⊤uj=lim⁡L→∞∑i,jcicj eL(ui,uj) ≥ 0\sum_{i,j}c_ic_j\,e^{2\gamma u_i^\top u_j}=\lim_{L\to\infty}\sum_{i,j}c_ic_j\,e_L(u_i,u_j)\ \ge\ 0
    For finitely many points the exponential series converges for every pair, so the quadratic forms converge; a limit of nonnegative numbers is nonnegative. Hence e2γu⊤ve^{2\gamma u^\top v} is positive definite.
  5. Step 5:
    g(u,v)=h(u) e2γu⊤v h(v),h(u)=e−γ∥u∥2g(u,v)=h(u)\,e^{2\gamma u^\top v}\,h(v),\qquad h(u)=e^{-\gamma\lVert u\rVert^2}
    The rule h(x)k(x,x′)h(x′)h(x)k(x,x')h(x') of the RKHS lesson: absorb h(ui)h(u_i) into the coefficients cic_i.
  6. Step 6:
    [g(ψ(xi),ψ(xj))]ij=[g(ui,uj)]ij,ui=ψ(xi)\big[g\big(\psi(x_i),\psi(x_j)\big)\big]_{ij}=\big[g(u_i,u_j)\big]_{ij},\quad u_i=\psi(x_i)
    The Gram matrix of the composed kernel on x1,…,xMx_1,\dots,x_M is the Gram matrix of gg on the points ψ(x1),…,ψ(xM)\psi(x_1),\dots,\psi(x_M), which is positive semidefinite (also when some ψ(xi)\psi(x_i) coincide).

∎

Theorem

The projected quantum kernel is positive definite

For every quantum feature map and every γ>0\gamma>0, kPQk^{PQ} is a positive-definite kernel with kPQ(x,x)=1k^{PQ}(x,x)=1 and 0<kPQ(x,x′)≤10<k^{PQ}(x,x')\le1. With the Bloch vectors r⃗j(x)\vec r_j(x) of the reduced states, kPQ(x,x′)=∏j=0n−1exp⁡(−γ2∣r⃗j(x)−r⃗j(x′)∣2),k^{PQ}(x,x')=\prod_{j=0}^{n-1}\exp\Big(-\frac\gamma2\big\lvert\vec r_j(x)-\vec r_j(x')\big\rvert^2\Big), a Schur product of nn Gaussian kernels on the reduced-state vectors.

Proof (5 steps)
  1. Step 1:
    ∥ρj(x)−ρj(x′)∥F2=12∣r⃗j(x)−r⃗j(x′)∣2\big\lVert\rho_j(x)-\rho_j(x')\big\rVert_F^2=\tfrac12\big\lvert\vec r_j(x)-\vec r_j(x')\big\rvert^2
    The Bloch lemma applied to the reduced state of each qubit (a valid, possibly mixed, one-qubit density matrix).
  2. Step 2:
    kPQ(x,x′)=exp⁡(−γ2∑j∣Δr⃗j∣2)=∏j=0n−1gj(x,x′),gj(x,x′)=exp⁡(−γ2∣r⃗j(x)−r⃗j(x′)∣2)k^{PQ}(x,x')=\exp\Big(-\frac\gamma2\sum_j\lvert\Delta\vec r_j\rvert^2\Big)=\prod_{j=0}^{n-1}g_j(x,x'),\qquad g_j(x,x')=\exp\Big(-\frac\gamma2\lvert\vec r_j(x)-\vec r_j(x')\rvert^2\Big)
    The exponential of a sum is the product of the exponentials.
  3. Step 3:
    gj=g(ψj(x),ψj(x′)),ψj=r⃗j:X→R3,g(u,v)=e−γ2∥u−v∥2 ⇒ gj PDg_j=g\big(\psi_j(x),\psi_j(x')\big),\quad\psi_j=\vec r_j:\mathcal X\to\mathbb R^3,\quad g(u,v)=e^{-\frac\gamma2\lVert u-v\rVert^2}\ \Rightarrow\ g_j\ \text{PD}
    Each factor is a Gaussian kernel with rate γ/2\gamma/2 composed with the map x↦r⃗j(x)x\mapsto\vec r_j(x); apply the Gaussian lemma.
  4. Step 4:
    k1,k2 PD⇒k1k2 PD ⇒ ∏j=0n−1gj PDk_1,k_2\ \text{PD}\Rightarrow k_1k_2\ \text{PD}\ \Rightarrow\ \prod_{j=0}^{n-1}g_j\ \text{PD}
    The Schur product theorem (closure under pointwise products, RKHS lesson), by induction on the number of factors.
  5. Step 5:
    kPQ(x,x)=e0=1,∑j∥⋅∥F2∈[0,∞) ⇒ 0<kPQ≤1k^{PQ}(x,x)=e^{0}=1,\qquad\sum_j\lVert\cdot\rVert_F^2\in[0,\infty)\ \Rightarrow\ 0<k^{PQ}\le1
    The exponent is minus a finite nonnegative number. Equivalently, kPQk^{PQ} is one Gaussian kernel of the concatenated vector (r⃗0(x),…,r⃗n−1(x))∈R3n\big(\vec r_0(x),\dots,\vec r_{n-1}(x)\big)\in\mathbb R^{3n}.

∎

Derivation

Projected kernel of the R_X product encoding and its scale

  1. Step 1:
    ρ(x)=⨂kρ(k)(xk) ⇒ ρj(x)=(∏k≠jTr ρ(k)(xk))ρ(j)(xj)=ρ(j)(xj)\rho(x)=\bigotimes_k\rho^{(k)}(x_k)\ \Rightarrow\ \rho_j(x)=\Big(\prod_{k\ne j}\mathrm{Tr}\,\rho^{(k)}(x_k)\Big)\rho^{(j)}(x_j)=\rho^{(j)}(x_j)
    The partial trace of a product operator traces each discarded factor; every factor has trace 11. So ρj\rho_j depends on xjx_j only.
  2. Step 2:
    ∣r⃗j(x)−r⃗j(x′)∣2=(sin⁡xj−sin⁡xj′)2+(cos⁡xj−cos⁡xj′)2=2−2cos⁡(xj−xj′)\lvert\vec r_j(x)-\vec r_j(x')\rvert^2=(\sin x_j-\sin x'_j)^2+(\cos x_j-\cos x'_j)^2=2-2\cos(x_j-x'_j)
    r⃗j(x)=(0,−sin⁡xj,cos⁡xj)\vec r_j(x)=(0,-\sin x_j,\cos x_j) from the Bloch cross-check; expand and use the addition theorem.
  3. Step 3:
    ∥ρj(x)−ρj(x′)∥F2=1−cos⁡Δj=2sin⁡2Δj2,kPQ(x,x′)=exp⁡(−γ∑j=0n−1(1−cos⁡Δj))\big\lVert\rho_j(x)-\rho_j(x')\big\rVert_F^2=1-\cos\Delta_j=2\sin^2\frac{\Delta_j}2,\qquad k^{PQ}(x,x')=\exp\Big(-\gamma\sum_{j=0}^{n-1}\big(1-\cos\Delta_j\big)\Big)
    The Bloch lemma. Compare K(x,x′)=∏j1+cos⁡Δj2K(x,x')=\prod_j\frac{1+\cos\Delta_j}2: a product of nn factors with mean 12\frac12 against the exponential of a sum whose rate γ\gamma is a free parameter.
  4. Step 4:
    E[e−γ(1−cos⁡Δj)]=e−γ 12π∫02πeγcos⁡δ dδ=e−γI0(γ)\mathbb E\big[e^{-\gamma(1-\cos\Delta_j)}\big]=e^{-\gamma}\,\frac1{2\pi}\int_0^{2\pi}e^{\gamma\cos\delta}\,\mathrm d\delta=e^{-\gamma}I_0(\gamma)
    The uniform-difference lemma for uniform data; I0I_0 is the modified Bessel function of order zero, defined here by this integral.
  5. Step 5:
    I0(γ)=∑k≥0γkk! 12π∫02πcos⁡kδ dδ=∑m≥0γ2m(2m)! 14m(2mm)=∑m≥0(γ/2)2m(m!)2I_0(\gamma)=\sum_{k\ge0}\frac{\gamma^k}{k!}\,\frac1{2\pi}\int_0^{2\pi}\cos^k\delta\,\mathrm d\delta=\sum_{m\ge0}\frac{\gamma^{2m}}{(2m)!}\,\frac{1}{4^m}\binom{2m}{m}=\sum_{m\ge0}\frac{(\gamma/2)^{2m}}{(m!)^2}
    The exponential series converges uniformly on [0,2π][0,2\pi], so it can be integrated term by term. With cos⁡δ=eiδ+e−iδ2\cos\delta=\frac{e^{i\delta}+e^{-i\delta}}2, cos⁡kδ=2−k∑l(kl)ei(2l−k)δ\cos^k\delta=2^{-k}\sum_l\binom kle^{i(2l-k)\delta}, and only a term with 2l=k2l=k survives the integration: odd powers integrate to 00, and the 2m2m-th power to (2mm)4−m\binom{2m}m4^{-m}.
  6. Step 6:
    E[kPQ]=(e−γI0(γ))n,1≤I0(γ)≤∑m(γ2/4)mm!=eγ2/4\mathbb E\big[k^{PQ}\big]=\big(e^{-\gamma}I_0(\gamma)\big)^n,\qquad1\le I_0(\gamma)\le\sum_m\frac{(\gamma^2/4)^m}{m!}=e^{\gamma^2/4}
    Independence across qubits, as in the concentration theorem. The bounds hold termwise, since (m!)2≥m!(m!)^2\ge m! and the m=0m=0 term is 11.
  7. Step 7:
    γ=γ0n:e−γ0 ≤ E[kPQ] ≤ e−γ0+γ02/(4n)\gamma=\frac{\gamma_0}n:\qquad e^{-\gamma_0}\ \le\ \mathbb E\big[k^{PQ}\big]\ \le\ e^{-\gamma_0+\gamma_0^2/(4n)}
    Raise the bounds e−γ≤e−γI0(γ)≤e−γ+γ2/4e^{-\gamma}\le e^{-\gamma}I_0(\gamma)\le e^{-\gamma+\gamma^2/4} to the power nn. With a rate proportional to 1/n1/n the mean kernel value stays of order one for every nn, instead of decaying like 2−n2^{-n}.
  8. Step 8:
    Var[γ∑j(1−cos⁡Δj)]=γ2 n E[cos⁡2Δ]=γ2n2=γ022n\mathrm{Var}\Big[\gamma\sum_j(1-\cos\Delta_j)\Big]=\gamma^2\,n\,\mathbb E\big[\cos^2\Delta\big]=\frac{\gamma^2n}2=\frac{\gamma_0^2}{2n}
    Independent terms; E[cos⁡Δ]=0\mathbb E[\cos\Delta]=0 and E[cos⁡2Δ]=12\mathbb E[\cos^2\Delta]=\frac12 by the lemma. The exponent fluctuates by O(1/n)O(1/\sqrt n) around γ0\gamma_0, so kernel values differ polynomially, not exponentially, and can be resolved with polynomially many shots.

Result

kPQ(x,x′)=e−γ∑j(1−cos⁡Δj),E[kPQ]=(e−γI0(γ))n∈[e−γ0, e−γ0+γ02/(4n)] for γ=γ0n\boxed{k^{PQ}(x,x')=e^{-\gamma\sum_j(1-\cos\Delta_j)},\qquad\mathbb E\big[k^{PQ}\big]=\big(e^{-\gamma}I_0(\gamma)\big)^n\in\big[e^{-\gamma_0},\,e^{-\gamma_0+\gamma_0^2/(4n)}\big]\ \text{for}\ \gamma=\tfrac{\gamma_0}n}

Why the projection helps, and what it costs. The fidelity kernel compares two vectors in a 2n2^n-dimensional space, and two generic vectors in high dimension are nearly orthogonal; for product encodings this appears as a product of nn factors with average 12\frac12. The projected kernel only compares one-qubit marginals, aggregates the nn local distances by a sum, and maps the sum through e−γ(⋅)e^{-\gamma(\cdot)} with a rate that can be matched to nn. It also changes the measurement budget: ρj(x)\rho_j(x) is fixed by its Bloch vector (⟨Xj⟩,⟨Yj⟩,⟨Zj⟩)\big(\langle X_j\rangle,\langle Y_j\rangle,\langle Z_j\rangle\big), and measuring all qubits in the XX, YY and ZZ bases gives every r⃗j(x)\vec r_j(x) at once. Training on MM points therefore needs 3M3M circuit settings instead of M(M−1)/2M(M-1)/2 overlap circuits, and the M2M^2 kernel values are computed classically from the estimated Bloch vectors, each component to precision ε\varepsilon with O(1/ε2)O(1/\varepsilon^2) shots. Two caveats: for product encodings both kernels are classically computable, and the motivation of Huang et al. is entangling encodings whose reduced states are hard to simulate; and the projected kernel concentrates as well when the reduced states approach the maximally mixed state (r⃗j→0\vec r_j\to0), as they do for highly entangling or noisy encodings.

Quick check

What is the squared Frobenius distance ∥ρ−ρ′∥F2\lVert\rho-\rho'\rVert_F^2 between ρ=∣0⟩⟨0∣\rho=\lvert0\rangle\langle0\rvert and ρ′=∣+⟩⟨+∣\rho'=\lvert+\rangle\langle+\rvert?

tolerance ±0.000001

Estimating a kernel matrix with shots#

Theorem

Shot cost of one kernel entry

Run the inversion test NN times and let N0N_0 count the outcomes 0n0^n; set K^=N0/N\hat K=N_0/N. Then (a) E[K^]=K\mathbb E[\hat K]=K and Var[K^]=K(1−K)N≤14N\mathrm{Var}[\hat K]=\frac{K(1-K)}N\le\frac1{4N}; (b) P(∣K^−K∣≥ε)≤14Nε2P\big(\lvert\hat K-K\rvert\ge\varepsilon\big)\le\frac1{4N\varepsilon^2}, so N≥14δε2N\ge\frac1{4\delta\varepsilon^2} shots give precision ε\varepsilon with probability at least 1−δ1-\delta; (c) by Hoeffding's inequality N≥ln⁡(2/δ)2ε2N\ge\frac{\ln(2/\delta)}{2\varepsilon^2} suffices; (d) for the SWAP-test estimator K^S=2N0/N−1\hat K_S=2N_0/N-1, Var[K^S]=1−K2N\mathrm{Var}[\hat K_S]=\frac{1-K^2}N and N≥2ln⁡(2/δ)ε2N\ge\frac{2\ln(2/\delta)}{\varepsilon^2} suffices. In all cases N=O(ε−2log⁡(1/δ))N=O\big(\varepsilon^{-2}\log(1/\delta)\big).

Proof (7 steps)
  1. Step 1:
    Bs∈{0,1},P(Bs=1)=K,K^=1N∑s=1NBsB_s\in\{0,1\},\quad P(B_s=1)=K,\quad\hat K=\frac1N\sum_{s=1}^NB_s
    Each shot prepares a fresh state, so the indicators BsB_s of the outcome 0n0^n are independent Bernoulli variables with success probability KK (inversion-test derivation).
  2. Step 2:
    E[K^]=1N∑sE[Bs]=K,Var[K^]=1N2∑sVar[Bs]=K(1−K)N\mathbb E[\hat K]=\frac1N\sum_s\mathbb E[B_s]=K,\qquad\mathrm{Var}[\hat K]=\frac1{N^2}\sum_s\mathrm{Var}[B_s]=\frac{K(1-K)}N
    Linearity of expectation; variances of independent variables add; Var[Bs]=K−K2\mathrm{Var}[B_s]=K-K^2.
  3. Step 3:
    K(1−K)=14−(K−12)2≤14K(1-K)=\tfrac14-\big(K-\tfrac12\big)^2\le\tfrac14
    Complete the square: the Bernoulli variance is largest at K=12K=\frac12.
  4. Step 4:
    P(∣K^−K∣≥ε)≤Var[K^]ε2≤14Nε2≤δ  ⟺  N≥14δε2P\big(\lvert\hat K-K\rvert\ge\varepsilon\big)\le\frac{\mathrm{Var}[\hat K]}{\varepsilon^2}\le\frac1{4N\varepsilon^2}\le\delta\iff N\ge\frac1{4\delta\varepsilon^2}
    Chebyshev's inequality and the worst-case variance.
  5. Step 5:
    P(∣K^−K∣≥ε)≤2e−2Nε2≤δ  ⟺  N≥ln⁡(2/δ)2ε2P\big(\lvert\hat K-K\rvert\ge\varepsilon\big)\le2e^{-2N\varepsilon^2}\le\delta\iff N\ge\frac{\ln(2/\delta)}{2\varepsilon^2}
    Hoeffding's inequality (1963) for the mean of NN independent variables with values in [0,1][0,1]; it improves the dependence on the confidence from 1/δ1/\delta to ln⁡(1/δ)\ln(1/\delta).
  6. Step 6:
    P(0)=1+K2,K^S=2P^0−1,Var[K^S]=4 P(0)(1−P(0))N=4⋅(1+K)(1−K)4N=1−K2NP(0)=\frac{1+K}2,\quad\hat K_S=2\hat P_0-1,\quad\mathrm{Var}[\hat K_S]=4\,\frac{P(0)\big(1-P(0)\big)}N=4\cdot\frac{(1+K)(1-K)}{4N}=\frac{1-K^2}N
    The SWAP-test outcome 00 is Bernoulli with P(0)=1+K2P(0)=\frac{1+K}2; the affine map p↦2p−1p\mapsto2p-1 multiplies the variance by 44.
  7. Step 7:
    ∣K^S−K∣≥ε  ⟺  ∣P^0−P(0)∣≥ε2 ⇒ P≤2e−Nε2/2≤δ  ⟺  N≥2ln⁡(2/δ)ε2\lvert\hat K_S-K\rvert\ge\varepsilon\iff\lvert\hat P_0-P(0)\rvert\ge\tfrac\varepsilon2\ \Rightarrow\ P\le2e^{-N\varepsilon^2/2}\le\delta\iff N\ge\frac{2\ln(2/\delta)}{\varepsilon^2}
    Hoeffding with precision ε/2\varepsilon/2 on P^0\hat P_0: the SWAP test needs four times as many shots as the inversion test for the same guarantee, in exchange for not needing U†U^\dagger.

∎

Proposition

Cost of a whole Gram matrix

For MM training points with pure encoded states, the Gram matrix requires L=M(M−1)2L=\frac{M(M-1)}2 distinct circuits. With N=⌈ln⁡(2L/δ)2ε2⌉N=\big\lceil\frac{\ln(2L/\delta)}{2\varepsilon^2}\big\rceil inversion-test shots per entry, all entries are within ε\varepsilon simultaneously with probability at least 1−δ1-\delta, for a total of L⋅N=O(M2ε−2log⁡(M/δ))L\cdot N=O\big(M^2\varepsilon^{-2}\log(M/\delta)\big) shots. Predictions on MtM_t test points need MtMM_tM further entries.

Proof (6 steps)
  1. Step 1:
    Kii=Tr ρ(xi)2=1,Kij=KjiK_{ii}=\mathrm{Tr}\,\rho(x_i)^2=1,\qquad K_{ij}=K_{ji}
    Pure states have purity 11, and the kernel is symmetric, so only the entries above the diagonal must be estimated.
  2. Step 2:
    L=#{(i,j):1≤i<j≤M}=(M2)=M(M−1)2L=\#\{(i,j):1\le i<j\le M\}=\binom M2=\frac{M(M-1)}2
    Number of unordered pairs of distinct indices.
  3. Step 3:
    P(⋃(i,j){∣K^ij−Kij∣≥ε})≤∑(i,j)P(∣K^ij−Kij∣≥ε)≤L⋅δL=δP\Big(\bigcup_{(i,j)}\big\{\lvert\hat K_{ij}-K_{ij}\rvert\ge\varepsilon\big\}\Big)\le\sum_{(i,j)}P\big(\lvert\hat K_{ij}-K_{ij}\rvert\ge\varepsilon\big)\le L\cdot\frac\delta L=\delta
    Union bound, with each entry estimated at confidence δ/L\delta/L.
  4. Step 4:
    N=⌈ln⁡(2L/δ)2ε2⌉,ln⁡2Lδ≤ln⁡M2δ=2ln⁡M+ln⁡1δN=\Big\lceil\frac{\ln(2L/\delta)}{2\varepsilon^2}\Big\rceil,\qquad\ln\frac{2L}\delta\le\ln\frac{M^2}\delta=2\ln M+\ln\frac1\delta
    Hoeffding's bound of the previous theorem at confidence δ/L\delta/L, with 2L=M(M−1)≤M22L=M(M-1)\le M^2.
  5. Step 5:
    L⋅N=O(M2ε2log⁡Mδ)L\cdot N=O\Big(\frac{M^2}{\varepsilon^2}\log\frac M\delta\Big)
    Multiply the number of circuits by the shots per circuit.
  6. Step 6:
    M=100, ε=0.01, δ=0.05:L=4950,N=⌈ln⁡1980002⋅10−4⌉=60981,LN≈3.0×108M=100,\ \varepsilon=0.01,\ \delta=0.05:\quad L=4950,\quad N=\Big\lceil\frac{\ln198000}{2\cdot10^{-4}}\Big\rceil=60981,\quad LN\approx3.0\times10^8
    A modest dataset already needs hundreds of millions of shots, which at typical rates of a few thousand shots per second is a day of machine time. The test kernel K(xa∗,xi)K(x^\ast_a,x_i) has neither symmetry nor a known diagonal, hence MtMM_tM entries.

∎

Corollary

Concentrated kernels need exponentially many shots

If a kernel entry has size K≈2−nK\approx2^{-n}, then (a) a relative precision Var[K^]≤εrK\sqrt{\mathrm{Var}[\hat K]}\le\varepsilon_rK requires N≥1−Kεr2K=2n−1εr2N\ge\frac{1-K}{\varepsilon_r^2K}=\frac{2^n-1}{\varepsilon_r^2} shots; (b) P(K^=0)=(1−K)N≥1−NKP(\hat K=0)=(1-K)^N\ge1-NK, so for the concentrated product-encoding kernel with a shot budget N≪2nN\ll2^n almost every estimated off-diagonal entry is exactly 00, the estimated Gram and test matrices are the identity and zero, and the trained model predicts the same constant at every new input.

Proof (6 steps)
  1. Step 1:
    K(1−K)N≤εrK  ⟺  N≥1−Kεr2K\sqrt{\frac{K(1-K)}N}\le\varepsilon_rK\iff N\ge\frac{1-K}{\varepsilon_r^2K}
    Square both sides of the relative-precision requirement and divide by K2K^2.
  2. Step 2:
    K=2−n:1−2−nεr22−n=2n−1εr2K=2^{-n}:\quad\frac{1-2^{-n}}{\varepsilon_r^22^{-n}}=\frac{2^n-1}{\varepsilon_r^2}
    Multiply numerator and denominator by 2n2^n: exponentially many shots per entry.
  3. Step 3:
    P(K^=0)=P(B1=⋯=BN=0)=(1−K)NP(\hat K=0)=P(B_1=\cdots=B_N=0)=(1-K)^N
    All NN independent shots must miss the outcome 0n0^n.
  4. Step 4:
    (1−K)N≥1−NK(0≤K≤1, N∈N)(1-K)^N\ge1-NK\qquad(0\le K\le1,\ N\in\mathbb N)
    Bernoulli's inequality, by induction: (1−K)N+1≥(1−NK)(1−K)=1−(N+1)K+NK2≥1−(N+1)K(1-K)^{N+1}\ge(1-NK)(1-K)=1-(N+1)K+NK^2\ge1-(N+1)K.
  5. Step 5:
    Ex,x′[(1−K)N]≥1−N E[K]=1−N2−n\mathbb E_{x,x'}\big[(1-K)^N\big]\ge1-N\,\mathbb E[K]=1-N2^{-n}
    Average the pointwise inequality over random pairs and use the concentration theorem. For example n=30n=30 and N=n3=27000N=n^3=27000 shots give a fraction ≥1−2.5×10−5\ge1-2.5\times10^{-5} of zero entries.
  6. Step 6:
    K^train=IM,  K^test=0 ⇒ f(x∗)=∑iαi⋅0+b=b  for every x∗\hat K_{\text{train}}=I_M,\ \ \hat K_{\text{test}}=0\ \Rightarrow\ f(x^\ast)=\sum_i\alpha_i\cdot0+b=b\ \ \text{for every }x^\ast
    The basis-encoding lesson: with an identity Gram matrix, kernel ridge regression with bias predicts b=yˉb=\bar y for every unseen input, independently of the data's structure.

∎

Quick check

How many distinct kernel circuits must be run to estimate the training Gram matrix of M=100M=100 data points with pure encoded states?

tolerance ±0.5

Quick check

How many inversion-test shots per entry guarantee a standard deviation Var[K^]≤0.01\sqrt{\mathrm{Var}[\hat K]}\le0.01 for every possible kernel value K∈[0,1]K\in[0,1]?

tolerance ±0.5

The TypeScript cell below checks the main results with the platform's simulator and QML library: the lab value from the simulated states against the closed form, the positive semidefiniteness of a ZZ-feature-map Gram matrix, the concentration of the product-encoding kernel (Monte Carlo means over 20002000 random pairs against 2−n2^{-n}, with the predicted standard deviation (3/8)n−4−n\sqrt{(3/8)^n-4^{-n}}), and the Frobenius–Bloch identity behind the projected kernel.

TypeScriptrunnable
import { matrix, mulberry32, reducedStateFromPure, runStatevector } from '@/lib/quantum-simulator';
import { angleEncoding, fidelityKernel, isPositiveSemidefinite, kernelMatrix, zzFeatureMap } from '@/lib/qml';

// (1) One kernel entry: R_X product encoding, x = (0.3, 1.2), x' = (1.0, 0.4).
const rx = angleEncoding(2, { rotation: 'RX' });
const x = [0.3, 1.2];
const xp = [1.0, 0.4];
const closed = Math.cos(0.35) ** 2 * Math.cos(0.4) ** 2;
console.log("K(x, x') simulated = " + fidelityKernel(rx, x, xp).toFixed(12) + '   closed form = ' + closed.toFixed(12));

// (2) A Gram matrix of the entangling ZZ feature map: symmetric, unit diagonal, positive semidefinite.
const rng = mulberry32(39);
const X = Array.from({ length: 10 }, () => [0, 1, 2].map(() => 2 * Math.PI * rng()));
const K = kernelMatrix(zzFeatureMap(3, { reps: 2 }), X);
const trace = K.reduce((s, row, i) => s + row[i], 0);
console.log('ZZ Gram matrix 10 x 10: trace = ' + trace + ', PSD = ' + isPositiveSemidefinite(K));

// (3) Exponential concentration of the product-encoding kernel over i.i.d. uniform pairs.
for (let n = 1; n <= 6; n++) {
  const enc = angleEncoding(n, { rotation: 'RX' });
  const S = 2000;
  let sum = 0;
  for (let s = 0; s < S; s++) {
    const a = Array.from({ length: n }, () => 2 * Math.PI * rng());
    const b = Array.from({ length: n }, () => 2 * Math.PI * rng());
    sum += fidelityKernel(enc, a, b);
  }
  const sd = Math.sqrt((3 / 8) ** n - 4 ** -n);
  console.log('n = ' + n + ': mean K = ' + (sum / S).toFixed(4) + '   2^-n = ' + (2 ** -n).toFixed(4) + '   predicted std = ' + sd.toFixed(4));
}

// (4) Projected kernel: ||rho_j(x) - rho_j(x')||_F^2 = |r - r'|^2 / 2 = 1 - cos(x_j - x'_j) for R_X encodings.
const sx = runStatevector(rx(x));
const sxp = runStatevector(rx(xp));
let exponent = 0;
for (let j = 0; j < 2; j++) {
  const diff = matrix.sub(reducedStateFromPure(sx, [j]).toMatrix(), reducedStateFromPure(sxp, [j]).toMatrix());
  const d2 = matrix.frobeniusNorm(diff) ** 2;
  exponent += d2;
  console.log('qubit ' + j + ': squared Frobenius distance = ' + d2.toFixed(12) + '   1 - cos(dx) = ' + (1 - Math.cos(x[j] - xp[j])).toFixed(12));
}
console.log('projected kernel (gamma = 1) = ' + Math.exp(-exponent).toFixed(6) + '   fidelity kernel = ' + closed.toFixed(6));

Expected output

K(x, x') simulated = 0.748604895026   closed form = 0.748604895026
ZZ Gram matrix 10 x 10: trace = 10, PSD = true
n = 1: mean K = 0.5058   2^-n = 0.5000   predicted std = 0.3536
n = 2: mean K = 0.2518   2^-n = 0.2500   predicted std = 0.2795
n = 3: mean K = 0.1252   2^-n = 0.1250   predicted std = 0.1926
n = 4: mean K = 0.0595   2^-n = 0.0625   predicted std = 0.1260
n = 5: mean K = 0.0314   2^-n = 0.0313   predicted std = 0.0802
n = 6: mean K = 0.0168   2^-n = 0.0156   predicted std = 0.0504
qubit 0: squared Frobenius distance = 0.235157812716   1 - cos(dx) = 0.235157812716
qubit 1: squared Frobenius distance = 0.303293290653   1 - cos(dx) = 0.303293290653
projected kernel (gamma = 1) = 0.583652   fidelity kernel = 0.748605

The NumPy cell builds the encoded states as explicit Kronecker products, confirms ∣⟨ϕ∣ϕ′⟩∣2=Tr(ρρ′)=∏jcos⁡2Δj2\lvert\langle\phi\vert\phi'\rangle\rvert^2=\mathrm{Tr}(\rho\rho')=\prod_j\cos^2\frac{\Delta_j}2 and K=V†VK=V^\dagger V, evaluates the moments E[cos⁡2]=12\mathbb E[\cos^2]=\frac12 and E[cos⁡4]=38\mathbb E[\cos^4]=\frac38 exactly on the equispaced grid δk=2πk/N\delta_k=2\pi k/N (the rectangle rule on a periodic grid of NN nodes is exact for trigonometric polynomials of degree below NN, and cos⁡4δ2\cos^4\frac\delta2 has degree 22), tabulates the mean, the variance and the relative-precision shot count 1−Kεr2K\frac{1-K}{\varepsilon_r^2K} with εr=0.1\varepsilon_r=0.1, and checks the Bloch identity on a partial trace.

Pythonrunnable
import numpy as np

def rx(t):
    c, s = np.cos(t / 2), np.sin(t / 2)
    return np.array([[c, -1j * s], [-1j * s, c]])

def phi(x):
    psi = np.array([1.0 + 0j])
    for xj in x:
        psi = np.kron(psi, rx(xj) @ np.array([1.0, 0.0]))
    return psi

# (1) One kernel entry three ways: overlap, Tr(rho rho'), product formula.
x, xp = np.array([0.3, 1.2]), np.array([1.0, 0.4])
a, b = phi(x), phi(xp)
rho, sig = np.outer(a, a.conj()), np.outer(b, b.conj())
print(f"|<phi(x)|phi(x')>|   = {abs(np.vdot(a, b)):.12f}")
print(f"|<phi(x)|phi(x')>|^2 = {abs(np.vdot(a, b)) ** 2:.12f}")
print(f"Tr(rho(x) rho(x'))   = {np.trace(rho @ sig).real:.12f}")
print(f"prod cos^2(dx/2)     = {np.prod(np.cos((x - xp) / 2) ** 2):.12f}")

# (2) The Gram matrix is the Gram matrix of the vectors vec(rho_i), hence PSD.
pts = np.stack([np.linspace(0.0, 6.0, 8), np.linspace(2.5, 0.2, 8)], axis=1)
states = [phi(p) for p in pts]
K = np.array([[abs(np.vdot(u, v)) ** 2 for v in states] for u in states])
V = np.stack([np.outer(u, u.conj()).ravel() for u in states], axis=1)
G = V.conj().T @ V
print("K = V^dagger V:", bool(np.allclose(G, K, atol=1e-12)), "| min eigenvalue >= -1e-10:", bool(np.linalg.eigvalsh(K).min() >= -1e-10))

# (3) Moments over a uniform difference (exact on an equispaced grid): E cos^2 = 1/2, E cos^4 = 3/8.
d = 2 * np.pi * np.arange(4096) / 4096
m2, m4 = round(float(np.mean(np.cos(d / 2) ** 2)), 12), round(float(np.mean(np.cos(d / 2) ** 4)), 12)
print(f"E[cos^2] = {m2:.6f}, E[cos^4] = {m4:.6f}")
for n in (1, 2, 4, 8, 16):
    mean, var = m2 ** n, m4 ** n - m2 ** (2 * n)
    print(f"n = {n:2d}: E[K] = {mean:.3e}, Var[K] = {var:.3e}, shots for 10% relative error ~ {(1 - mean) / (0.01 * mean):.3e}")

# (4) Bloch vectors: ||rho - rho'||_F^2 = |r - r'|^2 / 2 for the reduced state of qubit 0.
paulis = [np.array([[0, 1], [1, 0]]), np.array([[0, -1j], [1j, 0]]), np.array([[1, 0], [0, -1]])]
def bloch(r1):
    return np.array([np.trace(r1 @ p).real for p in paulis])
r0 = rho.reshape(2, 2, 2, 2).trace(axis1=1, axis2=3)
s0 = sig.reshape(2, 2, 2, 2).trace(axis1=1, axis2=3)
print(f"||rho_0 - rho_0'||_F^2 = {np.linalg.norm(r0 - s0) ** 2:.12f}, |r - r'|^2 / 2 = {np.sum((bloch(r0) - bloch(s0)) ** 2) / 2:.12f}")

Expected output

|<phi(x)|phi(x')>|   = 0.865219564634
|<phi(x)|phi(x')>|^2 = 0.748604895026
Tr(rho(x) rho(x'))   = 0.748604895026
prod cos^2(dx/2)     = 0.748604895026
K = V^dagger V: True | min eigenvalue >= -1e-10: True
E[cos^2] = 0.500000, E[cos^4] = 0.375000
n =  1: E[K] = 5.000e-01, Var[K] = 1.250e-01, shots for 10% relative error ~ 1.000e+02
n =  2: E[K] = 2.500e-01, Var[K] = 7.812e-02, shots for 10% relative error ~ 3.000e+02
n =  4: E[K] = 6.250e-02, Var[K] = 1.587e-02, shots for 10% relative error ~ 1.500e+03
n =  8: E[K] = 3.906e-03, Var[K] = 3.758e-04, shots for 10% relative error ~ 2.550e+04
n = 16: E[K] = 1.526e-05, Var[K] = 1.527e-07, shots for 10% relative error ~ 6.554e+06
||rho_0 - rho_0'||_F^2 = 0.235157812716, |r - r'|^2 / 2 = 0.235157812716

References

  1. V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow and J. M. Gambetta, Supervised learning with quantum-enhanced feature spaces, Nature 567, 209–212 (2019).doi:10.1038/s41586-019-0980-2
  2. M. Schuld and N. Killoran, Quantum machine learning in feature Hilbert spaces, Physical Review Letters 122, 040504 (2019).doi:10.1103/PhysRevLett.122.040504
  3. M. Schuld, Supervised quantum machine learning models are kernel methods, arXiv:2101.11020 (2021).arxiv.org
  4. H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven and J. R. McClean, Power of data in quantum machine learning, Nature Communications 12, 2631 (2021).doi:10.1038/s41467-021-22539-9
  5. S. Thanasilp, S. Wang, M. Cerezo and Z. Holmes, Exponential concentration in quantum kernel methods, Nature Communications 15, 5200 (2024).doi:10.1038/s41467-024-49287-w
  6. R. Shaydulin and S. M. Wild, Importance of kernel bandwidth in quantum machine learning, Physical Review A 106, 042407 (2022).doi:10.1103/PhysRevA.106.042407
  7. J. M. Kübler, S. Buchholz and B. Schölkopf, The inductive bias of quantum kernels, Advances in Neural Information Processing Systems 34 (NeurIPS 2021), arXiv:2106.03747.arxiv.org
  8. W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58(301), 13–30 (1963).doi:10.1080/01621459.1963.10500830

Hands-on labs

  • Evaluate a quantum kernel entry

    1 step · auto-graded

    Compute one entry of a quantum kernel matrix by hand: the fidelity kernel K(x,x′)=∣⟨ϕ(x)∣ϕ(x′)⟩∣2K(x,x')=\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2 of the two-qubit RXR_X product encoding at x=(0.3,1.2)x=(0.3,1.2) and x′=(1.0,0.4)x'=(1.0,0.4), using the closed form ∏jcos⁡2xj−xj′2\prod_j\cos^2\frac{x_j-x'_j}{2} derived in the lesson.

    Open lab