Chapter 37: Quantum Optimization with QAOA

Chemistry had the best claim to being natural. Optimization has the best claim to being valuable — routing, scheduling, portfolio selection, and circuit layout are the problems companies actually pay to solve, and the Quantum Approximate Optimization Algorithm is the near-term proposal for solving them.

It is also the application where the classical baseline is strongest, and — unlike chemistry — the baseline publishes its benchmarks. Combinatorial optimization has fifty years of engineering behind it, standard instance libraries, and competitions. There is nowhere to hide.

This chapter measures QAOA against that baseline on MaxCut, the standard benchmark, and the result is the cleanest scorecard in the book:

Across ten random 3-regular graphs, QAOA won 0, Goemans–Williamson won 6, and 4 were 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.

And then a finding that is worse for QAOA than losing: GW returns a certificate and QAOA does not.

37.1 MaxCut, and why it is the benchmark

Given a graph, split the vertices into two sets so that the number of edges between the sets is as large as possible.

MaxCut is NP-hard, it is the standard QAOA benchmark, and it has three properties that make it the right thing to measure:

• The optimum is computable by brute force at the sizes a simulator reaches, so the approximation ratio is exact rather than estimated.
• The trivial baseline is known. A uniformly random assignment cuts each edge with probability $\tfrac{1}{2}$, so it achieves half the edges in expectation, with no algorithm at all.
• The good baseline is known, and is provably good. Goemans–Williamson achieves at least 0.87856 of the optimum, guaranteed, in polynomial time.

That middle number is the one to hold onto. Any MaxCut result below 0.878 is beaten by a classical algorithm from 1994 — not on average, not usually, but with a proof.

🗝️ A note on the date. Goemans and Williamson presented this at STOC in 1994 and published the full analysis in JACM in 1995. This chapter says "1994" because that is when the result existed; Chapter 24 §24.5 and both chapters' reading lists cite the 1995 journal paper, which is the one to read. The two dates are the same result, and neither is a typo.

37.1.1 Two denominators, one assignment

The ten instances §37.6 uses are random 3-regular graphs on 10 vertices, and they are identical in the two numbers that set the scale: every one has $|E| = 15$ and $\text{OPT} = 13$. That makes the denominator problem concrete rather than pedantic.

A uniformly random assignment cuts each edge with probability $\tfrac12$ independently of the graph — linearity of expectation, no approximation anywhere — so its expected cut is exactly $|E|/2 = 7.5$. Now divide:

   expected cut of a random assignment          7.500
     as a fraction of the EDGES     7.5 / 15  = 0.5000
     as a fraction of the OPTIMUM   7.5 / 13  = 0.5769

Same assignment, same graph, same run, two numbers 15% apart. The larger one is the flattering one, which is why ratio_denominator() in vqelab.combinatorial raises AmbiguousRatioError rather than picking a default. "QAOA achieves 0.9" is not a claim until you say 0.9 of what.

The guarantee needs the same care in the other direction. $0.87856 \times 13 = 11.42$, so on these instances any cut of 12 or more clears the 1994 bound. Enumerating all $2^{10} = 1{,}024$ assignments, between 0.98% and 2.34% of them do — a random bitstring clears the Goemans–Williamson guarantee about one time in fifty. That is not an argument against the guarantee; it is a warning about how to read it. 0.87856 is impressive because it holds for every graph at every size and arrives with the certificate of §37.7, not because 0.878 is a hard number to hit on one small instance.

📐 Math Aside: the gap between $|E|$ and OPT is a statement about odd cycles.

Why is the optimum 13 and not 15? Take any cycle $v_1 v_2 \ldots v_k v_1$ and multiply the edge variables around it:

$$(z_1z_2)(z_2z_3)\cdots(z_kz_1) \;=\; z_1^2 z_2^2 \cdots z_k^2 \;=\; +1$$

