QAOA Performance Bounds and Concentration

The Quantum Approximate Optimization Algorithm promises to attack hard combinatorial problems — MaxCut, Max-SAT, portfolio selection — with a shallow, parameterized quantum circuit. But a promise is not a proof, and the theory of QAOA is really the theory of two questions in tension: how good can it be? and why is it so easy to train? Both answers flow from a single structural fact: at depth $p$ , the algorithm is strictly local. A QAOA circuit alternates $p$ layers of a problem unitary $e^{-i\gamma_k C}$ and a mixer $e^{-i\beta_k B}$ , and each cost term $C_a$ , evolved in the Heisenberg picture, can only reach qubits within graph distance $p$ of its own support. Its causal light cone has radius $p$ , no more. That one geometric constraint organizes everything. Because $F_p$ is a sum of contributions that each see only a radius- $p$ neighbourhood, two large instances sharing the same local structure yield almost the same expected cost at the same angles — so optimal parameters concentrate and transfer, and the cost value concentrates to a sharp mean with $O(1/\sqrt{m})$ fluctuations. The same locality is a cage: on large-girth graphs every light cone looks like an identical tree, so constant-depth QAOA is provably blind to global structure and cannot beat the best classical local algorithms on ensembles like the Sherrington–Kirkpatrick spin glass. This article assembles the guarantees, the concentration theorems, and the locality obstructions into one picture, and names the central open question: how fast must $p$ grow with $n$ for QAOA to win?

Key takeaways

QAOA at depth $p$ prepares $|\gamma,\beta\rangle=\prod_{k=1}^{p}e^{-i\beta_k B}e^{-i\gamma_k C}|+\rangle^{\otimes n}$ and maximizes $F_p=\langle C\rangle$ over $2p$ angles; its power is set by depth, degree, and geometry.
For MaxCut on triangle-free 3-regular graphs the level-1 guarantee is exactly $r\ge\tfrac12+\tfrac{1}{3\sqrt3}=0.6924$ — beating random ( $0.5$ ) but short of the classical Goemans–Williamson bound $0.8786$ .
Higher depth helps monotonically: Wurtz and Love prove $r\ge0.7559$ at $p=2$ and $r\ge0.7924$ at $p=3$ on 3-regular MaxCut, climbing toward the classical value.
Optimal angles concentrate — for fixed $p$ they depend only on local subgraph types, so they are nearly instance-independent, transferable, and learnable.
The cost value concentrates too: $\mathrm{Var}(F_p/m)\le O(D^{2p})/m$ , a gift for cheap estimation but also the root of no-go theorems, since locality blinds constant-depth QAOA to global structure.
Girth $g>2p+1$ makes every radius- $p$ light cone a tree, so QAOA cannot distinguish hard instances from typical random graphs — beating classical algorithms requires $p$ to grow with $n$ .
Key idea: At depth $p$ each local cost term sees only a radius- $p$ light cone, so $F_p$ is a sum of instance-independent local contributions — this simultaneously forces optimal parameters and cost values to concentrate and imposes locality-based limitation theorems bounding constant-depth performance.

Where this lives today

QAOA is the flagship candidate for near-term quantum advantage in optimization, and the performance-and-concentration theory is what tempers the hype into a research program. Google's Sycamore ran QAOA up to a few dozen qubits, and Harvard–MIT–QuEra neutral-atom arrays ran QAOA for Maximum Independent Set on hundreds of atoms — the sparse ensembles where the obstructions bite, so measured ratios are read against the FGG no-go baseline, not against $r=1$ . Parameter concentration is now standard practice: the INTERP and FOURIER heuristics of Zhou et al. exploit the smooth, near-universal schedules (rising $\gamma_k$ , falling $\beta_k$ ) to seed depth- $p$ angles from depth $p-1$ , and transferability lets angles from small tree light cones be reused on large instances. On the theory frontier the question is quantitative: constant depth provably cannot win on the hardest ensembles, so the live problem is how slowly $p$ may grow — is $p=O(\log n)$ enough to overtake the best classical solvers, and does the optimization stay tractable? Recursive RQAOA, longer-range mixers, and warm-started variants all try to buy reach without paying full depth, each benchmarked against these locality bounds.

