Case Study 2: The Quadratic Nobody Costed
The pitch, which is a good one
A team has been following Part VI closely and has drawn the right conclusion from Chapter 33: the variational classifier's problems are optimization problems. Non-convex landscape, random initialization, learning rate, barren plateaus, and no guarantee that sixty Adam steps finds what the circuit can represent.
So they switch to kernels, and the argument is excellent:
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
Every trainability problem Part VI has measured disappears. The quantum circuit computes a fixed similarity function; the learning is a convex quadratic program that a classical solver handles exactly, in about two milliseconds.
This is not hype. It is the strongest structural claim in Part VI, and this chapter endorses it.
The proposal costs the change carefully. Chapter 32's training budget no longer applies — there is no $(2p+1)$ parameter-shift factor, no optimizer steps, no epochs. The variational training cost goes to zero. They present that as the headline saving.
The cost that replaced it
Training an SVM needs the kernel between every pair of training points.
n = 201 training points
-> n(n+1)/2 = 20,301 unique kernel entries
-> each one is a circuit execution
And each entry is a probability, estimated from shots. Chapter 24 §24.3's wall applies: resolving a probability of size $K$ to relative precision needs $\mathcal{O}(1/K^2)$ shots.
So the kernel's concentration multiplies into the Gram matrix's size, exactly as barren plateaus multiplied into Chapter 32's training budget:
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.
And note what it is buying: a kernel whose off-diagonal entries average 0.00078. Nearly two QPU-months to resolve numbers that are almost identical to each other, in a matrix that is approaching the identity.
🔬 Honest Assessment: convexity removed the optimization. It did not remove the shots, and it introduced a quadratic.
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$, with the constant set by concentration. For the same 201 samples that is a different shape of bill, not a smaller one.
And the quadratic is the other half
The concentration factor is what makes ten qubits expensive. The $n^2$ is what makes any real dataset expensive, regardless of concentration:
training set unique entries vs n=201
201 20,301 1x
2,010 2,021,055 100x
20,100 202,015,050 9,951x
Ten times the data is a hundred times the kernel evaluations. A dataset of twenty thousand samples — modest by any classical standard — needs two hundred million circuit executions to build its Gram matrix, before shots are counted.
And inference adds $m \times n$ more, which is Chapter 33 §33.6's recurring bill in a new form: every prediction requires the kernel against every support vector, and this chapter's SVM used 91–152 of them.
What the proposal should have contained
1. THE TRAINING COST THAT WENT AWAY. Real, and worth stating. [they had this]
2. THE GRAM COST THAT REPLACED IT. n(n+1)/2 entries. [missing]
3. THE SHOTS PER ENTRY, from the MEASURED concentration. [missing]
4. THE SCALING. n^2, evaluated at the dataset size they
actually have, not the 201 in the demo. [missing]
5. INFERENCE. m x (support vectors) kernel evaluations,
recurring -- Chapter 33 Sec 33.6's lesson, unchanged. [missing]
Items 2 through 4 are three lines of arithmetic, and together they reverse the conclusion.
The project module makes the omission hard:
def gram_shot_budget(n_train, mean_kernel_value, n_test=0):
"""Shots to build a Gram matrix, given how concentrated the kernel is.
CONCENTRATION AND THE SHOT BUDGET MULTIPLY -- exactly the structure of
Chapter 32 Sec 32.5's barren-plateau product.
"""
mean_kernel_value has no default. You cannot get a budget without supplying the measured
concentration, which forces you to have measured it.
What the method is still good for
The convexity advantage is real and this chapter does not retract it.
Small $n$. The quadratic is only ruinous when $n$ is large. For a few hundred samples with a well-conditioned feature map, the Gram matrix is cheap — 0.03 QPU-days at six qubits — and you get an exactly-solved training problem for it.
Where the rigorous separations live. Liu, Arunachalam and Temme's proven quantum advantage is a kernel result, and that is not an accident: a fixed feature map is analytically tractable in a way a variational landscape is not. If a rigorous QML advantage is demonstrated, current evidence suggests it will be here.
And where the data is already quantum. Chapter 35's subject. If the input is a quantum state, the kernel is an overlap between states you already have — no encoding, and the $n^2$ buys something with no classical equivalent.
The lessons
A cost that goes away is not a saving until you cost what replaced it. The variational training budget genuinely vanished. The Gram matrix genuinely arrived.
Check the scaling exponent, not just the constant. Linear-in-$n$ became quadratic-in-$n$, and at demo size (201) that is invisible while at production size it is decisive.
Measure concentration before budgeting. The shots-per-entry term spans five orders of magnitude across the qubit range in this chapter, and it is measurable in one line.
And notice the shape. Chapter 25's team read an improvement factor when the decision needed a breakeven. Chapter 33's team costed training and not inference. Here the cost simply changed form, and the new form was not looked for because the old one had been eliminated.
Reproduce it: code/example-03-the-gram-bill.py runs the ten-split comparison and then prices the
Gram matrix across the measured concentration range; gram_shot_budget and gram_entries in
code/vqelab/kernels.py require the measured concentration, and
test_concentration_and_the_shot_budget_MULTIPLY and test_the_bill_is_quadratic_in_the_dataset
assert both halves.