Key Takeaways: Quantum Optimization with QAOA
The scorecard
Ten random 3-regular graphs. One seed each, one sample each. QAOA won 0, Goemans–Williamson won 6, four ties.
GW's single randomized rounding hit the exact optimum on 8 of 10 instances, in 5.9 milliseconds against QAOA's 5.2 seconds — 875×, and QAOA's time was on an exact simulator where expectation values are free.
This is the cleanest comparison in the book, because unlike Chapter 36 there is no modelling error in the way. The Ising mapping is exact. Everything measured is a property of the algorithm.
What the chapter measured
| Claim | Measured |
|---|---|
| Random assignment | 0.5 of the edges = 0.577 of the optimum — same cut, two ratios |
| GW guarantee | 0.87856 of the optimum, proven, polynomial time, every graph |
| QAOA mean ratio, $p=1 \to 5$ | 0.751 → 0.812 → 0.852 → 0.873 → 0.907 |
| Landscape variance, $p=1 \to 4$ | std 0.000 → 0.021 |
| $P(\text{optimal})$, $p=1 \to 5$ | 0.020 → 0.388, against 0.0005 uniform — 795× |
| Head-to-head, 10 instances | QAOA 0, GW 6, ties 4 |
| GW exact-optimum hit rate | 8/10 from one rounding |
| Wall clock | GW 5.9 ms, QAOA 5.2 s — 875× |
| SDP certificate | cut 13, bound 13.0326 — certified 0.9975 without knowing OPT |
| Shot budget, $p=3$, $\epsilon=0.01$ | 13,000,000 shots = 22 minutes of device time |
The six things to carry forward
1. QAOA is doing real work, and that has to be said first. At $p=5$ it concentrates 39% of its probability on 2 optimal states out of 4,096 — a factor of 795 over the uniform superposition it started from. The means rise monotonically with $p$. This is not a failed algorithm; it is an algorithm that works and loses anyway.
2. $p=1$ scores 0.751, below a proof from 1994. It takes $p=5$ to clear 0.87856 on this instance — in expectation, on a simulator, with no shot noise and no hardware error. Any MaxCut result below 0.878 is beaten by Goemans–Williamson, not usually but always.
3. Say what the denominator is. Random assignment is 0.5 of the edges and 0.577 of the optimum, from the same assignment on the same graph. "QAOA achieves 0.9" means nothing until you say 0.9 of what, and the two denominators get swapped constantly.
4. The state is not the answer. QAOA's mean $E[\text{cut}]/\text{OPT}$ was 0.891 — above the guarantee — while its single samples returned 9 and 11 against an optimum of 13. A distribution with a good mean still returns bad individual answers, and an optimization user receives an answer, not a mean. Chapter 30 §30.5 refused to let a fidelity be quoted without its statistic; this is that refusal with a graph attached.
5. ★★ GW returns a certificate and QAOA does not. The SDP produces an upper bound on the optimum, so GW proves its own answer is within 0.9975 of optimal without brute force and without being told the optimum. QAOA returns a bitstring. Nothing in a QAOA output distinguishes instance 9's cut of 9 from instance 5's optimal 13. To find out you must run something else — and if the something else is GW, you have already solved the problem.
This is not a performance gap. It is a difference in what the two algorithms produce, and it does not close when devices improve. A faster QAOA is a faster uncertified answer.
6. The simulator was hiding the shot budget. 13 million shots — 22 minutes of exclusive device time — at $p=3$ and $\epsilon = 0.01$, for a 12-node graph GW solved in 8 milliseconds. And that is the optimistic term: it assumes 100 iterations suffice, that simulator angles transfer to hardware, and that noise does not flatten the landscape below the resolution the shots buy.
The error this chapter made, and why it is the fourth
The first version of §37.3's table used one seed per $p$ and showed $p=4$ scoring worse than $p=3$. At 8 seeds, $p=4$ beat $p=3$ in 7 of 8.
- Chapter 27 reported 1.0% from 2 runs in 200 — it was 0.150% at 2,000
- Chapter 28 called optimization levels 2 and 3 identical from two circuits — they differ in 14 of 40
- Chapter 33 read a classifier's accuracy off one train/test split
- Chapter 34 predicted from one draw and measured the opposite
A result from one or two samples is a draw from a distribution. It keeps happening because the single sample is cheap and the distribution costs eight times as much.
What made this one catchable: $p=4$ contains $p=3$. Set the two extra angles to zero and you recover it exactly, so a strictly more expressive ansatz scoring worse is structurally impossible at the optimum. The theory said which measurement deserved a second look — which is a better error detector than suspicion, because it is specific.
And the part that survived: the variance is real and grows with $p$, from exactly 0.000 at $p=1$ to 0.021 at $p=4$. The landscape does get harder. What was wrong was reading a particular regression out of a single draw.
What went into vqelab
vqelab.combinatorial, 26 tests passing:
OptimizationResultcarries the expected ratio and the sampled answer;reportable_ratio()refuses to return one number.ratio_denominator()raises without an explicit"edges"or"optimum".compare_solvers()returnsINSUFFICIENT_SEEDSbelowMIN_SEEDS = 8— this chapter's own error, made unrepeatable.CertifiedResultvsUncertifiedResult. The latter'scertified_ratioisNone, not 1.0, because returning a number there would be a lie.qaoa_shot_budget()prices what exact simulation was hiding.
Next: Chapter 38 — the one application in this book that is deployed, commercially available, and works. And whose hard problems turn out to live somewhere the physics does not reach.