The physical picture

Think of each edge as a tiny sensor contributing to the MaxCut cost. Evolve its operator $C_a$ backward through the circuit — the Heisenberg picture — and the diagonal cost layers leave its support unchanged, while each mixer $e^{-i\beta_k B}=\prod_j e^{-i\beta_k X_j}$ smears it onto every neighbouring qubit. After $p$ mixer layers the operator lives on the radius- $p$ ball around the edge and nowhere else — the causal light cone, whose size grows like $D^p$ on a degree- $D$ graph. The first figure draws this cone and states the two facts everything rests on: it holds at most $1+D+\cdots+D^p$ qubits, and with no short cycles it is a tree.

Figure

The causal light cone of one cost term: diagonal layers e^{iγC} leave support fixed while each mixer e^{iβB} widens it by one shell, so after p layers U†C_aU is supported only on the radius-p ball N_p(a), of size at most 1 + D + D² + … + Dᵖ, a tree when girth g > 2p+1

Locality is double-edged, and the second figure turns the two edges into numbers. Because $F_p$ is a sum over local cones, the certified worst-case ratio is fixed by the least favourable subgraph type — and climbs with $p$ as the cones grow. Farhi, Goldstone and Gutmann proved $0.6924$ at $p=1$ for 3-regular MaxCut; Wurtz and Love pushed it to $0.7559$ at $p=2$ and $0.7924$ at $p=3$ ; the staircase sits below the classical Goemans–Williamson bound $0.8786$ and above the random floor $r=0.5$ . This is the honest scorecard for constant-depth QAOA.

Figure

Certified worst-case approximation ratio for QAOA on 3-regular MaxCut rising with depth: r ≥ 0.6924 at p = 1 Farhi–Goldstone–Gutmann, then 0.7559 at p = 2 and 0.7924 at p = 3 Wurtz–Love, climbing toward the classical Goemans–Williamson bound 0.8786 and the ceiling r = 1, above the random floor 0.5

The core equations

QAOA is defined by one state and one number. The state alternates the problem Hamiltonian and the mixer $p$ times from the uniform superposition; the number is its expected cost, maximized over the $2p$ angles. Everything downstream is a statement about this expectation.

|\gamma,\beta\rangle = \prod_{k=1}^{p} e^{-i\beta_k B}\, e^{-i\gamma_k C}\,|+\rangle^{\otimes n} \qquad (1)

where: $C=\sum_a C_a$ — diagonal cost Hamiltonian, for MaxCut $C=\tfrac12\sum_{(i,j)\in E}(I-Z_iZ_j)$ ; $B=\sum_{j=1}^n X_j$ — transverse-field mixer; $\gamma_k\in[0,2\pi),\ \beta_k\in[0,\pi)$ — the $2p$ variational angles; $|+\rangle^{\otimes n}$ — uniform superposition, the ground state of $-B$ . Reading: imprint cost phases and mix, $p$ times, from the equal superposition. The figure of merit is the expected cost, reported as an approximation ratio against the true optimum. A ratio of $1$ is exact; random guessing scores $\tfrac12$ on MaxCut, the floor any honest algorithm must beat.

F_p(\gamma,\beta) = \langle\gamma,\beta|C|\gamma,\beta\rangle,\qquad r=\frac{\max_{\gamma,\beta}F_p}{C_{\max}} \qquad (2)

where: $F_p$ — expected cost at depth $p$ ; $C_{\max}$ — maximum cost over all bit strings, the exact optimum; $r$ — approximation ratio, with $r=1$ exact and $r=\tfrac12$ for random MaxCut. Reading: tune the angles to push $F_p$ toward $C_{\max}$ . The structural heart of the theory is that $F_p$ decomposes into local pieces: evolved in the Heisenberg picture, each term $C_a$ is supported only on the radius- $p$ ball $N_p(a)$ , so its expectation is computed on that subgraph alone.