Each cut edge contributes $z_uz_v = -1$ and each uncut edge $+1$, so the product is $(-1)^{\#\text{cut}}$. It equals $+1$, therefore the number of cut edges in any cycle is even. A triangle can have at most 2 of its 3 edges cut, a 5-cycle at most 4 of 5, and so on.

Two consequences follow immediately. A graph achieves $\text{cut} = |E|$ exactly when it is bipartite — no odd cycles at all — and otherwise the number of uncut edges is at least the number of edge-disjoint odd cycles you can find in it.

Measured: all ten instances have girth 3 or 4 and between 0 and 3 triangles; none is bipartite. Each gives up exactly 2 of its 15 edges. The 12-node graph of §37.3 has $|E| = 18$, girth 3, three triangles, $\text{OPT} = 16$ — again exactly 2 edges surrendered.

So the denominator gap is structural, not noise. It is also why the ratio to the optimum is the only denominator that compares across graphs: $|E|$ is fixed by the degree, and OPT is not.

37.2 The Ising mapping

MaxCut becomes a Hamiltonian by assigning each vertex a spin $z_i = \pm 1$. An edge $(u,v)$ is cut when $z_u \neq z_v$, so the cut value is

$$C = \sum_{(u,v)\in E} \frac{1 - z_u z_v}{2}$$

Promote each $z_i$ to a Pauli $Z_i$ and the objective is a diagonal Hamiltonian:

$$H_C = \sum_{(u,v)\in E} \frac{1 - Z_u Z_v}{2}$$

This mapping is exact and free — no active space, no basis-set truncation, nothing like Chapter 36's $10^7$ approximation. One qubit per vertex, one two-qubit term per edge. Everything this chapter measures is a property of the algorithm, with no modelling error in the way.

That is why optimization is the cleaner test of the two.

37.2.1 The Hamiltonian, written out

Expand the sum and the structure appears:

$$H_C \;=\; \sum_{(u,v)\in E}\frac{1 - Z_uZ_v}{2} \;=\; \frac{|E|}{2}\,I \;-\; \frac{1}{2}\sum_{(u,v)\in E} Z_uZ_v$$

On the 12-node graph of §37.3 that is $9I - \tfrac12\sum_{18\ \text{edges}} Z_uZ_v$, and the constant is not decoration. In the uniform superposition every $\langle Z_uZ_v\rangle$ vanishes, so $\langle +|^{\otimes n} H_C |+\rangle^{\otimes n} = |E|/2$ exactly. The identity term in the Hamiltonian is the random baseline. Enumerating all 4,096 assignments of that graph confirms it: the mean cut is 9.0000, to the last digit.

Everything QAOA does is therefore an attempt to drive the second term negative. It starts at zero.

Three properties of $H_C$ shape the whole algorithm:

• It is diagonal. Its eigenvectors are the computational basis states and its eigenvalues are the cut values — integers. On the 12-node graph the spectrum runs from 0 to 16, and the degeneracies are brutally lopsided: 766 assignments cut 10 edges, 8 cut 15, and exactly 2 of 4,096 achieve the optimum of 16.
• All its terms commute, because $Z_uZ_v$ and $Z_aZ_b$ are both diagonal. So $e^{-i\gamma H_C}$ factorizes exactly into a product of two-qubit rotations — one per edge, in any order. There is no Trotter error inside a cost layer.
• It does not commute with the mixer. $[Z_uZ_v, X_u] \neq 0$, and that single fact is the entire reason $p$ exists. Layering is what buys back the non-commutativity, and §37.3's Physics callout is the statement of how much you would have to buy.

37.2.2 The symmetry the mapping inherits

Flipping every vertex to the other side exchanges the two sets and cuts precisely the same edges, so $C(x) = C(\bar{x})$ for every bitstring. Checked exhaustively on the 12-node graph: it holds for all 4,096 assignments.

In operator language, $X^{\otimes n} Z_uZ_v X^{\otimes n} = (-Z_u)(-Z_v) = Z_uZ_v$, so $[H_C, X^{\otimes n}] = 0$. The mixer $H_M = \sum_j X_j$ commutes with $X^{\otimes n}$ too, and $|+\rangle^{\otimes n}$ is its $+1$ eigenstate. Every factor in the QAOA product therefore preserves the symmetry:

Every QAOA state is invariant under a global bit flip, at every $p$, for every choice of angles. The output distribution satisfies $P(x) = P(\bar x)$ identically — not approximately, not on average.

Three things follow that are worth having in advance:

1. The number of optimal basis states is always even. Measured: 2 on the 12-node graph, and 2, 4, 2, 6, 6, 6, 2, 2, 4, 8 across the ten instances of §37.6. When §37.3 reports 39% of the probability mass on "the two optimal states," symmetry guarantees it is 19.4% on each. That is not a lucky split.
2. QAOA cannot break the symmetry, so it cannot express a preference between a partition and its complement. If your real problem does distinguish them — a fixed depot, a cardinality constraint, a vertex that must be on side A — that structure has to enter through the mixer or through added cost terms. No choice of angles will do it.
3. The same symmetry halves the classical brute force: fix $z_0 = +1$ and enumerate $2^{n-1}$. This chapter's code does not bother, because at $n = 12$ the full sweep costs milliseconds. At $n = 30$ it would matter, and at $n = 50$ neither version runs.

⚙️ Under the Transpiler: what a cost layer actually costs.

Each edge term is $e^{i\gamma Z_uZ_v/2}$ up to a global phase, and the textbook decomposition is CNOT · $R_z(\gamma)$ · CNOT — two entangling gates and one rotation per edge per layer. The mixer is free of two-qubit cost: the $X_j$ commute, so $e^{-i\beta\sum_j X_j} = \prod_j R_x(2\beta)$.

Qiskit 2.5.1 will price it for you. Building the same cost operator as a SparsePauliOp and handing it to QAOAAnsatz, then decomposing:

text n p |E| parameters cx rz r depth 12 1 18 2 36 18 12 23 12 3 18 6 108 54 36 55 12 5 18 10 180 90 60 87

So §37.9's "$p=5$ on 12 nodes is already 90 two-qubit gates" is counting one $ZZ$ interaction per edge per layer — $18 \times 5$. Qiskit's own decomposition turns those into 180 CNOTs, and that is still before a coupling map is involved.

Routing is the term missing from the table, and it is not small here. A random 3-regular graph has triangles — eight of the ten instances have girth 3 — while IBM's heavy-hex coupling map is triangle-free, so the problem graph cannot embed and SWAPs are mandatory. Chapter 29 measured a hardware-aware level-1 transpilation at 0.9116 fidelity against a naive level-3 at 0.7720 on the same circuit, and Chapter 39 compiled one 14-qubit layout under 24 seeds and got between 49 and 112 two-qubit gates out of identical logical input. The gate count above is a floor, and the spread around it is a factor of two.

37.3 The ansatz, and what $p$ buys

QAOA alternates two layers $p$ times, starting from the uniform superposition:

$$|\gamma,\beta\rangle = \prod_{i=1}^{p} e^{-i\beta_i H_M} e^{-i\gamma_i H_C}\;|+\rangle^{\otimes n}$$

where $H_M = \sum_j X_j$ is the mixer. Two parameters per layer, $2p$ in total — far fewer than any ansatz in Part VI, which is the design's real virtue.

cost_h, mixer_h = qml.qaoa.maxcut(G)

@qml.qnode(dev)
def circuit(params):
    for w in range(n):
        qml.Hadamard(wires=w)
    for i in range(p):
        qml.qaoa.cost_layer(params[0, i], cost_h)
        qml.qaoa.mixer_layer(params[1, i], mixer_h)
    return qml.expval(cost_h)

Measured on a 12-node 3-regular graph, 8 random initializations per $p$, Adam for 100 steps:

     p     mean     std     min     max
     1    0.751   0.000   0.751   0.751
     2    0.812   0.008   0.802   0.821
     3    0.852   0.016   0.818   0.877
     4    0.873   0.021   0.834   0.897
     5    0.907   0.014   0.884   0.926

More layers genuinely help. The mean rises monotonically, and QAOA is doing real work: at $p=5$ it puts 39% of its probability mass on the two optimal states out of 4,096, against 0.05% for the uniform superposition it started from. That is a factor of 795, and it is not an artifact.

⚛️ The Physics Underneath: why $p \to \infty$ must work.

QAOA is a Trotterized adiabatic evolution. As $p \to \infty$ with the right angle schedule, it becomes adiabatic quantum computation and finds the exact optimum. The algorithm is guaranteed correct in a limit nobody can reach, and every practical question is about what happens at the small $p$ a device can actually run.

Compare Chapter 21's Grover: also guaranteed, also asymptotic, and Chapter 21 §21.6 found the same gap between the guarantee and the machine.

📐 Math Aside: the adiabatic schedule is inside the ansatz, and that is what $p \to \infty$ means.

Interpolate between the mixer and the cost Hamiltonian:

$$H(s) \;=\; (1-s)\,H_M \;+\; s\,H_C, \qquad s: 0 \to 1$$

The ground state of $H(0) = H_M$ is $|+\rangle^{\otimes n}$ — exactly QAOA's initial state, not coincidentally. The adiabatic theorem says that evolving slowly enough from there ends in the ground state of $H(1) = H_C$, which is the optimal cut.

Now discretize that evolution into $p$ steps of size $\Delta t = T/p$ at $s_i = i/p$ and Trotterize each one:

$$e^{-iH(s_i)\Delta t} \;\approx\; e^{-i(1-s_i)\Delta t\, H_M}\; e^{-i s_i \Delta t\, H_C}$$

That is a QAOA layer, with $\beta_i = (1-s_i)\Delta t$ and $\gamma_i = s_i\Delta t$. The adiabatic schedule is one particular point in QAOA's $2p$-dimensional parameter space, and an optimizer searching that space freely can only do at least as well as it. The $p\to\infty$ guarantee is not a theorem about QAOA; it is a theorem about adiabatic evolution that QAOA inherits by containment — the same containment argument §37.4 uses one level down to catch a bad measurement.

The price is where it gets uncomfortable. Two errors compete. Adiabatic error falls as $1/(T g_{\min}^2)$, where $g_{\min}$ is the smallest spectral gap along the path, so $T \gtrsim 1/(\epsilon\, g_{\min}^2)$. Trotter error accumulates as $T^2\|[H_M,H_C]\|/p$, so $p \gtrsim T^2\|[H_M,H_C]\|/\epsilon$. Chaining them:

$$p \;\gtrsim\; \frac{\|[H_M,H_C]\|}{\epsilon^3\, g_{\min}^{4}}$$

This is an order-of-magnitude balance, not a theorem, and the constants are not the point. The exponent on $g_{\min}$ is. On the instance families that make MaxCut worth attacking, the minimum gap is expected to close exponentially in $n$ — and then $p$ grows exponentially too. The guarantee is not merely asymptotic; it is asymptotic in the one parameter that blows up precisely where the problem gets hard.

Which is why the measured table matters more than the limit. The increments in the mean ratio are $+0.061$, $+0.040$, $+0.021$, $+0.034$ from $p=1$ to $p=5$. They do not decay monotonically, four points is not a curve, and this chapter is not going to extrapolate them.

37.3.1 Ten parameters, and where they pay off

At $p=5$ on 12 qubits, QAOA has 10 parameters — verified against Qiskit's QAOAAnsatz, which reports num_parameters == 2 * reps regardless of the graph. A hardware-efficient ansatz of the kind Part VI used, one $R_y$ per qubit per layer, would need $12 \times 5 = 60$; with $R_y$ and $R_z$, 120. QAOA's parameter count does not grow with the problem size at fixed depth. Twelve qubits or a hundred, $p=5$ is ten numbers.

That buys two different things, and only one of them is the one usually cited.

The advertised benefit is the landscape. Chapter 32 §32.5 measured gradient variance collapsing from $1.03\times10^{-1}$ at 2 qubits to $1.17\times10^{-3}$ at 10 — a factor of 88 — which is the barren plateau arriving on schedule. A 10-parameter landscape is a much smaller target for that effect than a 120-parameter one, and §37.3's measured standard deviation of exactly 0.000 at $p=1$ is what a two-parameter landscape with a single basin looks like from eight random starts.

The unadvertised benefit is the shot budget, and it is larger. Parameter-shift gradients cost two circuit evaluations per parameter plus one for the energy: $2(2p) + 1$ evaluations per optimizer step. That is the leading factor in §37.8's table, and it is the only factor QAOA's design touches. Run the same protocol on a 60-parameter ansatz and the 13 evaluations per step at $p=3$ become 121:

   ansatz                      parameters   evals/step   shots at eps=0.01   device time
   QAOA p=3                             6           13          13,000,000        22 min
   hardware-efficient, 5 layers        60          121         121,000,000       3.4 hours

QAOA's parameter economy is worth roughly an order of magnitude in device time, and it is still not enough. That is worth saying carefully, because it is the shape of most honest quantum results in this book: the clever thing works, it buys a constant factor, and the constant factor loses to a classical algorithm that was already fast. Chapter 36 §36.7 is the same sentence with a molecule in it.

37.3.2 What 39% of the probability mass buys

The factor of 795 is not a fitted number; it is one division. Brute force over the 12-node graph finds exactly 2 optimal assignments out of 4,096, so the uniform superposition places $2/4096 = 0.000488$ of its probability on the optimum. Against $p=5$'s measured 0.388:

$$\frac{0.388}{2/4096} \;=\; 794.6$$

Turn that into the number a user would actually feel. To see an optimal cut at least once with 99% confidence you need $k$ shots with $1 - (1-P)^k \geq 0.99$, so $k \geq \ln(0.01)/\ln(1-P)$:

   uniform superposition      P = 0.000488   ->   9,430 shots
   QAOA p=1                   P = 0.020      ->     228 shots
   QAOA p=5                   P = 0.388      ->      10 shots

Ten shots. Roughly a millisecond of device time. The concentration is real, it is large, and it does exactly what the algorithm claims.

📊 What the Numbers Say. The 795× is real and it is in the wrong budget line.

Those 10 shots are the readout. The 21,000,000 shots in §37.8 are what it cost to find the angles that make the readout cheap. Concentration saves 9,420 shots and the optimization loop spends 21 million — a ratio of about 2,200 to 1 in the direction nobody quotes.

The expensive part of QAOA is not preparing the answer. It is finding the angles. Which is exactly why §37.9's two live directions — angle transfer and warm-starting — are both attacks on the optimization loop rather than on the circuit, and why both of them begin from something classical.

🔀 In Another Framework: three ways to write the circuit, and no way to get the baseline.

This chapter is written in PennyLane because qml.qaoa ships the whole layer. Qiskit 2.5.1 ships the circuit but not the driver:

```python from qiskit.quantum_info import SparsePauliOp from qiskit.circuit.library import QAOAAnsatz

cost = SparsePauliOp.from_sparse_list( [("ZZ", [u, v], 0.5) for u, v in G.edges()], num_qubits=n) ansatz = QAOAAnsatz(cost_operator=cost, reps=3) # 6 parameters, 10 qubits ```

On the 15-edge instance that decomposes to 90 cx and 45 rz, as §37.2.2's table predicts. The optimizer loop, the estimator calls, and the result object are yours to write.

Cirq 1.7.0 has no QAOA helper at all. You build the layer from cirq.ZZPowGate with sympy symbols and sweep the parameters yourself; one layer on the same graph is 35 operations — 10 Hadamards, 15 $ZZ$ rotations, 10 $R_x$.

And now the part worth noticing. None of the three ships the classical baseline. networkx.algorithms.approximation.maxcut exists and exposes exactly two functions — randomized_partitioning and one_exchange — the 0.5 baseline and a local search. Goemans–Williamson is in none of them; §37.5's version had to be written by hand against cvxpy, a general convex modelling package with no MaxCut in it.

So the tooling makes the quantum algorithm three lines and the strong classical baseline twenty, while the weak classical baseline is one line and already imported. The comparison that is easiest to run is the flattering one. That is Chapter 21 §21.7's lesson arriving through the package manager, and it costs nothing to notice and about an hour to fix.

🗝️ Version Note: where the QAOA machinery lives now.

from qiskit.algorithms import QAOA has not worked since Qiskit 1.0 removed the qiskit.algorithms module. The QAOA class — optimizer plus estimator plus result object — moved to the separate qiskit-algorithms package, which is not installed in this book's environment; what Qiskit core still ships is the circuit, QAOAAnsatz in qiskit.circuit.library, alongside a functional qaoa_ansatz builder. Higher-level problem modelling lives in qiskit-optimization, also separate. If a tutorial imports QAOA from Qiskit directly, it predates 1.0.

One PennyLane detail that costs people ten minutes: qml.qaoa.maxcut(G) on a 15-edge graph returns a cost Hamiltonian with 30 terms, not 15. It emits the $\tfrac12 I$ and the $-\tfrac12 Z_uZ_v$ of §37.2.1 as separate terms per edge. If you print the term count expecting $|E|$, that is why — and the two-qubit gate count is still one per edge, so nothing about the circuit changed.

37.4 The regression that was not there

The first version of the table above used one seed per $p$, and it showed $p=4$ scoring worse than $p=3$ on two of three graphs.

That looked like a finding, and there is a tempting story for it: more layers, harder landscape, the optimizer failing. The story is even partly true — notice that the standard deviation grows with $p$, from exactly 0.000 at $p=1$ to 0.021 at $p=4$. The landscape does get harder.

But the regression itself was not real. Re-run at 8 seeds:

$p=4$ beat $p=3$ in 7 of 8 seeds. The single-seed $p=3$ range (0.818–0.877) overlaps the $p=4$ range (0.834–0.897) almost completely. The original table was a draw from a distribution, and it drew badly.

⚠️ Common Pitfall: this book has now made this mistake four times.

Chapter 27 reported a 1.0% false-failure rate from 2 runs in 200 — it was 0.150% at 2,000. Chapter 28 concluded optimization levels 2 and 3 were 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 a memorization effect from one draw and measured the opposite.

A result from one or two samples is a draw from a distribution. The reason it keeps happening is that the single sample is cheap, and the distribution costs eight times as much to see.

Note what saved it here: $p=4$ contains $p=3$ — set the two extra angles to zero and you recover it exactly. A strictly more expressive ansatz scoring worse is a structural impossibility at the optimum, so the measurement had to be wrong or the optimizer had to be failing. The theory said which measurements deserved a second look.

37.4.1 What a single draw was actually sampling

The summary statistics in §37.3 hide the shape. Here are the eight per-seed ratios behind each row:

     p     per-seed ratios (8 random initializations, same graph, same optimizer)
     1     0.751  0.751  0.751  0.751  0.751  0.751  0.751  0.751
     2     0.814  0.814  0.821  0.819  0.802  0.802  0.802  0.821
     3     0.858  0.858  0.854  0.818  0.836  0.877  0.857  0.857
     4     0.878  0.834  0.864  0.894  0.850  0.884  0.897  0.885
     5     0.916  0.920  0.910  0.884  0.889  0.898  0.926  0.915

Paired seed against seed, $p=4$ beats $p=3$ in 7 of 8. But the original protocol did not pair anything — it drew a fresh random initialization for each $p$ independently, which means the relevant question is what happens when you draw one value from each list at random. There are 64 such ordered pairs, and they can simply be counted:

   pairs where the p=4 draw lands BELOW the p=3 draw      14 / 64  =  0.219
   probability of seeing it at least once in 3 graphs      1 - 0.781^3  =  0.523
   probability of seeing it on 2 or more of 3 graphs                     0.123

A one-seed protocol had a 21.9% chance of showing the regression on any given graph, and was more likely than not to show it at least once across three. The original table saw it on two of three — a 12% event, which is to say a Tuesday.

That is the number worth internalizing. The failure was not a freak coincidence that a careful person would have smelled; it was a routine draw. The mean difference between $p=3$ and $p=4$ is $+0.0214$ and the spread within each is about $0.02$ — a one-sigma effect, which single samples get backwards roughly a fifth of the time by construction.

Notice also which row is not ambiguous: at $p=1$ all eight seeds land on 0.751 and the sample size does not matter at all. The seeds you need scale with the variance, and the variance grows with $p$ — so the protocol that was adequate for the first row was guaranteed to fail somewhere further down it.

🐛 Debug This: eight different seeds, eight identical numbers.

Symptom. At $p=1$, all eight random initializations return 0.751 to three decimals. Standard deviation exactly 0.000.

Your first hypothesis should always be that the seed is not reaching the initialization. The usual culprits are a default_rng(seed) created inside a helper that was called with its default argument, a params array built once outside the loop and reused, or a PennyLane parameter tensor that opt.step() returned and the caller quietly discarded.

The test costs one line, and it is not the line most people reach for. Do not re-run with more seeds; print the converged angles rather than the ratio:

python print(seed, np.round(params.flatten(), 4), round(ratio, 4))

If the angles differ across seeds and the ratio does not, the landscape has one basin and the identical result is real. If the angles are identical, your RNG is not wired up and every "8 seeds" claim in your notebook is one seed eight times.

Here they differ, and 0.751 is genuine: two parameters, one basin, and Adam finds it from anywhere in $[0,\pi]^2$. It is also a property that evaporates immediately — the standard deviation is 0.008 at $p=2$ and 0.021 at $p=4$. An identical result is evidence of a bug until you have found the mechanism that makes it not one, and "I checked and the mechanism is a convex-looking two-parameter landscape" is a finding you can write down. Chapter 26 is nine sections of this failure class.

37.5 Goemans–Williamson

The baseline is not a heuristic. GW solves a semidefinite relaxation, then rounds with a random hyperplane:

X = cp.Variable((n, n), PSD=True)
prob = cp.Problem(cp.Maximize(cp.sum(cp.multiply(W, 1 - X)) / 4),
                  [cp.diag(X) == 1])
prob.solve()

Relax each spin to a unit vector, solve the resulting SDP in polynomial time, cut the sphere with a random hyperplane, and read off the signs. The analysis gives 0.87856 of the optimum in expectation.

GW is also a randomized algorithm that samples and takes the best, which is exactly QAOA's structure. That matters for the comparison, because Chapter 35 §35.5 already showed what happens when two sampling algorithms are compared at unequal budgets: the answer inverts.

37.5.1 The relaxation, derived

The exact problem is a maximization over $z \in \{\pm1\}^n$, and the $\pm1$ is the whole difficulty. So relax it — not by dropping the constraint, but by raising the dimension. Replace each scalar $z_i \in \{\pm1\}$ with a unit vector $\mathbf v_i \in \mathbb{R}^n$, and each product $z_uz_v$ with the inner product $\langle \mathbf v_u, \mathbf v_v\rangle$:

$$\max_{\|\mathbf v_i\| = 1} \sum_{(u,v)\in E}\frac{1 - \langle \mathbf v_u, \mathbf v_v\rangle}{2}$$

Collect the inner products into the Gram matrix $X_{ij} = \langle \mathbf v_i, \mathbf v_j\rangle$. A matrix is the Gram matrix of some set of vectors exactly when it is positive semidefinite, and "unit vectors" is exactly $X_{ii} = 1$. That is the entire cvxpy program above: PSD=True and cp.diag(X) == 1. The objective's division by 4 rather than 2 is because W is the full symmetric adjacency matrix and counts each edge twice.

Why it is an upper bound is one line, and it is worth having that line by heart. Any feasible $\pm1$ assignment $z$ can be written as a feasible $X$: pick any unit vector $\mathbf e$ and set $\mathbf v_i = z_i \mathbf e$. Then $X_{ij} = z_iz_j$, which is rank 1, PSD, and has unit diagonal — feasible for the SDP, with the same objective value. So the relaxation's feasible set contains the integer feasible set, and a maximum over a larger set cannot be smaller:

$$\text{SDP} \;\geq\; \text{OPT}$$

Always. Every graph. No probability involved, no assumption about structure. Measured on the ten instances:

     #   OPT   SDP bound   bound/OPT
     0    13     13.0326      1.0025
     1    13     13.3710      1.0285
     2    13     13.1015      1.0078
     3    13     13.7263      1.0559
     4    13     13.7263      1.0559
     5    13     13.6557      1.0504
     6    13     13.0522      1.0040
     7    13     13.0326      1.0025
     8    13     13.3710      1.0285
     9    13     13.4401      1.0339

   mean bound/OPT   1.0270

The relaxation is 2.7% loose on average and 0.25% loose at its tightest. That looseness is the entire certificate: GW ends up holding a cut $c$ and a bound $B$ with $c \le \text{OPT} \le B$, so it knows $c/\text{OPT} \geq c/B$ without ever computing OPT. §37.7 is what that is worth.

📐 Math Aside: the random hyperplane, and where 0.87856 comes from.

The rounding is four lines of code and one of the prettiest arguments in combinatorial optimization.

Draw $\mathbf r \sim \mathcal N(0, I)$ and set $z_i = \operatorname{sign}\langle \mathbf r, \mathbf v_i\rangle$ — cut the sphere with a uniformly random hyperplane through the origin and read off which side each vector fell on.

What is the probability that edge $(u,v)$ gets cut? Project everything onto the 2-plane spanned by $\mathbf v_u$ and $\mathbf v_v$. A Gaussian vector's projection points in a uniformly random direction of that plane, and the two signs disagree exactly when that direction lands in one of the two arcs lying between the vectors. Two arcs of angular width $\theta_{uv}$ out of $2\pi$:

$$\Pr[(u,v)\ \text{cut}] \;=\; \frac{\theta_{uv}}{\pi}, \qquad > \theta_{uv} = \arccos\langle \mathbf v_u, \mathbf v_v\rangle$$

The SDP's own credit for that edge is $(1 - \cos\theta_{uv})/2$. So edge by edge, the rounding delivers a fraction

$$\alpha(\theta) \;=\; \frac{\theta/\pi}{(1-\cos\theta)/2} \;=\; \frac{2\theta}{\pi\,(1-\cos\theta)}$$

and by linearity of expectation, $E[\text{cut}] \geq \left(\min_\theta \alpha\right) \cdot \text{SDP} \geq \left(\min_\theta \alpha\right)\cdot \text{OPT}$. Minimizing numerically over $(0,\pi]$:

text alpha_min 0.878567 at theta* 2.331122 rad = 133.563 degrees P(separated) theta/pi = 0.742019 SDP credit (1-cos)/2 = 0.844579 ratio 0.878567

Two things are worth pulling out of that.

First, $\alpha(\pi/2) = 1$ and $\alpha(\pi) = 1$. The bound is tight at exactly one interior angle near 133.6°, and the edges that cost the most are the obtuse ones — the pairs the SDP was most confident should be separated. The worst case is not the ambiguous edges. It is the confident ones, being rounded slightly less often than their confidence deserved.

Second, look at where the chain of inequalities lands. It runs $E[\text{cut}] \geq \alpha \cdot \text{SDP} \geq \alpha \cdot \text{OPT}$, and the middle quantity is computable on your instance. That is what turns 0.87856 from a worst-case constant into a per-instance number: on instance 0, GW does not have to fall back on 0.878, because it can divide 13 by 13.0326 and report 0.9975. A guarantee you can evaluate on your own input is a certificate. One you can only quote is a slogan.

37.6 The comparison, run fairly

One seed each, one sample each, ten random 3-regular graphs on 10 vertices, QAOA at $p=3$:

     #  |E|  OPT  GW(1)  GW=OPT  QAOA E[cut]/OPT  QAOA best-of-1   winner
     0   15   13     13    True            0.873              13      tie
     1   15   13     13    True            0.854               9       GW
     2   15   13     13    True            0.900               9       GW
     3   15   13     13    True            0.898              11       GW
     4   15   13     11   False            0.907              11      tie
     5   15   13     13    True            0.911              13      tie
     6   15   13     12   False            0.874              11       GW
     7   15   13     13    True            0.873              11       GW
     8   15   13     13    True            0.896              13      tie
     9   15   13     13    True            0.922               9       GW

QAOA won 0 of 10. GW won 6. Four ties.

   GW's single rounding hit the exact optimum on   8/10 instances
   QAOA p=3 mean E[cut]/OPT                        0.891 (std 0.020)
   mean GW time                                    5.9 ms
   mean QAOA time                                  5.2 s      (875x)

Read the two QAOA columns together, because they say different things. The expected cut ratio is 0.891 — respectable, and above the 0.878 guarantee. The single sample is frequently 9 or 11 against an optimum of 13. A distribution with a good mean still returns bad individual answers, and an optimization user gets an answer, not a mean.

📊 What the Numbers Say. 0.891 is a real number and it is the wrong number to quote. It describes the state QAOA prepared, not the answer a user receives. Chapter 30 §30.5 refused to let a fidelity be quoted without naming its statistic; this is the same refusal with a graph attached.

37.6.1 GW's rounding is a distribution too

The GW=OPT column above is ten single roundings — one random hyperplane per instance. Which is precisely the protocol §37.4 just spent a section warning about, applied to this chapter's own headline number. So it was re-measured: the same ten SDP solutions, 1,000 hyperplanes each.

     #   OPT   P(one rounding = OPT)   mean cut   worst of 1,000
     0    13                   0.639     12.454       10
     1    13                   0.759     12.519       11
     2    13                   0.539     12.195       10
     3    13                   0.846     12.693       10
     4    13                   0.840     12.680       10
     5    13                   0.745     12.743       11
     6    13                   0.524     12.182       10
     7    13                   0.606     12.398       10
     8    13                   0.773     12.547       11
     9    13                   0.533     12.392        9

   mean P(one rounding hits OPT)   0.680     range 0.524 - 0.846

The expected number of exact hits in ten single roundings is 6.8, not 8. Under these per-instance probabilities, exactly 8 happens 21.2% of the time and 8-or-more 32.4%.

So §37.6's 8/10 is a true measurement and a favourable draw. Nothing above it changes — QAOA still won 0, because GW would have to fall to 9 or 11 on an instance to lose to the samples QAOA returned — but what the number is changes. 8 of 10 is a draw. 0.68 per rounding is a rate. The second one is the one that will still be true next week.

This is the fifth appearance of the same lesson in this book, and it differs from the other four in one respect worth noting. The previous four were caught because a result looked wrong. This one was caught by turning the rule on a number that looked entirely right — the chapter's own most flattering statistic, in favour of the side the chapter was already arguing for. That is the only place the rule is ever inconvenient, and therefore the only place it is worth anything.

37.6.2 Distribution against distribution

QAOA has one honest defence left in §37.6, and it should be taken seriously: its expected ratio of 0.891 clears the 0.87856 guarantee, and comparing a distribution's mean against a single classical sample is unfair in the other direction. Fine — compare mean to mean. QAOA's $E[\text{cut}]/\text{OPT}$ against the mean of GW's 1,000 roundings, per instance:

     #   QAOA E[cut]/OPT   GW rounding mean/OPT   P(one GW rounding > QAOA's mean)
     0             0.873                 0.9580                              0.845
     1             0.854                 0.9630                              0.760
     2             0.900                 0.9381                              0.702
     3             0.898                 0.9764                              0.848
     4             0.907                 0.9754                              0.842
     5             0.911                 0.9802                              0.998
     6             0.874                 0.9371                              0.732
     7             0.873                 0.9537                              0.834
     8             0.896                 0.9652                              0.774
     9             0.922                 0.9532                              0.926

   mean of means      QAOA 0.8908      GW 0.9600

★★ GW's rounding distribution has the higher mean on 10 of 10 instances, and the two sets of per-instance means do not even overlap: GW's worst (0.9371) is above QAOA's best (0.9220). The probability that a single GW rounding beats QAOA's entire expected value runs from 0.702 to 0.998.

The defence does not survive. Compared sample to sample, QAOA lost 0–6–4. Compared distribution to distribution — the comparison QAOA's own defenders should prefer — it loses 0–10. The 0.891 was never being measured against a lucky single draw. It was being measured against a distribution centred on 0.96.

One last row of that table deserves its own sentence. On instance 9, QAOA's single sample returned a cut of 9. Over 1,000 roundings, GW's worst result on that instance was also 9. QAOA's answer equalled the classical algorithm's worst-in-a-thousand.

37.7 The certificate

This is the finding that outlasts the scorecard, because hardware improvements do not touch it.

The SDP does not only produce a cut. It produces an upper bound on the optimum:

   n=10  OPT=13  GW cut=13  SDP upper bound=13.0326
   -> GW certifies its answer is within 0.9975 of optimal WITHOUT knowing OPT

GW hands back a solution and a proof that no solution is much better. On this instance it certifies its own answer to within a quarter of a percent — without brute force, and without being told the optimum.

QAOA returns a bitstring and nothing else. There is no bound, no gap, no certificate.

🔬 Honest Assessment: you cannot tell a good QAOA answer from a bad one without solving the problem another way.

Row 9 of the table returned a cut of 9 against an optimum of 13. Nothing in the QAOA output distinguishes that from row 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.

37.7.1 Relaxation bounds from above; restriction bounds from below

The missing certificate is not an oversight in QAOA's design and not a limitation of current hardware. It is the direction of an inequality, and the inequality is two lines long.

QAOA prepares a state $|\psi\rangle$ and reports $\langle\psi|H_C|\psi\rangle$. Because $H_C$ is diagonal with the cut values on its diagonal (§37.2.1), that expectation is a probability-weighted average of feasible cut values — and an average of feasible values cannot exceed the largest feasible value:

$$\langle\psi|H_C|\psi\rangle \;=\; \sum_x P(x)\,C(x) \;\leq\; \max_x C(x) \;=\; \text{OPT}$$

That holds for every state, every ansatz, every $p$, every set of angles, and every device, noisy or perfect. QAOA's objective is a lower bound on OPT. So is the bitstring it samples. So is anything any heuristic ever returns: producing a feasible solution is producing a lower bound, and lower bounds are the easy half of the problem.

The SDP goes the other way for one reason: it does not optimize over feasible solutions at all. It optimizes over the superset built in §37.5.1 — all PSD unit-diagonal matrices, which contains every $\pm1$ assignment as a rank-1 special case and a great deal besides. A maximum over a superset is an upper bound.

Relaxation bounds from above. Restriction bounds from below. QAOA is a restriction — to the states a $2p$-parameter circuit can reach — and widening a restriction never converts it into a relaxation. At $p\to\infty$ QAOA reaches the optimum. It still does not learn that it has.

★ This is worth stating carefully, because the same structure is usually described as an advantage one chapter earlier. Chapter 36's variational principle gives $\langle\psi|H|\psi\rangle \geq E_0$: your answer sits above the true ground energy, so you know the truth is at least as good as what you have. Identical situation, minimization instead of maximization, and identically silent about how much better the truth is. Chapter 36 §36.5 measured VQE converging to within $2.04\times10^{-9}$ Ha of the answer its active space could express, while the active space itself was off by 0.0201 Ha — a ratio of 9,870,104. The variational bound was tight on the quantity that did not matter and had nothing to say about the one that did.

37.7.2 Could QAOA ever produce one? Four routes, honestly

Exercise 37.29 asks this, and the answer is more interesting than "no."

1. The variational principle. Wrong direction, as above. It certifies that your answer is no better than optimal, which you knew.

2. Sampling statistics. With enough shots you can put an arbitrarily tight confidence interval on $\langle H_C\rangle$. But that is an interval around the state's mean, not around OPT. Shrinking it to zero tells you exactly what your circuit produces and still nothing about what the graph permits. This is Chapter 30 §30.5's distinction again, and it is the book's recurring "a measurement that cannot detect the thing being asked about" — six instances across Part V, and this is the cleanest one, because the measurement is perfect and still answers a different question.

3. Run the relaxation alongside. This works. It is also what the honest hybrid in §37.9 amounts to: warm-start from GW and keep GW's bound. Then the certificate is classical, the bound is the SDP's, and the quantum contribution is a local improvement step on an answer that was already certified. That is a defensible product. It is not "QAOA solved the problem."

4. The one that is genuinely open, and the strongest counterargument to §37.7: the certificate is produced by an SDP, and quantum algorithms for semidefinite programs exist in the literature with speedups in some parameters. If one ever ran at useful scale, a quantum computer would be producing the upper bound.

Notice what that concedes, though. The quantum algorithm that produces a certificate is not QAOA — it is a quantum implementation of the classical method. §37.7's gap is between QAOA and relaxation-based optimization, not between quantum and classical, and the way to close it is to build the relaxation rather than to route around it.

⚠️ Common Pitfall: "QAOA found the optimum on this instance."

Every such statement in this chapter is checkable only because $n \leq 12$ and brute force over $2^n$ was affordable — 4,096 assignments enumerated exactly, in milliseconds. The OPT column exists because the problem was already solved by exhaustion before either algorithm ran.

At $n = 50$ there are $1.1\times10^{15}$ assignments and there is no OPT column. The experiment that validates QAOA is only runnable at sizes where nobody needs QAOA. Above that line you are back to comparing against a bound — and QAOA does not have one, so the bound will be the SDP's.

This is exactly Chapter 36 §36.7's crossover with a graph instead of a molecule: the classical check that makes the quantum result meaningful — exact diagonalization there, 22.996 s at 12 qubits — stops being available precisely where the quantum result would start being interesting. The regime where you can verify and the regime where you would need to are disjoint, and no amount of hardware progress moves the first one.

37.8 What the simulator was hiding

Every number above came from exact state-vector simulation, where expectation values are free. On hardware they are sampled, and Chapter 24 §24.3's $1/\epsilon^2$ returns:

   p=1  eps=0.1         100 shots/energy        50,000 total       5.0 s of device time
   p=1  eps=0.01     10,000 shots/energy     5,000,000 total     500.0 s
   p=3  eps=0.1         100 shots/energy       130,000 total      13.0 s
   p=3  eps=0.01     10,000 shots/energy    13,000,000 total   1,300.0 s
   p=5  eps=0.01     10,000 shots/energy    21,000,000 total   2,100.0 s

Thirteen million shots — twenty-two minutes of exclusive device time — for a 12-node graph whose answer GW produced in 8 milliseconds.

And the shot budget is the optimistic term. It assumes the optimizer converges in 100 iterations, that the angles found on a simulator transfer to hardware, and that noise does not flatten the landscape below the resolution the shots buy.

37.8.1 Where the 13,000,000 comes from

The table is not an estimate. It is three multiplications, and doing one of them by hand tells you which factor is worth attacking.

Evaluations per optimizer step. Parameter-shift gradients need two circuit evaluations per parameter, plus one for the energy itself: $2(2p) + 1$. At $p=3$ that is 13.

Shots per evaluation. A standard error of $\epsilon$ on an expectation value costs $(\sigma/\epsilon)^2$ shots — Chapter 24 §24.3's $1/\epsilon^2$, which is Chapter 5's $1/\sqrt{N}$ inverted. At $\epsilon = 0.01$ with $\sigma = 1$: 10,000.

Optimizer steps. 100.

$$13 \times 10{,}000 \times 100 \;=\; 13{,}000{,}000 \;\longrightarrow\; 1{,}300\ \text{s at }10{,}000\ \text{shots/s}$$

The same arithmetic with 5, 13, and 21 evaluations per step reproduces every row of §37.8's table exactly, and qaoa_shot_budget() in vqelab.combinatorial is those three lines with the input validation attached.

Now read the factors for leverage. The $1/\epsilon^2$ is the largest and the least negotiable: one more digit of precision costs 100×. The $2(2p)+1$ is the only one QAOA's design touches, and §37.3.1 showed what it is worth — 13 evaluations instead of 121.

The 100 iterations is the softest number in the table and the one most likely to be wrong in the expensive direction. And it interacts badly with §37.4. The fix for reading a result off one draw is to run eight seeds, and eight seeds multiply this table by eight:

   p=3, eps=0.01, 1 seed        13,000,000 shots      22 minutes
   p=3, eps=0.01, 8 seeds      104,000,000 shots      2.9 hours

Just under three hours of exclusive device time, for one 12-node graph, to obtain a result you are willing to defend. The protocol that makes a QAOA result trustworthy costs eight times the protocol that makes it publishable. That is §37.4's lesson denominated in shots, and it is a better explanation than carelessness for why the cheap version keeps appearing in print.

📉 Noise Report: the margin is thinner than the error budget of the circuit that produces it.

Every number in this chapter is noiseless. The cheapest useful model of what changes is a global depolarizing channel: with probability $\lambda$ the state is replaced by the maximally mixed state.

The maximally mixed state samples bitstrings uniformly — and §37.1.1 already measured what a uniform bitstring cuts on these instances: 7.5 of 15 edges, 0.577 of the optimum. So the measured ratio degrades linearly between two numbers this chapter already owns:

$$r(\lambda) \;=\; (1-\lambda)(0.891) \;+\; \lambda\,(0.577)$$

Set that equal to the 1994 guarantee and solve:

$$\lambda^{*} \;=\; \frac{0.891 - 0.87856}{0.891 - 0.577} \;=\; \frac{0.01244}{0.3141} \;=\; 0.0396$$

A 4% global depolarizing rate consumes the entire margin QAOA has over Goemans–Williamson's guarantee. The margin being defended is 0.012.

Is 4% a lot? The $p=3$ circuit on a 15-edge instance is 45 $ZZ$ rotations, which Qiskit decomposes to 90 CNOTs. At Chapter 39's best measured cz error on a real device, $1.79\times10^{-3}$:

text 45 two-qubit interactions 1 - (1 - 0.00179)^45 = 0.0775 90 CNOTs 1 - (1 - 0.00179)^90 = 0.1489

Two to four times the budget — on the best link of the chip, with no routing, no readout error, and no idling. Chapter 30 measured the spread of two-qubit error across a single device at 0.00750 to 0.07205, a factor of 9.6, so the typical link is several times worse than the number above.

Say plainly what this is. Global depolarizing is a model, and the linear interpolation is its consequence, not an experiment. What is measured is the two endpoints (0.891 and 0.577) and the gate error ($1.79\times10^{-3}$). The conclusion that survives the model is structural: the margin is 0.012 and the circuit loses more than that long before it finishes.

And the direction noise pushes is not random. It pushes toward the maximally mixed state, whose expected cut is exactly the classical do-nothing baseline. Noise does not turn QAOA into a worse optimizer. It turns it into a slower random-bitstring generator.

💰 Cost and Queue: what 13 million shots costs at list price.

Chapter 39 §39.5 priced this chapter's own run under three billing models:

text experiment shots tasks QPU time @$0.00035 @$0.01/shot Ch.37 QAOA p=3, eps=0.01 13,000,000 1,300 0.5 m $4,940 $130,390

Note the QPU-time column against the 22 minutes above. Half a minute of gate time; the rest is shot delivery. Chapter 39 §39.2 measured why — measure at 1,560 ns and reset at 1,600–1,848 ns against cz at 68–184 ns, so a shallow circuit's per-shot duration is dominated by the two operations that have nothing to do with your algorithm.

Against that: GW solved the same instance in 8 milliseconds on a CPU that is already paid for. The cheaper of the two quantum figures buys the uncertified answer — and if the workload runs daily, it buys it again tomorrow.

37.9 What would actually have to change

The honest version of QAOA's case is narrower than the usual one, and it is not empty.

1. The instances have to be hard for the classical baseline. Random 3-regular MaxCut is not — GW solves it exactly, 8 times in 10, in milliseconds. This is Chapter 21 §21.7's lesson again: benchmarking on instances the baseline finds easy measures nothing. The interesting question is whether there is an instance family where GW's 0.878 is tight and QAOA does better, and the honest answer is that no such family has been demonstrated on hardware.

2. Warm-starting and problem structure. Initializing QAOA from the GW solution, or exploiting symmetry to fix angles without optimizing, removes the classical optimization loop — which is where both the shot budget and the barren-plateau risk live. This is the most promising direction in the chapter, and note what it concedes: it starts from the classical answer.

3. Depth, which the hardware does not have. $p=5$ on 12 nodes is already 90 two-qubit gates before routing. Chapter 29 measured what heavy-hex routing does to that, and Chapter 31 measured what coherence does. The $p \to \infty$ guarantee is not reachable and $p=1$ is below the classical guarantee.

4. A certificate, or an argument that one is not needed. Some applications genuinely do not need a bound — you take the best answer you can afford and ship it. But then the comparison is against simulated annealing and tabu search, which are also uncertified, also fast, and have fifty years of tuning. QAOA does not beat those either.

37.9.1 The bar is not 0.878

Point 1 above deserves a number, because the shape of the loss is routinely misdescribed.

QAOA did not lose to an algorithm with a 0.878 guarantee. On these instances the guarantee is nowhere near tight: §37.5.1 measured the relaxation at 2.7% loose on average and §37.6.2 measured the rounding delivering 0.9600 of the optimum in expectation and landing exactly on it 68% of the time.

   the number to beat in a proof        0.87856
   the number to beat in practice       0.9600     (measured, mean of GW's rounding distribution)
   what QAOA p=3 delivered              0.8908

0.878 is the worst case over all graphs; 0.96 is what actually arrived on this one. Any claim of the form "QAOA achieved 0.89, above the classical guarantee" is comparing against a bound the classical algorithm was never operating near. Chapter 21 §21.7's rule — compared to what? — has a second edge to it: comparing against the baseline's worst-case guarantee rather than its measured behaviour is a weak-baseline comparison wearing a proof for a disguise.

The same measurement prices point 2, warm-starting, more precisely than §37.9 did. GW's retry is essentially free — the SDP is solved once and each additional hyperplane is a matrix–vector product — so the honest baseline for "QAOA improves a GW solution" is a second hyperplane, not the first one:

   instances of 10 solved exactly, in expectation
     1 rounding      6.80
     2 roundings     8.83
     3 roundings     9.53
     5 roundings     9.91

To be worth its shot budget, a warm-started QAOA has to close the gap on the roundings that miss, more often than the next few microseconds of classical rounding would. That is the comparison the proposals do not run, and it is cheaper to run than the one they do.

What genuinely survives is angle transfer, and §37.3.2 said why in shots: the readout is 10 shots and the optimization is 21,000,000. If angles transfer across instances of a family, the optimization amortizes to zero and the marginal cost of an answer becomes a millisecond. That would be a different economic picture, and it is Exercise 37.12. This chapter did not measure it, so this chapter does not claim it — the status is that transfer is reported in the literature and not demonstrated here.

🧪 Run It: the experiment that would change this chapter's mind.

Everything above is one instance family, and this chapter's honest weakness is that random 3-regular MaxCut is easy for GW — 68% exact per rounding, 0.96 in expectation. Exercise 37.24 asks for a family where that is false. Two directions worth trying, in roughly increasing promise:

python G = nx.gnp_random_graph(14, 0.5, seed=0) # denser, no regularity for u, v in G.edges(): # and weighted, which is where G[u][v]["weight"] = rng.integers(1, 10) # the rounding gives up the most

Then re-run §37.6's protocol and report three columns rather than one: GW's single rounding, GW's rounding distribution over 1,000 hyperplanes, and QAOA's expected ratio. §37.6.2 exists because the first column on its own is not the comparison.

What would count as a result: a family where GW's mean rounding ratio falls below QAOA's expected ratio, on more than one instance, across at least eight seeds. compare_solvers() returns INSUFFICIENT_SEEDS until you have them, which is the entire reason it is in the module.

What would not count: QAOA's best-of-1,000 against GW's best-of-1. And what would not count either: a win with no certificate column, because §37.7 does not move when the scorecard does.

What we measured

• QAOA won 0 of 10 against Goemans–Williamson on random 3-regular MaxCut; GW won 6, 4 tied
• GW's single rounding hit the exact optimum on 8/10 instances, in 5.9 ms against QAOA's 5.2 s — 875× (wall-clock varies a few percent between runs)
• More layers do help: mean ratio 0.751 → 0.907 from $p=1$ to $p=5$, and $P(\text{optimal})$ rises from 0.02 to 0.39 against 0.0005 for the uniform superposition — a factor of 795
• $p=1$ scores 0.751, below GW's 0.87856 guarantee. A proof from 1994 beats QAOA's first layer
• The $p=4$ regression was not real — 7 of 8 seeds went the other way; the one-seed table was a draw from a distribution, the book's fourth instance of that error
• Landscape variance grows with $p$: std 0.000 at $p=1$ to 0.021 at $p=4$
• The Ising mapping is exact — unlike Chapter 36, no approximation stands between the problem and the Hamiltonian
• ★★ GW returns a certified answer and QAOA returns a bitstring. The SDP bound proved its cut was within 0.9975 of optimal without knowing the optimum. That gap is not a hardware problem.
• 13,000,000 shots at $p=3$ for $\epsilon = 0.01$ on a 12-node graph — 22 minutes of device time against 8 milliseconds
• ★★ Compared distribution to distribution, QAOA loses 0–10. Re-rounding each SDP solution 1,000 times, GW's rounding mean beats QAOA's $E[\text{cut}]/\text{OPT}$ on every instance — 0.9600 against 0.8908, with no overlap between the two sets of per-instance means
• GW's exact-hit rate is 0.680 per rounding (range 0.524–0.846), so 6.8 hits was the expectation and the reported 8/10 was a favourable draw — the fifth appearance of this lesson, and the first found by auditing a number that looked right rather than one that looked wrong
• The SDP relaxation is 2.7% loose on average, 0.25% at its tightest — which is the certificate
• 0.87856 is $\min_\theta \frac{2\theta}{\pi(1-\cos\theta)} = 0.878567$, attained at 133.563°, derived and confirmed numerically; the ratio returns to 1 at both $\pi/2$ and $\pi$
• A 4% global depolarizing rate erases QAOA's entire 0.012 margin over the 1994 guarantee, and the $p=3$ circuit loses 7.8–14.9% at the best two-qubit error Chapter 39 measured
• The one-seed protocol had a 21.9% chance of showing the $p=4$ regression on any graph, and a 52.3% chance across three — the error was a routine draw, not a fluke
• The concentration is in the wrong budget line: $P(\text{optimal}) = 0.388$ buys a 10-shot readout, after 21,000,000 shots of optimization

Next: Chapter 38 turns to the one application in this book that is deployed, commercially available, and works — and finds that its hard problems moved somewhere the physics does not reach.