Case Study 37.2: The Benchmark That Reversed
The situation
A research group is preparing a paper. Their result, from three months of work:
QAOA at $p=4$ underperforms $p=3$ on random 3-regular MaxCut, suggesting that the optimization landscape degrades faster than added expressivity compensates. We attribute this to the onset of barren-plateau behaviour at modest depth.
They have the measurements. The effect appears on two of the three graphs they tested. The explanation is plausible, cites real literature, and would be an interesting negative result — the kind of finding this book has repeatedly said the field needs more of.
A reviewer asks one question: how many random initializations per depth?
The answer is one.
Why the reviewer asked
Not because the result was surprising. Because it was structurally impossible.
QAOA at $p=4$ contains QAOA at $p=3$. The ansatz is
$$|\gamma,\beta\rangle = \prod_{i=1}^{p} e^{-i\beta_i H_M} e^{-i\gamma_i H_C}|+\rangle^{\otimes n}$$
Set $\gamma_4 = \beta_4 = 0$ and the fourth layer becomes the identity, recovering the $p=3$ circuit exactly. So the $p=4$ optimum is at least as good as the $p=3$ optimum, always, on every graph, as a matter of the parameterization rather than of physics.
Therefore any measured $p=4 < p=3$ is a statement about the optimizer, not about the ansatz. That does not make it uninteresting — "the optimizer cannot find the solution it provably contains" is a real and important finding, and it is close to what barren plateaus are. But it is a different claim from the one the abstract makes, and it requires different evidence.
Step 2: the re-run
Eight random initializations per depth, same graph, same optimizer, same 100 steps:
p mean std min max per-seed ratios
1 0.751 0.000 0.751 0.751 0.751 0.751 0.751 0.751 0.751 0.751 0.751 0.751
2 0.812 0.008 0.802 0.821 0.814 0.814 0.821 0.819 0.802 0.802 0.802 0.821
3 0.852 0.016 0.818 0.877 0.858 0.858 0.854 0.818 0.836 0.877 0.857 0.857
4 0.873 0.021 0.834 0.897 0.878 0.834 0.864 0.894 0.850 0.884 0.897 0.885
5 0.907 0.014 0.884 0.926 0.916 0.920 0.910 0.884 0.889 0.898 0.926 0.915
$p=4$ beat $p=3$ in 7 of 8 seeds. The means rise monotonically. The effect is gone.
Look at what the single-seed protocol was sampling from. The $p=3$ range is 0.818–0.877 and the $p=4$ range is 0.834–0.897 — they overlap across almost their entire width. Draw one from each and you have a substantial chance of the second being lower. The group drew badly, twice, and stopped.
Step 3: what survived, and it is not nothing
The re-run does not vindicate QAOA and does not erase three months of work. Read the std column:
p std parameters
1 0.000 2
2 0.008 4
3 0.016 6
4 0.021 8
At $p=1$, all eight initializations converge to exactly the same ratio. Two parameters, one basin, no dependence on where you start. The variance then grows with depth — which is the mechanism the group's abstract described, showing up cleanly and measurably.
So the group had found something real. They had attached it to the wrong observable. The defensible paper is:
Solution quality becomes increasingly initialization-dependent with QAOA depth, with the standard deviation across random starts rising from 0.000 at $p=1$ to 0.021 at $p=4$ on random 3-regular MaxCut, while mean performance continues to improve monotonically. Practitioners reporting single-run QAOA results at $p \geq 3$ should expect run-to-run variation comparable to the improvement from an additional layer.
That last sentence is a genuinely useful warning, it follows from the data, and it is more actionable than the original claim.
Step 4: the protocol change
The group adds a rule, and vqelab.combinatorial enforces it:
>>> from vqelab.combinatorial import compare_solvers
>>> compare_solvers([0.858], [0.834])
'INSUFFICIENT_SEEDS'
>>> p3 = [0.858, 0.858, 0.854, 0.818, 0.836, 0.877, 0.857, 0.857]
>>> p4 = [0.878, 0.834, 0.864, 0.894, 0.850, 0.884, 0.897, 0.885]
>>> compare_solvers(p4, p3)
'QUANTUM'
MIN_SEEDS = 8 is not a statistically derived constant and the module does not pretend otherwise. It
is a floor low enough to be affordable and high enough that a single unlucky draw cannot carry a claim.
The refusal is the feature: INSUFFICIENT_SEEDS is a different answer from "no difference," and
conflating them is how the original result happened.
What this case study is about
This is the book's own error. §37.3's table was drafted from single-seed runs and showed exactly the regression described above; the eight-seed re-run is what corrected it. It is the fourth time:
| Chapter | The claim from too few samples | What it was |
|---|---|---|
| 27 | 1.0% false-failure rate, from 2 of 200 | 0.150% at 2,000 runs |
| 28 | Optimization levels 2 and 3 are identical, from 2 circuits | Differ in 14 of 40 |
| 33 | Classifier accuracy, from one train/test split | A distribution across splits |
| 34 | Concentration will cause memorization, from one draw | Test accuracy rose |
| 37 | $p=4$ is worse than $p=3$, from one seed | $p=4$ wins 7 of 8 |
The pattern is not carelessness. In every case the single sample was the cheap measurement, the result was plausible, and there was a story ready to explain it. Plausibility plus a story is what makes a bad measurement survive — a surprising result gets checked, and a result that confirms what you expected does not.
What broke the pattern here was a structural argument, not suspicion. $p=4 \supseteq p=3$ is a fact about the parameterization, available before any measurement, and it converts "this seems off" into "this specific number must be wrong or must mean something else." That is a much stronger position to re-measure from.
The general habit: before reporting that more resources made something worse, check whether the larger configuration contains the smaller one. If it does, you are measuring your optimizer.
Questions
- The group's original explanation — barren plateaus — is not crazy. At what depth and system size would you expect it to actually bite, and what measurement would distinguish it from an unlucky initialization?
MIN_SEEDS = 8is admitted to be arbitrary. Derive a defensible number from the measured standard deviations above and a stated effect size you want to detect.- The rewritten claim says variation is "comparable to the improvement from an additional layer." Check that against the table. Is it true at every $p$?
- $p=1$ has std exactly 0.000 across eight random starts. Explain that, and predict whether it survives at $n=20$.
- The hard one.
compare_solversreturnsTIEwhen the means are within $2\sigma/\sqrt{n}$. Apply it to the $p=3$ vs $p=4$ data above and check whether the answer it gives is the one this case study argues for. If they disagree, which is right?