F_p = \sum_a \langle +|\,U^\dagger C_a\,U\,|+\rangle,\qquad U^\dagger C_a U \ \text{supported on}\ N_p(a) \qquad (3)

where: $U=\prod_k e^{-i\beta_k B}e^{-i\gamma_k C}$ — the full QAOA unitary; $N_p(a)$ — qubits within graph distance $p$ of the support of $C_a$ ; $\langle+|\cdot|+\rangle$ — expectation in the initial product state. Reading: the objective is a sum of local subgraph expectations; identical types contribute identically. At $p=1$ the subgraph is just the edge and its immediate neighbours, and the sum closes in closed form — the workhorse behind every level-1 guarantee, giving the probability an edge is cut in terms of the endpoint degrees and triangle count.

F_1^{\text{edge}}=\tfrac12+\tfrac14\sin(4\beta)\sin\gamma\,(\cos^{d_u}\!\gamma+\cos^{d_v}\!\gamma)-\tfrac14\sin^2(2\beta)\cos^{d_u+d_v-2f}\!\gamma\,(1-\cos^{f}\!2\gamma) \qquad (4)

where: $d_u,d_v$ — degrees of the endpoints $u,v$ excluding the shared edge; $f$ — number of triangles on edge $(u,v)$ ; $F_1^{\text{edge}}$ — probability that $(u,v)$ is cut at depth 1, summed over edges to give $F_1$ . Reading: the first term is the single-neighbour signal, the $f$ -term the triangle correction coupling the two cones. Optimizing (4) over the finite list of local subgraph types gives the certified worst-case bounds, which rise monotonically with depth toward — but never reach at finite $p$ — the Goemans–Williamson value.

r^{3\text{-reg}}_{p=1}\ge 0.6924,\quad r^{3\text{-reg}}_{p=2}\ge 0.7559,\quad r^{3\text{-reg}}_{p=3}\ge 0.7924,\quad r_{\text{GW}}=0.8786 \qquad (5)

where: $r^{3\text{-reg}}_{p}$ — worst-case ratio on 3-regular MaxCut at depth $p$ ; $r_{\text{GW}}=0.8786$ — Goemans–Williamson SDP guarantee. Reading: each layer buys a monotone increase in the certified ratio, but constant depth stays below the classical bound. Concentration is the second pillar. Because disjoint light cones are independent over a random ensemble, the variance of the rescaled objective is bounded by the overlapping-cone count per term — a function of depth and degree only, not $n$ .

\mathrm{Var}_{G}\!\big[F_p/m\big] \le \frac{c(p,D)}{m},\qquad c(p,D)=O(D^{2p}) \qquad (6)

where: $m$ — number of cost terms (edges); $D$ — degree bounding the cone size; $c(p,D)$ — constant independent of $n$ . Reading: the objective per term has $O(1/\sqrt m)$ fluctuations, so typical instances share a value — and share optimal angles. Finally, locality makes gradients cheap: differentiating by any angle inserts a generator at one layer, but only the part inside a term's light cone survives, so each gradient is a sum of local parameter-shift evaluations.

\partial_\theta F_p=\tfrac12\big[F_p(\theta+\tfrac{\pi}{2})-F_p(\theta-\tfrac{\pi}{2})\big] \qquad (7)

where: $\theta$ — any of the $2p$ angles $\gamma_k,\beta_k$ ; the shift rule is exact for generators with eigenvalues $\pm1$ and each shift touches only bounded-size subgraphs. Reading: exact gradients from two local evaluations per angle keep training tractable at fixed $p$ and $D$ .

Derivation ALevel-one MaxCut cut probability from the radius-one light cone

The goal is to derive the closed-form single-edge cut probability of equation (4) from first principles, since it is the analytic seed of every level-1 guarantee including the celebrated $0.6924$ . We take the MaxCut cost $C=\tfrac12\sum(I-Z_iZ_j)$ , evolve one edge correlator $\langle Z_uZ_v\rangle$ in the Heisenberg picture through a single layer, and evaluate it in $|+\rangle^{\otimes n}$ , where the light cone reduces the computation to the edge and its immediate neighbours.

