Chapter 34: Quantum Kernels

This is the technique in Part VI with the cleanest mathematical story, and it deserves to be presented on its merits before it is costed.

Chapter 33's variational classifier had every problem Part V catalogued: a non-convex landscape, random initialization, a learning rate, barren plateaus, and no guarantee that training finds what the model can represent. The kernel method removes all of them at once.

You use the quantum circuit to compute a similarity function between pairs of data points, hand the resulting matrix to a classical support vector machine, and the SVM's optimization is convex. One optimum, found exactly, in about two milliseconds. No plateaus, no initialization, no learning rate.

That is a genuine structural advantage, and it is not a small one.

Then the costs arrive, and they are different from Chapter 33's but not smaller. And one measurement in this chapter contradicted a claim I had written down before running it — §34.6 keeps both.

34.1 The idea

A feature map $\phi$ sends a data point $x$ into some space where the classes are easier to separate. Classical kernel methods never construct $\phi(x)$ explicitly; they only ever need the inner product between pairs:

$$K(x, x') = \langle \phi(x), \phi(x')\rangle$$

That is the kernel trick, and it is why an RBF kernel can work in an infinite-dimensional space on a laptop.

The quantum version encodes $x$ into a quantum state. The feature map is a circuit $U(x)$ acting on $|0\dots0\rangle$, and the feature space is the Hilbert space of $n$ qubits — which has $2^n$ dimensions. The kernel is the squared overlap:

