Case Study 2: The Optimizer That Lost to 1995

The pitch

A logistics team has a hard combinatorial problem — a graph partitioning task that reduces to MaxCut. Their current solver is slow on large instances, and QAOA is described everywhere as the near-term quantum optimization algorithm.

They build a prototype. It works:

     p    approximation ratio
     1                 0.8086
     2                 0.9636
     3                 0.9979

At $p = 3$, QAOA essentially solves the instance — the optimum appears in 99.5% of sampled shots. The result is real and the implementation is correct.

They plan to scale it up.

The question nobody asked

What does the best classical algorithm get?

Goemans–Williamson, published in 1995, is a polynomial-time classical algorithm for MaxCut based on semidefinite programming, with a proven approximation guarantee:

$$\text{ratio} \;\geq\; 0.87856 \quad\text{for \textbf{any} graph}$$

Set that beside the QAOA results:

     p    QAOA ratio    vs Goemans-Williamson
     1        0.8086    BELOW the classical guarantee
     2        0.9636    above
     3        0.9979    above
     4        0.9998    above

At depth 1, QAOA loses to a thirty-year-old classical algorithm.

Why depth 1 is the number that matters

Not because deeper QAOA is uninteresting, but because depth is what hardware cannot supply.

Each QAOA layer applies the full cost Hamiltonian — one two-qubit interaction per edge. So a $p$-layer circuit on a graph with $|E|$ edges has $\mathcal{O}(p|E|)$ two-qubit gates, before routing.

Their real instances have hundreds of edges. At $p = 3$ that is on the order of a thousand two-qubit gates, and Part II measured what that costs:

Chapter 12 — a 288× spread in two-qubit gate error across one chip, median around 0.0078. Surviving 1,000 two-qubit gates at that error rate is $(1-0.0078)^{1000} \approx 4 \times 10^{-4}$.

Chapter 17 — up to 3.18× routing overhead when the interaction graph is not local, and a logistics graph is emphatically not a line.

Chapter 16 — the gradient costs $2n+1$ evaluations per iteration, and $p=3$ on a large graph means more parameters and a flatter landscape.

So the achievable depth on current hardware is 1, possibly 2 — and $p = 1$ is where the classical algorithm wins outright.

The two claims, and why only one is strong

In QAOA's favour, and this should be said clearly: the ratios above are for one small instance, where QAOA at $p \geq 2$ comfortably beats 0.8785. Goemans–Williamson's guarantee is worst-case; on easy instances it also does better than 0.8785. So the comparison at $p \geq 2$ is not apples-to-apples in QAOA's disfavour.

Against QAOA, and this is the decisive part: QAOA has no guarantee at all.

$$\text{Goemans–Williamson: } \forall G,\; \text{ratio} \geq 0.87856 \qquad \text{QAOA: } \text{no such theorem}$$

There is no result stating that QAOA at depth $p$ achieves ratio $f(p)$ on arbitrary graphs, and there are known instance families where low-depth QAOA performs poorly.

A proven worst-case bound and a good average-case result are different kinds of claim.

The classical algorithm has the stronger kind. That does not make QAOA useless — heuristics without guarantees routinely beat guaranteed algorithms in practice, and simplex is the canonical example. But "we measured a good ratio on our instance" is not comparable to "this is provably within 12.2% of optimal on every instance", and a proposal that presents them as comparable has made an error of kind, not of degree.

What a fair evaluation looks like

Not "does QAOA work?" — it does. "Does QAOA beat what we would otherwise run, on our instances, at a depth our hardware can execute?" Three conditions, all load-bearing.

   1. Implement Goemans-Williamson. It is an SDP; solvers are mature.
      Measure its ratio on YOUR instances, not its worst-case bound.

   2. Measure QAOA at the depth your hardware can actually run,
      including routing overhead for YOUR interaction graph.

   3. Compare. And include the wall-clock cost of the variational loop:
      (2n+1) evaluations per gradient, times iterations, times shots.

Step 1 is the one that gets skipped, and it is the cheapest. The team had never run the classical baseline on their own instances — they had compared QAOA against their current slow solver, which was neither Goemans–Williamson nor anything close to state of the art.

That is the same error as Chapter 21 §21.7's database search: comparing a quantum algorithm against a weak classical strawman rather than against the best available classical method.

What QAOA is genuinely for

The honest positive case, which the team's proposal could have made instead:

It is a well-motivated heuristic with a problem-informed ansatz. Unlike Chapter 16's hardware-efficient ansätze, QAOA's structure comes from the problem — the cost layer is built from the graph — which is exactly the defence against barren plateaus that Chapter 16 §16.6 identified.

Its quality improves monotonically with depth, and at $p \to \infty$ it provably reaches the optimum (it becomes adiabatic evolution). That is a real theoretical foundation, even though the finite-$p$ guarantee is missing.

And it is the shape of program current hardware can run at all, which is not nothing.

What it is not is a demonstrated improvement over classical optimization on any instance anyone cares about, at any depth currently executable.

The lessons

Benchmark against the best classical algorithm, not your current one. The team's baseline was their existing solver. The relevant baseline was a thirty-year-old algorithm with a proven bound, and it takes an afternoon to run.

A guarantee and a measurement are different kinds of claim. "Provably within 12.2% on every graph" cannot be compared directly with "0.9979 on the instance we tried." Only one of them tells you what happens on the next instance.

Depth is the binding constraint, and $p = 1$ is where the hardware is. Quality that arrives at $p = 3$ is quality you cannot currently buy — and $p = 1$ is precisely where the comparison goes against you.

Ask "at what depth can we actually run this?" before "how good is it at depth $p$?" Chapter 12's error rates and Chapter 17's routing overhead answer the first question, and they answer it before any QAOA code is written.

And the honest positive case is available and stronger than the overclaim. QAOA is a problem-informed ansatz with a sound asymptotic foundation, runnable on current hardware. That is a defensible reason to study it. "It solves our optimization problem better than classical methods" is not, and asserting it invites exactly the comparison that defeats it.

Reproduce it: code/example-03-qaoa-maxcut.py measures the ratios and prints the Goemans–Williamson comparison; QAOAResult.beats_goemans_williamson in code/project-checkpoint.py makes the comparison non-optional.