Step 1. Write the level-1 state $|\gamma,\beta\rangle=e^{-i\beta B}e^{-i\gamma C}|+\rangle^{\otimes n}$ and push the observable into the Heisenberg picture: $\langle Z_uZ_v\rangle=\langle+|\,e^{i\gamma C}e^{i\beta B}\,Z_uZ_v\,e^{-i\beta B}e^{-i\gamma C}\,|+\rangle$ . Why: evolving the operator, not the state, exposes the light cone — only a handful of factors fail to commute through.

Step 2. Conjugate by the mixer first. Since $B=\sum_j X_j$ acts independently on each qubit, $e^{i\beta B}Z_j e^{-i\beta B}=\cos(2\beta)Z_j-\sin(2\beta)Y_j$ , a pure single-qubit rotation. Why: single-qubit $Z\to Y$ mixing grows the support by exactly one shell — the first ring of neighbours.

Step 3. Conjugate the resulting $Y_u,Y_v$ by the diagonal $e^{i\gamma C}$ . Each $Y$ picks up factors $\cos\gamma$ (identity on a neighbour edge) or $\sin\gamma$ (a $Z$ on the neighbour), one factor per edge incident to $u$ or $v$ . Why: the endpoint degrees enter as exponents $\cos^{d_u}\gamma,\cos^{d_v}\gamma$ — each independent neighbour multiplies by $\cos\gamma$ .

Step 4. Evaluate in $|+\rangle^{\otimes n}$ , using $\langle X_j\rangle=1$ and $\langle Y_j\rangle=\langle Z_j\rangle=0$ . Independent neighbours factorize; a shared neighbour — a triangle, counted by $f$ — couples the two cones and contributes the $(1-\cos^f 2\gamma)$ correction. Why: the product state factorizes over neighbours; only triangles break independence, giving the $f$ -term.

Step 5. Assemble the pieces into $\langle Z_uZ_v\rangle$ and convert to the cut probability $F_1^{\text{edge}}=\tfrac12(1-\langle Z_uZ_v\rangle)$ , recovering equation (4). Why: the cut probability is the physical quantity, and summing over edges gives $F_1$ .

Go deeper · Derivation B · 1 minObjective-value concentration from disjoint light cones

Derivation BObjective-value concentration from disjoint light cones

The goal is to prove that the rescaled objective $F_p/m$ concentrates across a random ensemble of $D$ -regular instances, with variance falling as $O(D^{2p})/m$ , so that at fixed depth and degree typical instances share their optimal value and, by the same reasoning, their optimal angles. We write the cost as $m$ local terms, argue that disjoint light cones are independent, and count the overlapping pairs.

Step 1. Decompose $C=\sum_{a=1}^m C_a$ and note that $\langle C_a\rangle$ depends only on the radius- $p$ subgraph $N_p(a)$ , whose size is at most $1+D+\cdots+D^p=O(D^p)$ . Why: by equation (3) each term depends on local geometry alone, so its randomness is confined to its own cone.

Step 2. Observe that if $N_p(a)\cap N_p(b)=\varnothing$ then the two subgraphs are drawn independently from the ensemble, so $\mathrm{Cov}(\langle C_a\rangle,\langle C_b\rangle)=0$ . Why: disjoint cones kill almost all cross terms — only overlapping pairs correlate.

Step 3. Count the survivors. Two cones of radius $p$ overlap only if their centres lie within distance $2p$ , and on a $D$ -regular graph each term has at most $O(D^{2p})$ such neighbours. Hence $\mathrm{Var}_G(F_p)=\sum_{a,b}\mathrm{Cov}(C_a,C_b)\le m\cdot O(D^{2p})$ . Why: $D^{2p}$ counts the terms reachable within the combined diameter of two radius- $p$ cones.

