Feature Maps and Quantum Kernels

To let a quantum computer touch classical data, we must first turn a data vector $x$ into a quantum state. Three encodings recur. Basis encoding writes a bitstring directly into computational-basis qubits — faithful but wasteful. Amplitude encoding packs $2^n$ real numbers into the amplitudes of $n$ qubits — exponentially compact, but preparing such a state is itself expensive. Angle encoding — the one we use — turns each feature into a rotation angle, $x_i\mapsto R_Z(x_i)$ or $R_Y(x_i)$: cheap, shallow, and hardware-friendly.

Whatever the encoding, the result is a feature map $\phi :x\mapsto |\phi (x)⟩$, a function from data space into the Hilbert space of Chapter 1. The learning happens there.

A feature map is prepared by an encoding circuit acting on the all-zeros state, $|\phi (x)⟩=U_{\phi }(x)|0\cdots 0⟩$. We use the ZZ feature map of Havlíček et al.: a layer of Hadamards puts every qubit in superposition, single-qubit $R_Z(2x_i)$ rotations imprint the data, and a two-qubit entangling block imprints the products $(\pi -x_i)(\pi -x_j)$ — a genuinely nonlinear, entangling map. Repeating the block deepens the map.

With feature states in hand, the kernel is their overlap — a fidelity (Chapter 4) between the two encoded states:

It is 1 when $x^{\prime }=x$ and shrinks as the feature states grow orthogonal. On real hardware you cannot read amplitudes, so you estimate the overlap by the compute–uncompute test: prepare $U_{\phi }(x)|0⟩$, apply $U_{\phi }(x^{\prime }{)}^{†}$, and measure the probability of returning to $|0\cdots 0⟩$, which is exactly $k(x,x^{\prime })$. Move two points and watch the kernel respond:

Equation (15.1) is a valid kernel — symmetric and positive semidefinite — because it is the Hilbert–Schmidt inner product of the projectors $|\phi (x)⟩⟨\phi (x)|$. That guarantee is what lets us drop it straight into a classical kernel machine.

What carries over from Chapter 14 is the kernel trick — a classifier that touches the data only through the $m\times m$ Gram matrix $K_{ij}=k(x_i,x_j)$ — not the solver. Chapter 14 trained kernel logistic regression: a cross-entropy loss with a bias term, minimized by gradient descent on the dual weights. Here we pair the quantum kernel with the simplest kernel machine of all, least-squares kernel ridge (LS-SVM): the same representer form $f(x)={\sum }_i{\alpha }_{i}k(x,x_i)$, but a squared loss, no bias, and a closed-form solution. Minimize the regularized squared error over the dual weights,

set the gradient to zero, and the kernel matrix factors out of the stationarity condition:

which is satisfied by solving the single linear system $(K+\lambda I)\alpha =y$. Because $K$ is positive semidefinite and $\lambda >0$, the matrix $K+\lambda I$ is symmetric positive definite: one Cholesky solve yields $\alpha$, and the prediction is $\hat{y}(x)=\mathrm{sign}{\sum }_i{\alpha }_{i}k(x,x_i)$. The only quantum ingredient is that each $k$ is now an overlap of feature states. The lab does exactly this and reports the accuracy beside a classical radial-basis-function baseline trained by the same solve.

Here is the honest scorecard, and it matters. A quantum feature map gives a kernel that might be classically hard to estimate, and on carefully constructed datasets a provable separation exists. But there is no generic advantage. For most natural data a classical kernel does just as well, and Huang et al. (2021) showed that when the quantum kernel can be estimated well from data, a classical method can often match it. Advantage must be argued case by case — never assumed because the word “quantum” appears. The lab's own result is starker still: on its dataset the quantum kernel outright loses to the classical RBF baseline out of sample — and a referee gates that sentence, failing the lab if it ever stops being true.

The lab builds the ZZ feature map and computes the kernel three independent ways — directly from the statevectors, by the compute–uncompute overlap, and as the density-matrix trace $\mathrm{Tr}[\rho (x)\rho (x^{\prime })]$ from an explicitly built unitary — plus a pen-and-paper closed form at one repetition. All routes must agree to machine precision:

1/// The gate list for U_φ(x) on `n` qubits with `reps` repetitions:
2///   [ H^⊗n , RZ(2 x_i)_i , { CNOT_{ij}, RZ(2(π−x_i)(π−x_j))_j, CNOT_{ij} }_{i<j} ] × reps.
3fn feature_ops(x: &[f64], n: usize, reps: usize) -> Vec<Op> {
4    let mut ops = Vec::new();
5    for _ in 0..reps {
6        for q in 0..n {
7            ops.push(Op::H(q));
8        }
9        for q in 0..n {
10            ops.push(Op::Rz(2.0 * x[q], q));
11        }
12        for i in 0..n {
13            for j in (i + 1)..n {
14                let phi = 2.0 * (PI - x[i]) * (PI - x[j]);
15                ops.push(Op::Cx(i, j));
16                ops.push(Op::Rz(phi, j));
17                ops.push(Op::Cx(i, j));
18            }
19        }
20    }
21    ops
22}

1/// DIRECT path: k = |⟨φ(x_i)|φ(x_j)⟩|² from the two statevectors.
2fn kernel_direct(psi_i: &[C], psi_j: &[C]) -> f64 {
3    let mut overlap = C::new(0.0, 0.0);
4    for k in 0..psi_i.len() {
5        overlap += psi_i[k].conj() * psi_j[k];
6    }
7    overlap.norm_sqr()
8}
9
10/// COMPUTE–UNCOMPUTE path: prepare U_φ(x_i)|0⟩, apply U_φ(x_j)†, read the
11/// probability of the all-zeros outcome. Equals |⟨φ(x_j)|φ(x_i)⟩|² = k(x_i,x_j).
12fn kernel_uncompute(xi: &[f64], xj: &[f64], n: usize, reps: usize) -> f64 {
13    let mut s = feature_state(xi, n, reps);
14    apply_feature_dagger(&mut s, xj, n, reps);
15    s[0].norm_sqr()
16}

10 referees then check that the kernel is a valid Gram matrix (symmetric across independent code paths, positive semidefinite, unit diagonal), that every kernel route agrees with every other to the tolerances listed in the panel, that the feature encoding is unitary, that the simulator reproduces the closed form of §15.3, and that the classifier clears an honest accuracy floor — with the quantum-vs-RBF verdict gated by a referee of its own. Everything below is read live from the lab's JSON:

Run it with cargo run --release in Rust-QML/ch15-qkernel. The feature map is fixed here; the next chapter makes the circuit trainable and confronts what happens when you try to learn its parameters at scale.