$$K(x, x') = \big|\langle \phi(x) | \phi(x')\rangle\big|^2 = \big|\langle 0|U^\dagger(x)U(x')|0\rangle\big|^2$$

⚛️ The Physics Underneath: why you can compute this without building the state.

$\big|\langle 0|U^\dagger(x)U(x')|0\rangle\big|^2$ is exactly the probability of measuring $|0\dots0\rangle$ after running $U(x')$ followed by $U^\dagger(x)$.

So the whole kernel is one circuit — feature map, then the adjoint of the feature map on the other point — and one number read off the output distribution. You never construct the $2^n$-dimensional feature vector, exactly as classical kernel methods never construct theirs.

@qml.qnode(dev)
def kernel_circuit(x1, x2):
    feature_map(x1)
    qml.adjoint(feature_map)(x2)
    return qml.probs(wires=range(n_qubits))

kernel = lambda a, b: float(kernel_circuit(a, b)[0])

Sanity checks, measured: $K(x,x) = 1.000000$ exactly, and the matrix is symmetric to machine precision. Both must hold, and both are one line to verify.

Why the SVM only ever needs inner products

The kernel trick is usually asserted. It is worth deriving, because the derivation is what licenses everything else in this chapter — including the convexity in §34.3 and the $n^2$ in §34.7.

A soft-margin support vector machine, stated in the feature space, looks like this:

$$\min_{w,b,\xi} \ \tfrac{1}{2}\|w\|^2 + C\sum_i \xi_i \quad \text{s.t.} \quad y_i\big(\langle w, \phi(x_i)\rangle + b\big) \ge 1 - \xi_i, \ \ \xi_i \ge 0$$

If $\phi(x)$ is a $2^n$-dimensional vector, then $w$ is too, and at ten qubits that is a 1,024-component parameter vector you would have to store and optimize. The dual eliminates it. Introducing multipliers $\alpha_i$ for the margin constraints and eliminating $w$ gives

$$\max_{\alpha} \ \sum_i \alpha_i - \tfrac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \,\langle \phi(x_i), \phi(x_j)\rangle \quad \text{s.t.} \quad 0 \le \alpha_i \le C, \ \ \sum_i \alpha_i y_i = 0$$

and the decision function is

$$f(x) = \operatorname{sign}\Big(\sum_i \alpha_i y_i \,\langle \phi(x_i), \phi(x)\rangle + b\Big)$$

Look at where $\phi$ appears: only ever inside an inner product, and never alone. Training touches $\langle \phi(x_i), \phi(x_j)\rangle$ for pairs of training points; prediction touches $\langle \phi(x_i), \phi(x)\rangle$ for a training point and a query. Substituting $K$ for every occurrence leaves an optimization in $n$ real numbers $\alpha_i$ that never mentions the feature space at all.

That is the whole trick, and it explains why a quantum feature map is such a natural fit. A quantum computer is very bad at handing you $\phi(x)$ and very good at handing you $|\langle\phi(x)|\phi(x')\rangle|^2$ — the first would require tomography and the second is one circuit and one bin of a histogram. The kernel formulation asks for exactly the quantity the hardware produces.

There is a second consequence, and it is the one that matters at scale. The eliminated $w$ satisfies $w = \sum_i \alpha_i y_i \phi(x_i)$: the solution is a combination of the training points and nothing else. That is the representer theorem, and it means the SVM cannot use any direction of the feature space that the training data does not span, no matter how large that space is.

How much of the feature space the data can actually reach

The representer theorem turns into a number, and the number is smaller than it looks. Measured on this chapter's 201-point training set, sweeping the feature map's qubit count:

    qubits      4^n   bound min(201, 4^n)   rank of the 201x201 Gram
         2       16                    16                        13
         3       64                    64                        27
         4      256                   201                        99
         6    4,096                   201                       201
         8   65,536                   201                       201

At two qubits the 201×201 Gram matrix has rank 13. The SVM is fitting in a thirteen-dimensional space, and adding training points cannot change that — they land in the same subspace. The matrix does not reach full rank until six qubits.

Put that beside §34.6's accuracy sweep on the same data:

    qubits   Gram rank   test acc
         2          13     0.7778
         4          99     0.8283
         6         201     0.8687
         8         201     0.8788
        12         201     0.8889

Over four-fifths of the total accuracy gain (+0.0909 of +0.1111) happens in the range where the Gram matrix is still rank-deficient. Once the rank saturates at 201, six more qubits buy 0.0202 — which is the same size as the "not significant" LogReg gap in §34.5.

That is a mechanism for §34.6's surprise, and it is a more specific one than "the extra depth helps." The extra qubits were not adding expressiveness in the abstract; they were adding rank to a matrix that did not have enough of it, and they stopped mattering when it did.

📐 Math Aside: the squared overlap is automatically a valid kernel, and this is why.

§34.1 says $|\phi(x)\rangle$ lives in the $2^n$-dimensional state space, which is right. But the kernel is the squared modulus, so the object that plays the role of the feature vector in the Mercer sense is not the state — it is the density matrix.

$$K(x,x') = \big|\langle\phi(x)|\phi(x')\rangle\big|^2 = \operatorname{Tr}\big[\rho(x)\,\rho(x')\big], > \qquad \rho(x) = |\phi(x)\rangle\langle\phi(x)|$$

$\operatorname{Tr}[AB]$ for Hermitian $A, B$ is the Hilbert–Schmidt inner product, and the Hermitian $d\times d$ matrices form a real vector space of dimension $d^2 = 4^n$. So the quantum kernel is a genuine inner product of genuine vectors in a $4^n$-dimensional real space.

Positive semi-definiteness then follows in two lines. For any real vector $c$,

$$\sum_{i,j} c_i c_j K_{ij} = \Big\langle \sum_i c_i \rho(x_i), \ \sum_j c_j \rho(x_j)\Big\rangle_{\rm HS} > = \Big\|\sum_i c_i \rho(x_i)\Big\|_{\rm HS}^2 \ \ge \ 0$$

A Gram matrix of inner products is PSD by construction, so an exactly-evaluated quantum kernel cannot fail the check in §34.3. That has a sharp practical corollary:

If validate_gram reports a non-PSD matrix, you have a bug, shot noise, or hardware noise — never a property of your feature map. It is a diagnostic with no false positives from the mathematics, which is exactly what makes it worth running.

It also explains the rank bound above: the feature dimension is $4^n$, not $2^n$, and the rank of any Gram matrix is at most $\min(n_{\text{samples}}, 4^n)$.

The feature map this chapter uses, and why it looks like that

The map in the code is not arbitrary, and its shape is the reason quantum kernels are interesting at all:

def feature_map(x):
    for w in range(n_qubits):
        qml.Hadamard(w)                       # into superposition
    for w in range(n_qubits):
        qml.RZ(x[..., w], wires=w)            # a phase per feature
    qml.IsingZZ(2 * (np.pi - x[..., 0]) * (np.pi - x[..., 1]), wires=[0, 1])

Hadamards, then phases only. Every gate after the Hadamard layer is diagonal in the computational basis — the $R_Z$ rotations and the $ZZ$ coupling both are. That structure has a name: it is an IQP circuit (instantaneous quantum polynomial-time), and Havlíček et al. (2019) chose it deliberately. IQP circuits are the standard example of a family that is shallow, easy to build, and conjectured to be hard to simulate classically.

The design intent was to place the kernel outside efficient classical evaluation. That intent is worth stating precisely, because it is easy to overclaim:

• The hardness results for IQP are about sampling from the output distribution.
• A kernel evaluation asks for one probability, $P(|0\dots0\rangle)$, to modest precision.
• Those are not the same problem, and no proof connects them.

So the honest statement is that this feature map is designed to be classically hard and is not known to be. Chapter 35 §35.4 is where that gap gets measured rather than argued, and §34.5 is where this particular map loses to a kernel sklearn computes in microseconds.

⚙️ Under the Transpiler: two feature maps, one diagonal block — and the transpiler finds only part of it.

The kernel circuit runs $U(x')$ and then $U^\dagger(x)$, so the naive gate count is twice the feature map's. For a diagonal map it does not have to be. Write $U(x) = D(x)\,H^{\otimes n}$ with $D$ diagonal; then

$$U^\dagger(x)\,U(x') = H^{\otimes n} D^\dagger(x) D(x') H^{\otimes n}$$

and $D^\dagger(x)D(x')$ is one diagonal block, because diagonal matrices commute and compose. Algebraically the two-qubit count should halve.

I predicted the transpiler would find that. It does not. Transpiling to ["rz","sx","x","cx"] at each optimization level, one independent feature per qubit:

text qubits naive (L0) L1 L2 L3 hand-merged (L3) algebraic ideal 2 4 2 2 2 2 2 4 12 10 10 10 6 6 6 20 18 18 18 10 10 8 28 26 26 26 14 14 10 36 34 34 34 18 18

The transpiler cancels exactly one adjacent pair — two CX — at every size, while the algebra permits removing half. At ten qubits that is 34 CX where 18 suffice, and depth 60 where 33 suffices. Optimization levels 1, 2 and 3 are identical, so turning the dial up does not help; Chapter 28 §28.4 measured the same ceiling from a different direction, finding levels 2 and 3 differing on only 14 of 40 circuit-seed pairs.

The hand-merged circuit is not an approximation. It reproduces the kernel to machine precision — the largest disagreement across 2 to 10 qubits was $2.8\times10^{-17}$.

The reason the transpiler misses it is scope. CommutativeCancellation looks for gates it can prove commute across a bounded window; recognizing that an entire interleaved block is diagonal and resynthesizing it is a global fact about the circuit, not a local one. This is a case where knowing your feature map's structure beats any optimization level, which is Chapter 28 §28.8's conclusion arriving in a new place.

And it stops working the moment the map is not purely diagonal. Adding repetitions inserts fresh Hadamard layers between the diagonal blocks, and the merge disappears:

text reps one map compute-uncompute ratio 1 6 10 1.67x 2 12 22 1.83x 3 18 34 1.89x

At three repetitions the kernel circuit costs essentially double the feature map, with no cancellation left to find. Note which row §34.4's sweep will find worst.

34.2 The Gram matrix, and a performance note worth having

Training an SVM needs the kernel between every pair of training points — the Gram matrix, $n^2$ entries.

The obvious implementation loops:

   201 x 201 = 40,401 kernel entries in 51.3 s

PennyLane broadcasts over a leading batch axis, so all 40,401 pairs can be submitted at once:

def gram(A, B):
    ai = np.repeat(A, len(B), axis=0)
    bi = np.tile(B, (len(A), 1))
    return np.asarray(kernel_circuit(ai, bi))[:, 0].reshape(len(A), len(B))

   201 x 201 = 40,401 kernel entries in 0.11 s      -- 478x faster

Roughly a five-hundredfold speedup from removing a Python loop. (Repeat runs gave 478× and 868× depending on machine load; the order of magnitude is the point.) Chapter 33 §33.3 hit the same thing and it mattered there too. On a simulator this is the difference between a chapter that runs and one that times out; on hardware the same batching becomes a single job submission rather than 40,401.

What batching does and does not fix

The arithmetic is worth doing, because it separates two costs that look like one.

   looping:   51.3 s / 40,401 entries  =  1,270 us per entry
   batched:    0.11 s / 40,401 entries =      2.7 us per entry

The per-entry work did not get 470× cheaper. The circuit is the same circuit; what vanished was roughly 1.27 milliseconds of Python and PennyLane dispatch overhead per call, paid 40,401 times. On a simulator, dispatch dominates a two-qubit circuit by three orders of magnitude, and the batched version amortizes it across the whole array.

That distinction is the whole point on hardware, where the analogous overhead is a job submission rather than a function call. Chapter 39 §39.3 measured 100 circuits submitted as 100 jobs costing about 99× the wall clock of one batched job, and Chapter 33 §33.3 measured ~100× from the same fix inside a training loop. Three chapters, three settings, the same lesson: the loop you wrote is not the cost you think it is.

And here is what batching does not fix. Every entry is still a circuit, and every circuit still needs shots. Batching removes the per-submission cost and leaves the per-shot cost exactly where it was — which is §34.7's subject, and it is the term that turns out to decide the chapter. Batching makes the Gram matrix possible; it does not make it cheap.

🐛 Debug This: the Gram matrix that came back asymmetric.

Batching requires flattening a 2-D grid of pairs into a 1-D array and reshaping the results back. There are two ways to do it and only one is right:

python ai = np.repeat(A, len(B), axis=0) # a0 a0 a0 ... a1 a1 a1 ... bi = np.tile(B, (len(A), 1)) # b0 b1 b2 ... b0 b1 b2 ...

Swap repeat for tile — an easy slip, since both "duplicate an array" — and you get a0 a1 a2 ... a0 a1 a2 ... paired with b0 b0 b0 ... b1 b1 b1 ..., which is the transpose of the matrix you wanted.

The symptom is that nothing obviously breaks. K(x,x) = 1 still holds, because the diagonal of a matrix and the diagonal of its transpose are the same. SVC(kernel='precomputed') fits without complaint. The accuracy is merely somewhat worse than it should be, which is indistinguishable from a feature map that needs tuning — and §34.4 has just established that feature maps need tuning, so there is a ready explanation waiting to absorb the bug.

The check that catches it is symmetry, and only because the Gram matrix is square and the error is a transpose:

python assert np.allclose(K, K.T) # fails immediately on the swap

For the test Gram matrix, which is rectangular ($m \times n$), symmetry is not available and the reshape is not even the same shape as its transpose — so the failure mode there is a broadcasting error, which is the good case. The dangerous version of this bug is the one on the square matrix, where the wrong answer has the right shape.

This is Chapter 26 §26.3's rule in kernel form: a check that passes on a broken input is not a check. validate_gram checks the diagonal, symmetry, and PSD together for exactly this reason — the diagonal alone would have missed it.

💰 Cost and Queue: on a per-task platform, batching is the difference between $0.30 and $6,090.

Chapter 39 §39.4 lists AWS Braket's superconducting pricing at roughly **$0.30 per task plus $0.00035 per shot**. A Gram matrix for 201 training points needs $n(n+1)/2 = 20{,}301$ unique entries. Submitted one at a time:

text 20,301 tasks x $0.30 = $6,090.30 in task fees, before a single shot one batched task = $0.30

Put that beside the shot cost at two qubits — 3.045e5 shots at $0.00035 is **$107 — and the arithmetic is stark: the submission overhead is 57× the compute.** A team that batches correctly and a team that does not are running the same experiment at two orders of magnitude apart in price, and neither invoice line is labelled "loop."

The per-minute model hides it differently. IBM's ~$96/min charges QPU time, so 20,301 separate submissions cost the same as one batch in device time — and then the queue arrives instead. Chapter 39 measured a five-minute queue giving a utilization of $2.31\times10^{-5}$; 20,301 queue waits at five minutes each is 70 days of wall clock for 30 seconds of computing.

Same mistake, two platforms, two completely different bills — one in dollars and one in months.

34.3 Training is convex

Here is the structural advantage, stated plainly.

svc = SVC(kernel="precomputed")
svc.fit(K_train, y_train)          # ~2 ms

   SVC(kernel='precomputed').fit  ->  1.2 ms
   support vectors: 91 of 201

The SVM dual is a convex quadratic program. There is exactly one optimum, standard solvers find it exactly, and the result does not depend on where you started.

Compare Chapter 33's variational classifier:

                        variational (Ch. 33)        kernel (Ch. 34)
   landscape            non-convex                  CONVEX
   initialization       random, matters             none
   learning rate        a hyperparameter            none
   barren plateaus      measured, 88x collapse      not applicable
   optimum              whatever 60 steps found     found exactly
   reproducibility      seed-dependent              deterministic

🔬 Honest Assessment: this is a real advantage and it should be said clearly.

Every trainability problem Part VI has measured — Chapter 32's barren plateaus, Chapter 33's dependence on initialization and step count, the gap between what a circuit can represent and what training finds — disappears. The quantum circuit computes a fixed function; the learning is classical and solved.

The quantum part is no longer being optimized. It is being evaluated.

That is the strongest structural claim in Part VI, and it survives everything that follows.

What the convexity is resting on

"Convex" is not a property of the SVM. It is a property of the SVM given a valid kernel matrix, and the dependence is exact enough to write down.

Return to the dual from §34.1 and write it in matrix form. Let $Q_{ij} = y_i y_j K_{ij}$, so that the objective is

$$\max_\alpha \ \mathbf{1}^\top \alpha - \tfrac{1}{2}\,\alpha^\top Q\, \alpha$$

over a box-and-hyperplane feasible region, which is convex regardless of anything. The objective is concave if and only if $Q$ is positive semi-definite — and since $Q = \operatorname{diag}(y) \, K \, \operatorname{diag}(y)$ with $y_i = \pm 1$, $Q$ is PSD exactly when $K$ is.

So the chain is short and every link is checkable:

   K is a Gram matrix of inner products      (proved in Sec 34.1's Math Aside)
     -> K is PSD
       -> Q is PSD
         -> the dual objective is concave
           -> ONE maximum, found exactly, independent of initialization

The convexity in the table above is not a feature of SVC. It is a feature of $K$, and the quantum circuit is what supplies it. That is a more precise version of the claim than "kernel methods are convex," and it tells you exactly what to check.

📐 Math Aside: what actually happens when the Gram matrix is not PSD.

§34.1 proved that an exactly-evaluated quantum kernel is PSD. On hardware it will not be exactly evaluated, and the failure is worth understanding rather than patching.

If $K$ has a negative eigenvalue $\lambda < 0$ with eigenvector $v$, then along the direction $v$ the dual objective $-\tfrac{1}{2}\alpha^\top Q \alpha$ is convex rather than concave — it curves upward, and the maximizer runs to the boundary of the box. Three things follow:

1. The optimum is no longer unique. There can be several local maxima on the feasible polytope, and which one you get depends on the solver's path. The determinism in §34.3's table is gone.
2. libsvm's SMO does not diverge; it converges to something. It is a working-set method that makes monotone progress on the objective, so it terminates. It just terminates at a point with no optimality guarantee — and it reports no error, because from the solver's perspective nothing unusual happened.
3. The result is still a classifier. It fits, it predicts, and it scores. The only thing you have lost is the reason to believe the score.

That third point is why this belongs in a chapter and not a footnote. A failure that produced an exception would be a nuisance. A failure that produces a plausible number is Part V's recurring subject — a measurement that cannot detect the thing being asked about — arriving in the one place in Part VI where the mathematics was supposed to have removed all such questions.

The standard repairs each cost something specific:

text method what it does what it costs clip negative eigenvalues K -> sum max(0, lambda) vv' changes the kernel shift the spectrum K -> K + |lambda_min| I inflates the diagonal project to nearest PSD convex program on K O(n^3), and still not K

PennyLane 0.45.1 ships the third as qml.kernels.closest_psd_matrix(K, fix_diagonal=False) and the first as qml.kernels.threshold_matrix(K). Both are honest tools and neither recovers information that was not measured — they make the matrix fittable, not correct. If the negative eigenvalues are large, the answer is more shots, not more post-processing.

The cost that convexity did not remove

It is worth being exact about what the 1.2 ms is and is not, because the table above invites reading it as the training cost.

It is the training cost — of the classical half. The SVM solves a 201-variable quadratic program in 1.2 ms. What it does not include is the 20,301 kernel evaluations that had to happen first, which on the simulator took 0.11 s batched and 51.3 s looped, and which on hardware are §34.7's subject.

   what                                       time
   building the Gram matrix (batched, sim)    0.11 s      = 99% of the total
   SVC(kernel='precomputed').fit              0.0012 s    =  1%

The convex solve is one percent of the wall clock even on a simulator, where the quantum part is free. Chapter 33's variational model had the opposite shape: the circuit evaluations and the optimization were interleaved, so removing the optimizer would have removed most of the calls. Here the optimizer was never where the work was.

🔬 Honest Assessment: convexity is a guarantee, not a speedup.

What §34.3 buys is that the number you report is the number the model can achieve, rather than the number sixty Adam steps from one random start happened to find. Chapter 33 §33.5b measured that distinction directly: initialization alone moved test accuracy by 0.0606, three times the true model difference it was trying to measure.

That entire source of variance is gone here, and it is gone by construction rather than by running more seeds. On the credibility of a reported result, that is a large win.

It is just not a win in accuracy, and §34.5 is where that shows.

🔀 In Another Framework: the same kernel three ways.

PennyLane 0.45.1 ships a qml.kernels module, and it is the shortest path if you are not batching by hand:

python from pennylane import kernels K_train = kernels.square_kernel_matrix(X_train, kernel, assume_normalized_kernel=True) K_test = kernels.kernel_matrix(X_test, X_train, kernel)

assume_normalized_kernel=True fills the diagonal with 1 instead of evaluating it — worth $n$ circuits, and worth not doing when you are trying to detect the noise in §34.6's Noise Report, because the diagonal is where that shows up first. The module also carries target_alignment, which scores a feature map against the labels without training an SVM, and is the right tool for §34.4's sweep.

Qiskit 2.5.1 has the feature map but not the kernel: zz_feature_map(feature_dimension=2, reps=1) builds the circuit, and you compose it with .inverse() yourself and read $P(|0\dots0\rangle)$, or install the separate qiskit-machine-learning package for FidelityQuantumKernel. It is not in the Qiskit metapackage, so import qiskit alone will not get you a kernel.

Note the default. zz_feature_map's signature is reps: int = 2 — and reps=2 is the row §34.4's sweep measures at 0.6167, the worst two-qubit result in the table and 0.2333 below the tuned one. The library default is not a recommendation; it is a default, and this chapter's own sweep is the argument for not accepting it.

Cirq 1.7.0 has neither, and that is a deliberate scope decision rather than an omission. You build cirq.Circuits for $U(x')$ and $U^\dagger(x)$, call cirq.Simulator().simulate(...), and take abs(final_state_vector[0])**2. Twenty lines, no abstractions, and Chapter 14 §14.1's trade in miniature: the framework that gives you the least gives you the fewest surprises about what is actually being computed.

All three produce the same number. §34.1's Math Aside is why — the kernel is defined by the physics, not by the API.

34.4 The feature map is a hyperparameter

What does not disappear is the design problem. It moves.

A first attempt — a plausible ZZ-style feature map, untuned — scored 0.6364. Sweeping qubit count, repetitions, and input scaling:

    qubits  reps  scale   test acc   mean K offdiag
         2     1    0.5     0.8167           0.4027
         2     1    1.0     0.8500           0.2821
         2     1    2.0     0.6833           0.2502
         2     2    1.0     0.6167           0.3139
         3     1    1.0     0.8167           0.2264
         3     2    2.0     0.5833           0.2056

0.6364 untuned to 0.8500 tuned — a swing larger than any difference this chapter will measure between methods.

⚠️ Common Pitfall: "no hyperparameters to train" is not "no hyperparameters."

The variational model's learning rate and initialization are gone. In their place are the feature map's structure, depth, entangling pattern, and input scaling — and the measurement above shows they matter more than the choice of method.

A quantum kernel result without a feature-map sweep is a result about one arbitrary feature map.

Note also the last column: higher qubit counts and more repetitions push the mean off-diagonal kernel value down. That is §34.6's subject, and it is visible here as a side effect of tuning.

Reading the sweep as an experiment rather than a table

Six rows is a small sweep and it should not be over-read, but it does support three statements, and they are not the ones a reader usually takes away.

Input scaling is the largest single effect. Holding qubits and reps fixed at 2 and 1 and varying only the scale:

    scale   test acc
      0.5     0.8167
      1.0     0.8500
      2.0     0.6833

A factor of two in a preprocessing constant costs 0.1667 of accuracy — nearly three times the $+0.0576$ that separates this chapter's quantum kernel from SVC(rbf). And scaling is not even a quantum design choice; it is where you put the StandardScaler.

The mechanism is visible in the last column of the main table. The map's phases are $x_i$ and $2(\pi - x_0)(\pi - x_1)$, both of which are angles. Doubling $x$ does not double the kernel's resolution; it wraps the phases further around the circle, and points that were far apart in data space start landing on top of each other. The mean off-diagonal value falls from 0.4027 to 0.2502 across the three rows, which is the signature of a map that is spreading states without spreading information.

Repetitions hurt here, and they hurt for a structural reason. The reps=2 row scores 0.6167, the worst two-qubit result. §34.1's transpiler note showed why the circuit gets more expensive — repetitions insert Hadamard layers between the diagonal blocks, the compute-uncompute merge fails, and the two-qubit count goes from 10 to 22 at four qubits. You pay double the gates for an accuracy 0.2333 below the tuned map. That is not proof that repetitions are always wrong; it is a measurement that the default is not free.

And the qubit count barely matters at all in this range. Comparing the two rows that differ only in qubits — 2/1/1.0 at 0.8500 against 3/1/1.0 at 0.8167 — gives $-0.0333$, the smallest effect in the sweep. §34.1's rank measurement predicts this: at two qubits the Gram matrix already has rank 13 out of a bound of 16, and a third qubit raises the bound to 64. The extra capacity is real and this data does not need it.

📊 What the Numbers Say: this table is a hyperparameter comparison, and §34.5 is a method comparison, and they are on the same axis.

text swing from tuning the feature map 0.6364 -> 0.8500 = 0.2136 full spread across the sweep table 0.5833 -> 0.8500 = 0.2667 SVC(rbf) - quantum kernel (Sec 34.5) = 0.0576

The design decision is worth 3.7× the method decision, and the full sweep spread is worth 4.6×.

Two consequences, and the second is the uncomfortable one:

1. An untuned quantum kernel reported against a tuned classical baseline is not a comparison. It is a measurement of how much tuning the quantum side did not get.
2. And so is the reverse. This chapter tuned the feature map over six configurations and used SVC() at scikit-learn defaults. If the RBF kernel's $\gamma$ and $C$ had been swept as thoroughly, SVC(rbf)'s 0.8889 would likely go up, not down. The measured gap of 0.0576 is a lower bound on the classical advantage, not an upper one.

🧪 Run It: sweep the axis this table does not have.

Every row above varies the circuit. None varies the entangling structure, which is the axis that decides whether the kernel is quantum in any meaningful sense.

Run the sweep again with three variants at fixed qubits, reps and scale:

text A. no IsingZZ at all -- a product feature map B. IsingZZ on a chain -- what this chapter uses C. IsingZZ on all pairs -- Qiskit's entanglement="full" default

Variant A is the important one. With no entangling gate the state factorizes, $|\phi(x)\rangle = \bigotimes_w |\phi_w(x_w)\rangle$, so the kernel factorizes too:

$$K(x,x') = \prod_{w=1}^{n} \big|\langle\phi_w(x_w)|\phi_w(x'_w)\rangle\big|^2$$

— a product of $n$ two-dimensional overlaps, each computable in closed form on a laptop. If variant A scores within noise of variant B, the chapter's quantum kernel has been beaten by a classical kernel that is a one-line formula, and no circuit was needed at all.

Exercise 34.13 asks this and it is not rhetorical. Record ten splits per variant, and report the spread across variants beside the $\pm 0.0083$ that separates methods in §34.5. The comparison you are running is only meaningful if the entangling gate is doing something, and that is measurable in about thirty lines.

34.5 The comparison

Tuned feature map, ten independent datasets and splits — the protocol Chapter 33 §33.3 established after a single split misled it:

   model                        mean      std     min     max
   quantum kernel SVM         0.8313   0.0381  0.7778  0.9091
   SVC (rbf)                  0.8889   0.0310  0.8283  0.9394
   kNN                        0.8970   0.0377  0.8283  0.9495
   LogReg                     0.8414   0.0463  0.7677  0.9091

   SVC (rbf) - quantum = +0.0576 +/- 0.0083   SIGNIFICANT
   kNN       - quantum = +0.0657 +/- 0.0137   SIGNIFICANT
   LogReg    - quantum = +0.0101 +/- 0.0070   not significant

The classical RBF kernel beats the quantum kernel by $+0.0576 \pm 0.0083$ — seven standard errors, on the same data, using the same SVM solver. The only difference between the two rows is which kernel function was used.

And the comparison that closes the loop with Chapter 33:

   quantum kernel SVM (Ch. 34)      0.8313 +/- 0.0381
   1-qubit variational (Ch. 33)     0.8343 +/- 0.0407

Statistically indistinguishable. Two structurally different quantum approaches — one convex and one not, one with 6 parameters and one with none — land in the same place, and both tie with logistic regression.

The convexity advantage is real and it did not produce a better classifier. It removed the optimization problem, and the optimization was not what was limiting the result.

Why this particular comparison is unusually clean

Most quantum-versus-classical comparisons in this book have a confound somewhere, and the book has been candid about them. Chapter 32's iris was solved by everything. Chapter 33 compared a variational circuit against kNN — different model classes, different training procedures, different failure modes, and a single split that turned out to be a lucky draw.

This one has almost none of that, and it is worth listing what is held fixed:

   held constant                       varied
   the datasets (10, seeded)           the kernel function
   the train/test splits (10, seeded)
   the SVM solver (libsvm)
   the SVM formulation (soft-margin dual)
   the regularization C (default 1.0)
   the training set (201) and test set (99)

The quantum kernel SVM row and the SVC (rbf) row differ in one function and nothing else. Both are libsvm solving the same convex dual on the same 201 points; one is handed a precomputed matrix and the other computes $\exp(-\gamma\|x-x'\|^2)$ internally. A difference of $+0.0576 \pm 0.0083$ between them is a difference between two similarity functions, full stop.

That is a rarer thing than it sounds. It is the cleanest head-to-head in Part VI, and it is the one the quantum side loses most decisively — seven standard errors against kNN's five and LogReg's not-significant. The comparison that controls the most is the comparison that flatters the quantum method least, and Chapter 40 §40.3's scorecard finds the same across all six of the book's head-to-heads.

One caveat belongs here rather than in a footnote. SVC() used scikit-learn's defaults — C=1.0, gamma='scale' — while the quantum feature map was tuned over six configurations in §34.4. The comparison is therefore biased toward the quantum side, and the measured gap is a lower bound on the classical advantage.

Where this would flip

The chapter has established that a quantum kernel loses on this problem. That is a statement about this problem, and the useful question is what would have to be different. Four conditions, in decreasing order of how much evidence supports them.

1. The data is a quantum state. This is the only one with no counterargument. If $x$ is not a classical vector but a state produced by an experiment or by another quantum computation, then $K(x,x') = |\langle\phi(x)|\phi(x')\rangle|^2$ is an overlap between two objects you already hold, and there is no classical feature vector to hand SVC at all. Chapter 32 §32.2's input problem — $N - \log_2 N - 1$ gates per sample, per epoch — goes to zero, and Chapter 35 §35.2 measures exactly that. Note what changes and what does not: the encoding cost disappears; the $n^2$ Gram evaluations and their shots do not.

2. The classification structure is genuinely quantum in origin. Liu, Arunachalam and Temme (2021) construct a learning problem based on discrete-log structure where a quantum kernel provably beats any classical learner under standard assumptions. This is a real separation and it is the strongest rigorous result in QML, and the thing to notice is the shape of the construction: the data was built so that the only efficiently-computable similarity function that separates the classes is the quantum one. Moons at noise 0.30 has no such property. The proven advantage is not evidence that quantum kernels are good similarity functions; it is evidence that a similarity function can be made hard.

3. The feature dimension is high and the sample count is low. §34.7's $n^2$ is in the number of samples, not features, and §34.6's concentration is in the number of features. Those pull in opposite directions, which leaves a window: a problem with few hundred samples and a feature map whose concentration is controlled would pay a Gram bill measured in QPU-hours rather than QPU-days. Case Study 2 puts the six-qubit figure at 0.1 QPU-days. That window is real and it is narrow, and nothing in this chapter demonstrates a useful problem inside it.

4. The classical kernel is the wrong shape for the data. RBF encodes a specific prior — similarity falls off with Euclidean distance — and it is an extremely good prior for moons, which is two Euclidean blobs bent into arcs. On data with periodic or group structure, RBF is a poor match and a feature map built from that structure could beat it. This is a design argument, not a quantum argument, and it predicts that the winning method would be a hand-designed classical kernel about as often as a quantum one.

🔬 Honest Assessment: notice which conditions are absent from the list.

More qubits is not on it. §34.1's rank measurement and §34.6's accuracy sweep both saturate, and §34.6's concentration and §34.7's shot budget both get exponentially worse with size. There is no qubit count at which this chapter's result reverses.

Better hardware is not on it either. Every measurement in this chapter came from an exact simulator. The quantum kernel loses by seven standard errors with zero noise, which is the same conclusion Chapter 33 §33.5b reached about the most hardware-robust model in Part VI. Noise is not what is holding these results back, and fidelity improvements will not move them.

Chapter 21 §21.7's question, asked of this chapter: compared to what? On this data, compared to one line of sklearn.

34.6 Kernel concentration — and a claim I had to withdraw

The known failure mode of quantum kernels is concentration: as the feature map spreads states over more of Hilbert space, any two states become nearly orthogonal, so $K(x,x') \to 0$ for $x \neq x'$ and the Gram matrix approaches the identity.

Measured, on random points with one feature per qubit:

    qubits   mean offdiag   std offdiag
         2        0.25147       0.21980
         4        0.06195       0.07810
         6        0.01497       0.02905
         8        0.00429       0.00664
        10        0.00088       0.00163

A collapse of several hundred fold across eight qubits — 286× and 327× on repeat draws. This is the kernel analogue of Chapter 32's barren plateaus, and it has the same character: an exponential loss of signal with system size.

Where those numbers come from

The collapse is not merely exponential; it hits a specific, predictable value, and the prediction takes one line.

Two independent Haar-random pure states in dimension $d$ have squared overlap distributed as $\mathrm{Beta}(1, d-1)$, whose mean is

$$\mathbb{E}\big[|\langle\psi|\varphi\rangle|^2\big] = \frac{1}{d} = \frac{1}{2^n}$$

The intuition is worth having in one sentence: a random state spreads its amplitude over $d$ dimensions, so its overlap with any fixed direction is one part in $d$ on average. A feature map that genuinely scrambles is a map whose outputs look Haar-random, so its kernel should sit at $1/2^n$.

Compare that against the measured column above, and against the independent run used for §34.7's shot budget:

    qubits    2^n      1/2^n     measured   ratio      run 2   ratio
         2      4   0.250000      0.25147   1.006    0.25346   1.014
         4     16   0.062500      0.06195   0.991    0.06105   0.977
         6     64   0.015625      0.01497   0.958    0.01494   0.956
         8    256   0.003906      0.00429   1.098    0.00360   0.922
        10  1,024   0.000977      0.00088   0.901    0.00078   0.799

Every measured value sits within 10% of $1/2^n$, across two independent runs and a factor of 256 in magnitude. The concentration is not "roughly exponential" — it is sitting on the Haar floor.

That reframes the failure mode more sharply than "values get small." The Gram matrix approaches $\frac{1}{2^n}(J - I) + I$, which is the identity plus a vanishing constant — and a constant carries no information about $x$ at all. The kernel is not becoming noisy; it is becoming uninformative in a specific direction, toward the matrix that says every pair of points is equally dissimilar.

There is one honest discrepancy, and it is the interesting part. The spread does not match as well as the mean:

    qubits   Haar std   measured std   ratio   measured std / mean
         2    0.19365        0.21980    1.14                  0.87
         4    0.05871        0.07810    1.33                  1.26
         6    0.01538        0.02905    1.89                  1.94
         8    0.00389        0.00664    1.71                  1.55
        10    0.00098        0.00163    1.67                  1.85

The measured spread runs 1.1× to 1.9× above the Haar prediction, and the gap widens with qubit count. That is a real signal: a depth-1 ZZ map is not a 2-design, so it does not scramble as completely as Haar. The residual structure above the Haar floor is the only thing the kernel has left to classify with — and note the last column, which says the off-diagonal values differ from each other by about as much as they are. §34.7's shot budget depends on exactly that fact.

📐 Math Aside: the redundant regime never reaches the floor, and that is the whole of §34.6.

Take the same comparison and evaluate it against $1/2^n$:

text qubits 1/2^n REDUNDANT (2 features) times above the floor 2 0.250000 0.25346 1.0 4 0.062500 0.10728 1.7 6 0.015625 0.05749 3.7 8 0.003906 0.03478 8.9 10 0.000977 0.02251 23.1

The redundant map's kernel sits 23× above the Haar floor at ten qubits, and the gap grows. The independent map sits on the floor at every size.

The reason is dimensional, and it is exact. A map reading $f$ independent features produces states on an $f$-dimensional manifold inside the $2^n$-dimensional state space. Adding qubits enlarges the space; it does not enlarge the manifold. With $f = 2$ the states never leave a two-parameter surface no matter how many qubits are available, so they cannot become Haar-typical and cannot concentrate to $1/2^n$.

The measured collapse factors say the same thing: 11.26× redundant against 285.8× independent, over the identical qubit range and the identical circuit family. The only difference is how many numbers the map was given.

Is this the same phenomenon as a barren plateau?

Exercise 34.23 asks it and the answer is genuinely two-sided, so it is worth settling here.

The case that they are the same. Both are exponential losses of signal with qubit count. Both arise from states spreading over Hilbert space until typical quantities approach their Haar averages. Both are made worse by the two things that make a circuit expressive — depth and entanglement. And both have the same practical consequence: the quantity you need to resolve shrinks like $2^{-n}$ while the shots needed to resolve it grow, so the bill is a product. Chapter 32 §32.5 wrote that product for gradients; §34.7 writes it for kernel entries, and the two paragraphs are structurally identical.

The case that they are different, and it is the more useful case. A barren plateau is a statement about a loss landscape — the gradient of a cost with respect to parameters vanishes. Kernel concentration is a statement about a fixed function — there are no parameters and no gradients, and nothing is being optimized. The consequences differ accordingly:

                       barren plateau (Ch. 32)      kernel concentration (Ch. 34)
   what vanishes       d(cost)/d(theta)             K(x, x') for x != x'
   what it blocks      finding the optimum          distinguishing the data
   fix by more shots   yes, at 1/g^2 each           yes, at 1/K^2 each
   fix by better init  sometimes                    not applicable -- no init
   fix by shallower    yes                          yes, and it costs expressiveness
   detectable by       gradient variance            mean off-diagonal

The distinction that matters: convexity does not protect you from concentration. §34.3's advantage is that the optimization is solved exactly — and it will solve exactly a Gram matrix that has become the identity, returning a perfectly-optimal classifier of a matrix carrying no information. The guarantee is about the solver, and the signal loss happens before the solver runs.

That is the sharpest thing in this chapter's relationship to Chapter 33. Removing the optimization problem removed one exponential and left the other exactly where it was.

📉 Noise Report: gate noise counterfeits concentration, and breaks the diagonal first.

Every number in this chapter came from an exact simulator. Re-running the kernel on default.mixed with a depolarizing channel after every gate, 20 random points, one independent feature per qubit:

text 4 qubits (uniform floor 1/2^4 = 0.06250) gate error K(x,x) mean offdiag min eig unit diag? PSD? 0e+00 1.00000 0.05705 5.16e-01 True True 1e-04 0.99800 0.05705 5.14e-01 False True 1e-03 0.98023 0.05711 5.04e-01 False True 1e-02 0.82142 0.05767 4.07e-01 False True 5e-02 0.40190 0.05954 1.56e-01 False True

Three findings, and they run in different directions.

The unit diagonal fails at every non-zero error rate. At $10^{-4}$ — better than Chapter 39's measured median sx error of $2.44\times10^{-4}$ — $K(x,x)$ is already 0.99800, and validate_gram's atol=1e-8 rejects it. The first property §34.1 checks is the first one hardware destroys, and it is the most useful diagnostic precisely because it has a known exact answer.

Noise drags the off-diagonal toward the uniform value $1/2^n$ — 0.05705 rises to 0.05954 against a floor of 0.06250, closing 46% of the gap at 5% gate error. Depolarizing noise mixes the state toward maximally mixed, and the maximally mixed state's overlap with anything is exactly $1/2^n$. So noise and concentration push the kernel to the same place, and a mean off-diagonal value near $1/2^n$ does not tell you which one you are looking at. Only the diagonal separates them.

PSD survives. The minimum eigenvalue stays comfortably positive at every rate. Depolarizing noise is a completely positive map, so the noisy kernel is still a legitimate inner product — of different states. You have not broken the mathematics; you have silently changed the feature map.

And the obvious repair is worse than nothing. Rescaling by the measured diagonal, $\tilde K_{ij} = K_{ij}/\sqrt{K_{ii}K_{jj}}$, restores the unit diagonal exactly and overshoots everything else:

text gate error raw offdiag rescaled noiseless |error| raw |error| rescaled 1e-02 0.06788 0.08258 0.06929 0.0014 0.0133 5e-02 0.06480 0.16058 0.06929 0.0045 0.0913

At 5% gate error the naive normalization is 20× further from the truth than doing nothing, because it applies a single-point correction to a two-point quantity. PennyLane 0.45.1 ships qml.kernels.mitigate_depolarizing_noise(K, num_wires, method) for this, which uses the measured diagonal to estimate the depolarization rate and then inverts the channel — a different and correct calculation. The lesson is Chapter 13's: a mitigation that makes the symptom go away is not the same as one that recovers the number.

The claim that was wrong

I wrote, before running it, that concentration would make the SVM memorize the training set and generalize at chance — every point its own island, every training point a support vector.

Measured on this chapter's actual data, sweeping qubits from 2 to 12:

    qubits   mean offdiag   train acc   test acc   support vecs      gap
         2        0.28387      0.8458     0.7778      91 / 201   0.0680
         4        0.12910      0.9254     0.8283      97 / 201   0.0971
         6        0.07021      0.9453     0.8687     114 / 201   0.0766
         8        0.04587      0.9552     0.8788     128 / 201   0.0764
        10        0.03300      0.9552     0.8889     132 / 201   0.0663
        12        0.02531      0.9602     0.8889     144 / 201   0.0713

Test accuracy rose, from 0.7778 to 0.8889. The generalization gap stayed roughly constant at 0.07. Support vectors grew but nowhere near all 201. No memorization.

The mechanism was right and the regime was wrong, and the difference is measurable:

    qubits   REDUNDANT (2 features over n qubits)   INDEPENDENT (n features)
         2                               0.25346                     0.25147
         4                               0.10728                     0.06195
         6                               0.05749                     0.01497
         8                               0.03478                     0.00429
        10                               0.02251                     0.00088

⚛️ Concentration is driven by the dimension of the data the map sees, not by the qubit count.

This chapter's moons data has two features. Spreading them over ten qubits re-encodes the same two numbers redundantly — adding expressive depth without spreading the state over more of Hilbert space. Concentration is mild (11× over eight qubits) and the extra depth helps.

A map with one independent feature per qubit does spread the state, and concentration is severe (several hundred fold over the same range).

The dangerous regime is high-dimensional data, which is exactly the regime kernels are for.

I have kept both measurements because the correction is the useful part: the failure mode is real, it is severe where it applies, and asserting that it applies without checking the feature dimension gets the sign of the effect wrong.

34.7 The Gram matrix bill

Chapter 32 costed training. Chapter 33 costed inference. The kernel method has a third shape of cost, and it is set by the $n^2$.

A Gram matrix for $n$ training points needs $n(n+1)/2$ unique entries. Each is a circuit whose output is a probability of size $K$, and resolving a probability of size $K$ to relative precision needs $\mathcal{O}(1/K^2)$ shots — Chapter 24 §24.3's wall, arriving again.

So concentration and the shot budget multiply, exactly as barren plateaus and the shot budget did in Chapter 32 §32.5:

    qubits     mean K   shots/entry     total shots   QPU hours   QPU days
         2    0.25346            15       3.045e+05         0.0        0.0
         4    0.06105           268       5.441e+06         0.2        0.0
         6    0.01494         4,480       9.095e+07         2.5        0.1
         8    0.00360        77,160       1.566e+09        43.5        1.8
        10    0.00078     1,643,655       3.337e+10       926.9       38.6

At ten qubits the Gram matrix alone costs 38.6 QPU-days — before any training — on a 201-sample problem, for a kernel whose off-diagonal entries are 0.00078 and therefore carry almost no information anyway.

And the $n^2$ is the other half. This is 201 training points. A dataset ten times larger needs a hundred times the entries, and inference against $m$ test points needs $m \times n$ more.

🔬 Honest Assessment: the kernel method trades a training problem for a data-size problem.

Chapter 33's variational cost scaled as $(2p+1) \times \text{samples} \times \text{steps}$ — linear in the dataset. The kernel cost scales as $n^2$, and the constant is set by how concentrated the kernel is.

Convexity removed the optimization. It did not remove the shots, and it introduced a quadratic.

Where the $1/K^2$ comes from, and how conservative it is

The shots-per-entry column is the term that spans five orders of magnitude, so it deserves a derivation rather than an assertion.

Chapter 24 §24.3 established the general form: an estimate with single-shot standard deviation $\sigma$ reaches precision $\epsilon$ in

$$N \sim \left(\frac{\sigma}{\epsilon}\right)^2$$

Two choices turn that into a number, and both are visible in §34.6's measurements.

What precision $\epsilon$ is needed? The Gram matrix's usable content is the variation among the off-diagonal entries, so you must resolve differences at the scale on which they actually differ. §34.6's spread table gives that scale directly: the measured standard deviation of the off-diagonal values runs 0.87× to 1.94× the mean, across the whole qubit range. The entries differ from each other by about as much as they are, so $\epsilon \approx K$. That is a measured justification for the choice, not a stipulation.

What is $\sigma$? A kernel evaluation is a Bernoulli trial — the shot either lands in $|0\dots0\rangle$ or it does not — so strictly $\sigma^2 = K(1-K)$. Taking the conservative bound $\sigma = \mathcal{O}(1)$, as Chapter 32 §32.5 does for gradients, gives

$$N \sim \frac{1}{K^2}$$

which is the column in the table. Taking the exact Bernoulli variance instead gives $N \sim K/K^2 = 1/K$, and it is worth writing both out:

    qubits     mean K   1/K^2 shots      QPU days    1/K shots    QPU days
         2    0.25346            15        0.0000            3      0.0001
         4    0.06105           268        0.0006           16      0.0004
         6    0.01494         4,480        0.1053           66      0.0016
         8    0.00360        77,160        1.8130          277      0.0065
        10    0.00078     1,643,655       38.6200        1,282      0.0301

The two models differ by a factor of about 1,280 at ten qubits — 38.6 QPU-days against 0.72 QPU-hours. That is a large enough spread that the honest statement is a bracket, and three things should be said about it.

The chapter's model is the conservative one, and it is the book's convention. Chapter 32 §32.5 priced gradients at $1/g^2$ from the same $\sigma = \mathcal{O}(1)$ assumption, and it is also the correct model in the general concentration setting, where a kernel concentrates around a non-zero constant $c$ with deviations of size $\delta$. There $\sigma^2 = c(1-c) = \mathcal{O}(1)$ genuinely, and $N \sim 1/\delta^2$ exactly. This chapter's map happens to concentrate toward zero, which is the one regime where the Bernoulli variance shrinks along with the signal.

Neither model is the number you would budget from anyway. Both price a single entry at one standard error, and a usable Gram matrix needs 20,301 of them with errors small enough not to perturb the SVM's solution. The real requirement sits above the $1/K$ line and below wherever you decide the accumulated perturbation stops mattering — which is a measurement nobody in this chapter made.

And the conclusion does not depend on the choice. $1/K$ with $K \sim 2^{-n}$ is $\mathcal{O}(2^n)$ shots per entry; $1/K^2$ is $\mathcal{O}(4^n)$. Both are exponential in the qubit count, and both are multiplied by the same $n^2$. The bracket moves where the wall is, not whether there is one — six qubits versus ten, on a 201-sample toy problem either way.

📊 What the Numbers Say: quote the model with the number.

"38.6 QPU-days" is a real figure from a stated cost model, and it is the right order to plan against. It is not a measurement of a QPU, and this chapter never ran one. Reporting it without the model is how a modelling assumption becomes a fact, which is the failure §34.6 already documented once in this chapter from the other direction.

The defensible form is the bracket: the Gram matrix at ten qubits costs between 0.72 QPU-hours and 38.6 QPU-days on 201 samples, depending on how tightly each entry must be resolved — and it grows as $n^2 \times 4^n$ or $n^2 \times 2^n$ from there.

And inference has the same shape as Chapter 33's

Case Study 2 notes that inference adds $m \times n$ evaluations. The arithmetic is worth doing, because it turns out to dominate everything above.

A trained SVM predicts by evaluating the kernel against every support vector. This chapter's models used 91 to 144 of them. For a million predictions:

   91 support vectors x 1,000,000 predictions = 9.10e7 kernel evaluations

     at 2 qubits  (K = 0.25346,       15 shots each):  1.365e09 shots =        38 QPU-hours
     at 10 qubits (K = 0.00078, 1.64e6 shots each):    1.496e14 shots = 4,154,795 QPU-hours

Thirty-eight QPU-hours at two qubits — and 474 QPU-years at ten. Chapter 33 §33.6 measured its variational classifier at 27.8 QPU-hours per million predictions, and the two-qubit kernel lands in the same place, which is the third time in two chapters that two structurally different quantum models have produced the same number.

Note what the kernel method adds that Chapter 33's did not have: the inference cost scales with the support vector count, which grows with the training set. §34.6 measured support vectors rising from 91 to 144 as qubits went from 2 to 12 — a 58% increase in the per-prediction bill, bought with the accuracy improvement in the same table. The thing that made the model better made every future prediction more expensive, and that trade has no analogue in the variational case.

Against SVC(kernel='rbf').predict on a million points, which is a matrix multiply.

🗝️ Version Note — the API around all of this moved, and one piece of it is gone.

Verified against the versions this chapter was built on: PennyLane 0.45.1, Qiskit 2.5.1.

ZZFeatureMap is deprecated. Qiskit 2.5.1 emits:

text DeprecationWarning: The class ``qiskit.circuit.library.data_preparation._zz_feature_map.ZZFeatureMap`` is deprecated as of Qiskit 2.1. It will be removed in Qiskit 3.0. Use the zz_feature_map function as a replacement. Note that this will no longer return a BlueprintCircuit, but just a plain QuantumCircuit.

The replacement is the lower-case function. The tail of that message is the part that breaks code: BlueprintCircuit supported rebinding its parameters after construction, and a plain QuantumCircuit does not. A kernel loop that built one feature map and reassigned its parameters per data point has to be rewritten to build a circuit per point — or, better, to use assign_parameters with the batch.

qml.adjoint cannot invert a noise channel, which is how the Noise Report above got written. Adding a DepolarizingChannel inside the feature map and calling qml.adjoint(feature_map)(x2) fails at execution, not at construction:

text pennylane.exceptions.DeviceError: Operator Adjoint(DepolarizingChannel(0.0001, wires=[1])) not supported with default.mixed and does not provide a decomposition.

This is correct behaviour — a channel is not unitary and has no adjoint — but it means the elegant one-line kernel circuit does not survive contact with a noise model. The uncompute half has to be written out by hand: reverse the gate order, negate every angle, and re-insert the channels forward. The kernel is still the same kernel; the abstraction is what fails.

34.8 What the kernel argument establishes

The honest summary, because this chapter's results point in genuinely different directions.

The mathematics is clean and the structural advantage is real. A convex training problem with no initialization, no learning rate, and no barren plateaus is strictly better than a non-convex one, and the quantum circuit's role — computing a fixed similarity function — is much easier to reason about than an optimization landscape.

There is a proven separation. Liu, Arunachalam and Temme (2021) construct a learning problem, based on discrete-log structure, where a quantum kernel provably beats any classical learner under standard assumptions. The kernel route is where QML's rigorous results live, and that is not an accident: the fixed feature map makes the analysis tractable.

On this data it loses to a classical kernel by seven standard errors, using the same solver, with the only difference being the kernel function.

And the costs are quadratic in the dataset and exponential in the concentration. 38.6 QPU-days for a Gram matrix at ten qubits, against SVC(kernel='rbf').fit in 1.3 milliseconds.

The strongest honest case: quantum kernels are where the rigorous separations are, and where the optimization problems are not. They are also where the $n^2$ is, and where the feature map is doing all the work.

Where this sits between Chapter 32's input problem and Chapter 35's dequantization

Part VI's four chapters are usually read as four techniques. They are better read as four placements of the same boundary, and this chapter's result is what it is because of where it put it.

   Ch. 32/33   the quantum circuit EVOLVES and is OPTIMIZED
               -> barren plateaus, initialization, learning rate
               -> cost: shots x samples x steps, LINEAR in the data

   Ch. 34      the quantum circuit only EVALUATES a fixed function
               -> no plateaus, no initialization, convex training
               -> cost: shots x n^2, QUADRATIC in the data

   Ch. 35      the quantum system SUPPLIES the data as well
               -> no encoding cost at all
               -> cost: constrained to data that is quantum by nature

Moving the boundary never removed a cost; it exchanged one for another, and this chapter's exchange was the cleanest to state and the least favourable to evaluate.

Two connections are worth making explicit because they decide how much of this chapter survives.

Chapter 32's input problem is still here, and the kernel formulation makes it worse. §32.2 measured amplitude encoding at $N - \log_2 N - 1$ two-qubit gates, charged per sample, per epoch. A kernel evaluation runs the feature map twice — $U(x')$ then $U^\dagger(x)$ — so it pays the encoding cost twice per entry, and there are $n(n+1)/2$ entries. §34.1's transpiler note is the one piece of relief available, and only for diagonal maps: the algebra permits merging the two encodings into one, which halves the cost the input problem imposes. That is a genuine and narrow win, and the transpiler does not currently take it.

And the dequantization question applies to this chapter's kernel directly. §34.1 argued that the ZZ feature map is an IQP circuit chosen to be classically hard to sample, while a kernel evaluation asks only for one probability. Chapter 35 §35.4 turns that gap into a measurement: a quantum state on 6 qubits is 128 real numbers, and SVC(rbf) reads them for free — scoring 0.7857 against the quantum classifier's 0.6429 on states the quantum model had direct access to.

The same argument reaches this chapter without modification. At two qubits, the feature space is 16 real dimensions and this chapter's Gram matrix had rank 13. There is no plausible sense in which a 13-dimensional similarity structure is beyond classical reach; sklearn computed a better one in microseconds. The quantum kernel's case begins only where $4^n$ is too large to write down — which is exactly the regime where §34.6's concentration puts the entries on the Haar floor and §34.7's shot budget puts the Gram matrix in QPU-days.

🔬 Honest Assessment: the two conditions for a quantum kernel to matter are in tension with each other.

For the kernel to be beyond classical simulation, the feature map must spread states across a space too large to enumerate. For the kernel to be informative, the states must remain distinguishable.

§34.6 measured that these are the same knob. Spreading the states put the off-diagonal entries on $1/2^n$; keeping them distinguishable required not spreading them, which is precisely what the redundant encoding did and why its kernel sat 23× above the floor.

This is not a proof that no feature map threads the needle — Liu, Arunachalam and Temme's construction is an existence proof that one can, on a purpose-built problem. It is a statement that threading it is the design problem, and that no amount of hardware improvement addresses it, because both effects are properties of the map rather than of the device.

Chapter 35 is where the tension resolves, and it resolves by removing one side of it: if the data was never classical, there is nothing to spread and nothing to compress, and the only question left is whether you can measure the state efficiently.

Chapter 35 closes Part VI on the case that changes the arithmetic entirely — when the data is already quantum, and there is no classical alternative to lose to.

What we measured

• $K(x,x) = 1.000000$ exactly and the Gram matrix is symmetric — both one line to check.
• Batching the Gram matrix: 40,401 entries in 0.11 s against 51.3 s looping — ~500× faster (478× and 868× on repeat runs).
• ★ Training is convex: SVC(kernel='precomputed').fit in ~2 ms, no initialization, no learning rate, no plateaus. Every trainability problem in Part VI disappears.
• ★ Feature-map tuning moved accuracy from 0.6364 to 0.8500 — a larger swing than any method-to-method difference in this chapter.
• ★★ Across ten splits: quantum kernel $0.8313 \pm 0.0381$; SVC(rbf) beats it by $+0.0576 \pm 0.0083$ (significant), kNN by $+0.0657 \pm 0.0137$, and it ties with LogReg.
• It is statistically indistinguishable from Chapter 33's variational model ($0.8343 \pm 0.0407$) — two structurally different approaches landing in the same place.
• ★★★ Kernel concentration: a several-hundred-fold collapse over eight qubits with independent features (286× and 327× on repeat draws), against ~11× with redundant ones. Concentration is driven by feature dimension, not qubit count.
• ★ A claim I withdrew: I predicted concentration would cause memorization and chance-level generalization. On this data test accuracy rose from 0.7778 to 0.8889 across 2–12 qubits. Right mechanism, wrong regime.
• ★★ The Gram bill: $n(n+1)/2$ entries at $\mathcal{O}(1/K^2)$ shots each. At ten qubits, 3.34e10 shots = 38.6 QPU-days for the matrix alone, on 201 samples.
• ★★ The 201×201 Gram matrix has rank 13 at two qubits, bounded by $4^n = 16$, and does not reach full rank until six. Over four-fifths of the accuracy gain in the qubit sweep (+0.0909 of +0.1111) happens while the matrix is still rank-deficient — a mechanism for §34.6's surprise more specific than "the extra depth helps."
• ★ The measured concentration sits on the Haar floor $1/2^n$, within 10% at every qubit count across two independent runs. The spread runs 1.1–1.9× above it, which is the residual structure the kernel classifies with.
• The compute-uncompute circuit is algebraically one diagonal block, and the transpiler does not find it: 34 CX at ten qubits where 18 reproduce the kernel to $2.8\times10^{-17}$. Levels 1, 2 and 3 are identical.
• Depolarizing noise breaks the unit diagonal before anything else — $K(x,x) = 0.99800$ at a gate error of $10^{-4}$ — and drags the off-diagonal toward $1/2^n$, so noise and concentration leave the same signature. Rescaling by the measured diagonal is 20× further from the truth than doing nothing.

The theme: removing the optimization problem does not remove the shot budget — and a failure mode's mechanism can be right while your judgement about whether it applies is wrong.