Step 4. Rescale by $m^2$ : $\mathrm{Var}_G(F_p/m)\le O(D^{2p})/m\to0$ as $m\to\infty$ at fixed $p,D$ . Why: the relative spread shrinks as $1/\sqrt m$ , so the objective per term becomes deterministic — value concentration, matching Brandão et al. (2018).

Go deeper · Derivation C · 1 minThe tree-neighbourhood obstruction at large girth

Derivation CThe tree-neighbourhood obstruction at large girth

The goal is to show why constant-depth QAOA is provably blind to global structure on high-girth graphs, turning the friendly concentration property into a hard limitation theorem. Assuming girth $g>2p+1$ , we follow the light-cone decomposition to conclude that the algorithm cannot distinguish structurally different instances sharing the same local tree, forcing $p$ to grow with $n$ for any advantage.

Step 1. If the shortest cycle exceeds $2p+1$ , no cycle fits inside a radius- $p$ ball, so every neighbourhood $N_p(a)$ is a $D$ -regular tree of depth $p$ , identical for every term $a$ . Why: only a cycle of length $\le 2p+1$ can close a radius- $p$ ball; forbidding them makes every cone the same acyclic object.

Step 2. By the light-cone decomposition, $\langle C_a\rangle=f_{\text{tree}}(\gamma,\beta)$ is the same tree expectation for all $a$ , so $F_p=m\,f_{\text{tree}}(\gamma,\beta)$ with $f_{\text{tree}}$ independent of the global graph. Why: if every local computation returns the same number, the total is $m$ copies of it — no global information.

Step 3. Two high-girth instances with different true optima but the same local tree therefore produce identical output statistics on every light cone. Why: depth $p$ cannot see past distance $p$ , so it acts the same on graphs that agree locally.

Step 4. For ensembles like the Sherrington–Kirkpatrick spin glass and sparse Maximum Independent Set, this indistinguishability means constant-depth QAOA cannot beat local classical algorithms — the overlap-gap-property and needs-to-see-the-whole-graph obstructions — so surpassing them requires $p$ to grow with $n$ . Why: a fixed-depth algorithm blind to global structure cannot exploit the long-range correlations that separate good solutions from typical ones — the essence of the no-go results.

Limiting cases

Performance and concentration are governed by depth, degree, and graph geometry; the extremes make the tradeoffs concrete.

Case	Result	Meaning
Depth $p\to\infty$	$r\to1$	Slowly-varying angles Trotterize adiabatic evolution and reach the optimum — an existence result, not a bound on required $p$ .
$p=1$ , triangle-free 3-regular MaxCut	$r\ge\tfrac12+\tfrac{1}{3\sqrt3}=0.6924$	The Farhi–Goldstone–Gutmann guarantee, attained on the tree-like local type.
Large girth / locally tree-like, fixed $p$	$r\le r_{\text{class}}$	Every cone is an identical tree, so QAOA cannot exploit global structure — no advantage over local classical algorithms for SK and sparse MIS.
Many terms, $m\to\infty$	$\dfrac{\sqrt{\mathrm{Var}(C)}}{\langle C\rangle}=O\!\big(\tfrac{1}{\sqrt m}\big)$	Objective concentrates across shots and typical instances — cheap estimation, transferable angles.
Triangles ( $f>0$ ), fixed degree	ratio non-monotonic	The $f$ -term in (4) can raise or lower the cut probability — worst case is not the densest type.

Common trapIf the cost value concentrates so tightly, QAOA must be reliably good

Concentration is not competence. It is tempting to read the sharp $O(1/\sqrt m)$ spread of $F_p/m$ as a guarantee of quality — a low-variance answer sounds like a good answer. It is not. Value concentration says the objective is nearly the same on every typical instance; it says nothing about whether that shared value is close to $C_{\max}$ . On tree-like graphs the shared value is exactly what makes QAOA blind — it returns the same output whether or not the instance has exploitable structure, the mechanism behind the SK and sparse-MIS no-go theorems. Keep the two separate: parameter concentration (transferable optimal $\gamma,\beta$ ) helps training, while value concentration, married to locality, is the root of the obstructions. And $0.6924$ is a worst-case lower bound at $p=1$ on 3-regular graphs, not typical performance.

Worked examples

1 · Deriving the 0.6924 guarantee (fully worked)

A 3-regular graph is triangle-free. Optimize the level-1 QAOA objective analytically and find the certified worst-case approximation ratio for MaxCut.

Step 1. Set local parameters. For a 3-regular edge each endpoint has two other neighbours, so $d_u=d_v=2$ , and triangle-free means $f=0$ , killing the last term of (4) via $(1-\cos^0 2\gamma)=0$ .

Step 2. Reduce the formula. What remains is $F_1^{\text{edge}}=\tfrac12+\tfrac14\sin(4\beta)\sin\gamma\,(2\cos^2\gamma)=\tfrac12+\tfrac12\sin(4\beta)\,\sin\gamma\cos^2\gamma$ .

Step 3. Optimize the mixer. Take $\sin(4\beta)=1$ , i.e. $\beta=\pi/8$ , leaving $F_1^{\text{edge}}=\tfrac12+\tfrac12\,\sin\gamma\cos^2\gamma$ .

Step 4. Optimize the cost angle. Maximizing $g(\gamma)=\sin\gamma\cos^2\gamma$ : $g'(\gamma)=\cos\gamma\,(1-3\sin^2\gamma)=0$ gives $\sin^2\gamma=\tfrac13$ , so $\cos^2\gamma=\tfrac23$ and $g_{\max}=\tfrac{1}{\sqrt3}\cdot\tfrac23=\tfrac{2}{3\sqrt3}=0.3849$ .

Step 5. Assemble the ratio. The optimized cut fraction is $F_1^{\text{edge}}=\tfrac12+\tfrac12(0.3849)=\tfrac12+\tfrac{1}{3\sqrt3}=0.69245$ . Every edge of a triangle-free 3-regular graph has this local type, so the objective inherits the same fraction and the certified worst-case ratio is $\mathbf{r\ge0.6924}$ — the FGG level-1 guarantee, above the random floor $0.5$ but below Goemans–Williamson $0.8786$ .

2 · Concentration and the shot budget

A 3-regular MaxCut instance has $n=2000$ vertices. Estimate the relative fluctuation of the objective and the measurement cost.

Step 1. Count the terms. A 3-regular graph on $n=2000$ vertices has $m=\tfrac{3\cdot2000}{2}=\mathbf{3000}$ edges, so $C=\sum_{a=1}^{3000}C_a$ with each $C_a\in\{0,1\}$ .

Step 2. Bound the variance. Equation (6) with $p=1$ , $D=3$ gives overlap constant $D^{2p}=9$ , so $\mathrm{Var}(F_1/m)\lesssim 9/3000=3\times10^{-3}$ and the relative spread is $O(1/\sqrt m)=1/\sqrt{3000}\approx\mathbf{0.018}$ , under two percent.

Step 3. Translate to shots. Estimating the mean to precision $\epsilon$ needs $O(1/\epsilon^2)$ shots — independent of $n$ here — so $\epsilon=10^{-2}$ costs of order $10^4$ shots whether $n=200$ or $n=2000$ .

Step 4. Read it off. The measurement cost does not grow with system size, and angles found on a small instance transfer to the large one because value and parameters both concentrate — the gift of locality, which is also exactly why $r$ stalls below the classical bound at fixed $p$ .

3 · How fast the light cone grows

On a 3-regular graph, how many qubits does an edge's light cone touch at $p=1,2,3$ , and what depth is needed to see a graph of diameter $\mathrm{diam}\approx\log_2 n$ ?

Step 1. Count a ball. A radius- $p$ ball on a $D$ -regular graph holds at most $1+D+\cdots+D^p$ vertices. For $D=3$ : $p=1\to4$ , $p=2\to13$ , $p=3\to40$ vertices.

Step 2. Read the reach. An edge cone is two such balls, so at $p=3$ it spans a few dozen qubits — a vanishing fraction of a large graph. Correlating vertices at distance $\ell$ needs $p\gtrsim\ell$ , or the cones never overlap.

Step 3. Compare to diameter. A random 3-regular graph has $\mathrm{diam}\approx\log_2 n$ , so exploiting global structure needs $p\gtrsim\log n$ . At constant $p$ the algorithm cannot see the whole graph — the geometric content of the FGG limitation theorem.

Physics of the portrait

QAOA fuses two big ideas — the adiabatic theorem and the variational method — and the person at the centre of both, and of the sharpest limitation theorems that followed, is Edward Farhi.

Origins · 1 minEdward Farhi and how this was discovered

Edward Farhi

b. 1952 · quantum optimization and the theory of QAOA

Edward Farhi is an American theoretical physicist who spent most of his career at MIT — long directing its Center for Theoretical Physics — before joining Google's quantum computing group. He began in particle physics but left his lasting mark through quantum algorithms. Around 2000, with Jeffrey Goldstone, Sam Gutmann and collaborators, he proposed adiabatic quantum computation, reframing optimization as slowly deforming a Hamiltonian from an easy ground state to one encoding the answer. In 2014 the same core trio distilled that into a circuit model — QAOA — replacing the continuous sweep with $p$ discrete alternations of a cost and a mixer unitary, and proving the first closed-form guarantee, the $0.6924$ ratio for 3-regular MaxCut. Characteristically, Farhi then mapped the limits as sharply as the promise: the 2020 paper with David Gamarnik and Gutmann, showing that constant-depth QAOA needs to see the whole graph, is as much his legacy as the algorithm itself.

History

1995

— Goemans and Williamson give the 0.8786 semidefinite-programming bound for MaxCut

2000

— Farhi, Goldstone, Gutmann and Sipser propose adiabatic quantum optimization

2014

— Farhi, Goldstone and Gutmann introduce QAOA and prove the 0.6924 guarantee

2018

— Brandão, Broughton, Farhi, Gutmann and Neven prove objective-value concentration

2020

— Farhi, Gamarnik and Gutmann show constant-depth QAOA needs to see the whole graph

2021

— Wurtz and Love establish the higher-depth 0.7559 and 0.7924 guarantees

Going further

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information, Ch. 4 · Preskill, Caltech Ph219 Lecture Notes, on quantum algorithms and NISQ optimization · Watrous, The Theory of Quantum Information, for the operator formalism behind the light-cone argument · Kitaev, Shen and Vyalyi, Classical and Quantum Computation, for the adiabatic-to-circuit correspondence QAOA discretizes.

Provenance. The primary sources are Farhi, Goldstone and Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014), and its bounded-occurrence companion arXiv:1412.6062; Wurtz and Love, MaxCut QAOA performance guarantees for p>1, Phys. Rev. A 103, 042612 (2021); Brandão, Broughton, Farhi, Gutmann and Neven, arXiv:1812.04170 (2018) for concentration; Farhi, Gamarnik and Gutmann, arXiv:2004.09002 / 2005.08747 (2020) for the whole-graph obstruction; Bravyi, Kliesch, Koenig and Tang, Phys. Rev. Lett. 125, 260505 (2020) for symmetry-protection limits; and Goemans and Williamson, J. ACM 42, 1115 (1995) for the classical $0.8786$ bound. A verifier should: (1) re-derive equation (4) by Heisenberg evolution and product-state expectation and confirm the $0.6924$ triangle-free 3-regular optimum $\tfrac12+\tfrac{1}{3\sqrt3}$ ; (2) check the $p=2,3$ guarantees $0.7559,0.7924$ against Wurtz–Love; (3) confirm the $O(D^{2p}/m)$ variance bound; (4) verify the girth $>2p+1\Rightarrow$ tree-neighbourhood argument.

Prerequisites. Quantum Approximate Optimization Algorithm · Variational Quantum Eigensolver · Cost-Function and Measurement Estimation in Variational Algorithms · Parameterized Quantum Circuits and Ansatz Design. Leads to. Classical Optimizers for Variational Quantum Algorithms · Barren Plateaus in Variational Landscapes · Expressibility, Entangling Capability, and Trainability Trade-offs.

Ask the tutor: Ask me to walk through the light-cone derivation of the $0.6924$ bound, or to show why value concentration turns into a no-go theorem on large-girth graphs.

Is the 0.6924 ratio the performance you should expect from QAOA in practice?

No — it is a worst-case lower bound for depth one on 3-regular graphs, not a typical value. It certifies that level-1 QAOA cuts at least a $0.6924$ fraction of the maximum on any triangle-free 3-regular instance. On most instances the achieved ratio is higher, and it rises with depth: $0.7559$ at $p=2$ , $0.7924$ at $p=3$ . The bound matters because it is instance-agnostic and provable, an honest floor against Goemans–Williamson $0.8786$ — but treating it as expected performance undersells typical runs and hides that depth, not luck, closes the gap.

What is the difference between parameter concentration and value concentration?

Two objects that share a mechanism. Parameter concentration is about the optimizer's inputs: for fixed depth the best angles depend only on local subgraph types, so they are nearly identical across a family and learnable on small samples. Value concentration is about the output: $F_p/m$ has $O(1/\sqrt m)$ fluctuations across typical instances and shots. Parameter concentration is unambiguously good — it slashes training cost. Value concentration is double-edged: it makes estimation cheap, but on tree-like graphs it is exactly why the algorithm cannot tell instances apart, driving the no-go theorems.

Why does girth greater than 2p+1 make the light cones into trees?

A radius- $p$ ball can contain a cycle only if some cycle is short enough to fit, and the smallest cycle that closes within it has length at most $2p+1$ . Demand girth $g>2p+1$ and every radius- $p$ ball is acyclic — a $D$ -regular tree of depth $p$ , identical for every term. That uniformity is the point: each local expectation returns the same number, the objective becomes $m$ copies of one tree value with no global information, and QAOA at depth $p$ cannot distinguish graphs that differ only beyond distance $p$ . Increasing girth is how theorists build instances that expose the constant-depth limitation.

Does QAOA reach the true optimum if you make the depth large enough?

Yes, but as an existence statement, not a practical recipe. As $p\to\infty$ with slowly-varying angles, the alternating layers Trotterize a continuous adiabatic evolution from $|+\rangle^{\otimes n}$ to the ground state of the cost Hamiltonian, so $r\to1$ . What this does not tell you is how large $p$ must be — the adiabatic theorem ties the depth to the inverse spectral gap along the path, which can be exponentially small for hard instances. So $p\to\infty$ makes QAOA a universal optimizer in principle, while the open question stays quantitative: how slowly can $p$ grow with $n$ before the advantage evaporates?

Why are QAOA gradients cheap to compute despite the exponentially large Hilbert space?

Two facts combine. First, the parameter-shift rule: because $C$ and $B$ have eigenvalues $\pm1$ (up to shifts), the exact derivative of $F_p$ with respect to any angle is $\tfrac12[F_p(\theta+\tfrac\pi2)-F_p(\theta-\tfrac\pi2)]$ , two evaluations with no finite-difference error. Second, locality: differentiating inserts a generator at one layer, but only the part inside a term's light cone contributes, so each gradient is a sum over bounded-size subgraphs. Together they keep gradients tractable at fixed $p$ and degree — one reason QAOA avoids the worst of the barren-plateau problem, though growing $p$ reintroduces trainability concerns.

How does QAOA compare with the classical Goemans–Williamson algorithm on MaxCut?

Goemans–Williamson is a classical polynomial-time algorithm that rounds a semidefinite relaxation and guarantees a $0.8786$ ratio on any MaxCut instance — a high, uniform bar. Constant-depth QAOA on 3-regular graphs certifies less: $0.6924$ at $p=1$ , rising to $0.7924$ at $p=3$ , still below GW, so low-depth QAOA does not yet beat the best classical method. The interesting regime is asymptotic: since GW is fixed while the QAOA guarantee climbs with $p$ , the question is whether modestly growing depth lets QAOA overtake it — exactly what the limitation theorems constrain and current research probes.