Simple Algorithm
Quantum Computing · Rydberg State · 30 min

QAOA in Depth

Alternating operators, adiabatic limits and performance guarantees.

QAOA is simple to state and surprisingly hard to analyze: alternate a problem Hamiltonian with a mixer, pp times. At p→∞p\to\infty it inherits the adiabatic theorem; at p=1p=1 it can be solved in closed form; and at low depth its locality provably blinds it to global structure. This lesson works through all three regimes.

What you’ll learn

  • State QAOA precisely, prove monotonicity in pp, and prove that each edge term depends only on its radius-pp neighborhood.
  • Derive the p=1p=1 MaxCut value on triangle-free regular graphs and the 0.69240.6924 guarantee on 3-regular graphs.
  • Prove convergence to the optimum as p→∞p\to\infty via Trotterized adiabatic evolution and Perron–Frobenius.
  • Derive a locality obstruction on large-girth bipartite graphs and relate it to symmetry-protection results.

The ansatz and its light cone

Two more structural facts. With suitable Hamiltonians, the alternating-operator form is computationally universal (Lloyd, 2018; Morales, Biamonte & Zimborás, 2020). And even at p=1p=1, its output distribution cannot be sampled efficiently by a classical computer under standard complexity assumptions, unless the polynomial hierarchy collapses (Farhi & Harrow, 2016). Sampling hardness, however, says nothing about whether the samples are good cuts.

p = 1, exactly

For MaxCut at p=1p=1, the Heisenberg calculation from the Excited State lesson extends to any graph. For an edge (u,v)(u,v) with degrees du,dvd_u,d_v and λuv\lambda_{uv} triangles through it (Wang, Hadfield, Jiang & Rieffel, 2018):

⟨Cuv⟩=12+14sin⁡4β sin⁡γ(cos⁡du−1γ+cos⁡dv−1γ)−14sin⁡22β cos⁡du+dv−2−2λuvγ (1−cos⁡λuv2γ)\expval{C_{uv}}=\frac12+\frac14\sin4\beta\,\sin\gamma\big(\cos^{d_u-1}\gamma+\cos^{d_v-1}\gamma\big)-\frac14\sin^22\beta\,\cos^{d_u+d_v-2-2\lambda_{uv}}\gamma\,\big(1-\cos^{\lambda_{uv}}2\gamma\big)
DerivationDerivation sketch, and the 3-regular guarantee
  1. ⟨ZuYv⟩γ=−sin⁡γ cos⁡dv−1γ\expval{Z_uY_v}_\gamma=-\sin\gamma\,\cos^{d_v-1}\gamma

    The mixer maps ZuZv↦c2ZuZv+cs(ZuYv+YuZv)+s2YuYvZ_uZ_v\mapsto c^2Z_uZ_v+cs(Z_uY_v+Y_uZ_v)+s^2Y_uY_v (c=cos⁡2βc=\cos2\beta, s=sin⁡2βs=\sin2\beta). Through the cost layer, an operator OO that anticommutes with a set A\mathcal A of edge terms becomes O∏e∈A(cos⁡γ+isin⁡γ Ze)O\prod_{e\in\mathcal A}(\cos\gamma+i\sin\gamma\,Z_e), and only products reducing to XX's survive in ∣+⟩⊗n\ket{+}^{\otimes n}. For ZuYvZ_uY_v, A\mathcal A is the set of edges at vv: the (u,v)(u,v) factor must contribute its sin⁡\sin term and each of the other dv−1d_v-1 edges its cos⁡\cos term:

  2. ⟨Cuv⟩=12+12sin⁡4β sin⁡γcos⁡D−1γ\expval{C_{uv}}=\frac12+\frac12\sin4\beta\,\sin\gamma\cos^{D-1}\gamma

    The YuYvY_uY_v term survives only through pairs of edges (u,w),(v,w)(u,w),(v,w) to a common neighbor, i.e. triangles, and vanishes on triangle-free graphs. So for triangle-free DD-regular graphs

  3. ⟨Cuv⟩max⁡=12+12⋅13⋅23=12+133≈0.6925\expval{C_{uv}}_{\max}=\frac12+\frac12\cdot\frac{1}{\sqrt3}\cdot\frac23=\frac12+\frac{1}{3\sqrt3}\approx0.6925

    Maximize: β=π/8\beta=\pi/8, and ddγ(sin⁡γcos⁡D−1γ)=0\frac{d}{d\gamma}\big(\sin\gamma\cos^{D-1}\gamma\big)=0 gives tan⁡2γ=1D−1\tan^2\gamma=\frac{1}{D-1}. For D=3D=3, sin⁡γ=13\sin\gamma=\frac{1}{\sqrt3} and cos⁡2γ=23\cos^2\gamma=\frac23:

  4. Every edge is cut with probability about 0.69250.6925, while the maximum cut has at most ∣E∣\abs E edges, so the approximation ratio is at least 0.69250.6925 on triangle-free cubic graphs. Farhi, Goldstone & Gutmann (2014) also handled the edge types containing triangles (where the per-edge value changes, but the maximum cut is also smaller than ∣E∣\abs E) and proved a ratio of at least 0.69240.6924 for every 3-regular graph.

Predict before you look

Using the triangle-free formula, what is the optimal p=1p=1 edge-cut probability on triangle-free 4-regular graphs?

Show the answer

0.662

tan⁡2γ=13\tan^2\gamma=\frac13 gives sin⁡γ=12\sin\gamma=\frac12 and cos⁡3γ=(34)3/2≈0.650\cos^3\gamma=(\frac34)^{3/2}\approx0.650, so 12+12⋅12⋅0.650≈0.662\frac12+\frac12\cdot\frac12\cdot0.650\approx0.662. Higher degree means weaker p=1p=1 performance: for large DD the excess over 12\frac12 shrinks like 1/D1/\sqrt D (about 0.30/D0.30/\sqrt D).

AlgorithmGuaranteed MaxCut ratio
Uniformly random assignment1/21/2
QAOA, p=1p=1, 3-regular graphs≥0.6924\ge0.6924
Goemans–Williamson SDP rounding (1995), all graphs≈0.878\approx0.878; optimal for polynomial-time algorithms if the Unique Games Conjecture holds (Khot, Kindler, Mossel & O'Donnell, 2007)
Specialized classical algorithms for cubic graphs≈0.93\approx0.93 (Halperin, Livnat & Zwick, 2004)
Any polynomial-time algorithm, unless P = NPat most 16/17≈0.94116/17\approx0.941 (Håstad, 2001)
Low-depth QAOA guarantees lag far behind classical ones; the hope lies at larger pp, where analysis is hard.

The adiabatic limit

DerivationProof sketch
  1. H(0)=B,H(1)=CH(0)=B,\qquad H(1)=C

    Interpolate H(s)=(1−s)B+sCH(s)=(1-s)B+sC for s∈[0,1]s\in[0,1]. At s=0s=0, ∣+⟩⊗n\ket{+}^{\otimes n} is the highest eigenstate of BB; at s=1s=1, the highest eigenstates of CC are optimal bit strings.

  2. Δ(s)=Emax⁡(s)−E2(s)>0(0≤s<1)\Delta(s)=E_{\max}(s)-E_2(s)>0\qquad(0\le s<1)

    For s<1s<1, H(s)H(s) has non-negative off-diagonal entries in the computational basis and is irreducible, because BB connects every bit string to every other through bit flips. By Perron–Frobenius its top eigenvalue is simple, so the gap below it is positive on [0,1)[0,1):

  3. T  ≫  max⁡s∥∂sH∥Δ(s)2T\;\gg\;\max_s\frac{\norm{\partial_sH}}{\Delta(s)^2}

    By the adiabatic theorem, evolving under H(t/T)H(t/T) keeps the state in the top eigenspace provided (up to logarithmic factors and endpoint care, since the gap may close at s=1s=1 where CC is degenerate, harmlessly, as every top eigenstate of CC is optimal)

  4. e−iδt H(sk)≈e−iδt(1−sk)B e−iδt skC,γk=δt sk,βk=δt (1−sk)e^{-i\delta t\,H(s_k)}\approx e^{-i\delta t(1-s_k)B}\,e^{-i\delta t\,s_kC},\qquad\gamma_k=\delta t\,s_k,\quad\beta_k=\delta t\,(1-s_k)

    Discretize the evolution into pp steps and split each with the Lie–Trotter formula:

  5. As p→∞p\to\infty (with T→∞T\to\infty and δt→0\delta t\to0) the Trotter error vanishes, so some QAOA angles reproduce the adiabatic output and Fp→max⁡CF_p\to\max C. Since MpM_p is at least these values, Mp→max⁡CM_p\to\max C. □\square

The catch is the gap. For hard instances Δ(s)\Delta(s) can be exponentially small, for example through perturbative level crossings in random instances (Altshuler, Krovi & Roland, 2010), making the required pp exponential. At moderate pp, QAOA is better viewed as a variational shortcut: optimized angles often beat a Trotterized adiabatic schedule of the same depth, but without a general guarantee.

Locality obstructions

Locality cuts both ways: it makes low-depth QAOA analyzable, and it makes it blind. Within radius pp, the algorithm cannot tell a bipartite graph from a random one whose neighborhoods look the same.

Stronger results push the obstruction to depths growing with nn. Bravyi, Kliesch, Koenig & Tang (2020) used the Z2\mathbb Z_2 symmetry of QAOA states (global bit flip) to show that on families of bipartite DD-regular graphs, QAOAp_p achieves ratio at most 56+O(1/D)\frac56+O(1/\sqrt D) for all pp below a threshold growing logarithmically with nn (roughly log⁡n/D\log n/D). They also proposed recursive QAOA, which uses measured correlations to eliminate variables one at a time and sidesteps the obstruction numerically. Farhi, Gamarnik & Gutmann (2020) showed, via the overlap gap property, that for maximum independent set on random sparse graphs QAOA needs depth growing with nn: it "needs to see the whole graph".

Check your understanding

Why does the locality obstruction not contradict lim⁡p→∞Mp=max⁡C\lim_{p\to\infty}M_p=\max C?

  1. The obstruction holds for fixed pp (or pp growing slowly with nn), while convergence may require pp to grow with nn
  2. Bipartite graphs are excluded from the convergence theorem
  3. The convergence theorem assumes triangle-free graphs
  4. The obstruction concerns sampling, not expectation values
Show the answer

A. The obstruction holds for fixed pp (or pp growing slowly with nn), while convergence may require pp to grow with nn

Once the light cone covers the graph, at depths comparable to its diameter (∼log⁡n\sim\log n for random regular graphs), QAOA can "see" bipartiteness, and the adiabatic argument may need much larger pp still. The obstructions bound what low depth can do.

Key takeaways

  • QAOAp_p is monotone in pp and local: each edge term depends only on its radius-pp neighborhood, so fixed-pp performance is classically computable.
  • At p=1p=1 on triangle-free DD-regular graphs, ⟨Cuv⟩max⁡=12+12max⁡γsin⁡γcos⁡D−1γ\langle C_{uv}\rangle_{\max}=\frac12+\frac12\max_\gamma\sin\gamma\cos^{D-1}\gamma; for D=3D=3 this is 0.69250.6925, behind the ≥0.6924\ge0.6924 guarantee.
  • As p→∞p\to\infty, Trotterized adiabatic evolution with a Perron–Frobenius gap gives Mp→max⁡CM_p\to\max C, but small gaps can make the needed pp exponential.
  • Low depth is blind to global structure: on large-girth bipartite graphs the ratio is at most 12+O(1/D)\frac12+O(1/\sqrt D), and symmetry protection extends obstructions to p∼log⁡np\sim\log n.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why is Mp+1≥MpM_{p+1}\ge M_p?

  1. Deeper circuits are less affected by noise
  2. Setting the extra two angles to zero reproduces any QAOAp_p state
  3. The adiabatic theorem guarantees it
  4. Because CC is diagonal
Show the answer

B. Setting the extra two angles to zero reproduces any QAOAp_p state

QAOAp_p states form a subset of QAOAp+1_{p+1} states (take γp+1=βp+1=0\gamma_{p+1}=\beta_{p+1}=0), so the maximum cannot decrease. On real hardware, deeper circuits are noisier, and measured performance can drop.

Question 2

At p=2p=2 on a 3-regular graph, the expectation of one edge term depends on at most how many vertices?

  1. 6
  2. 14
  3. 30
  4. all nn
Show the answer

B. 14

On the tree: the edge's 2 endpoints, their 2⋅2=42\cdot2=4 other neighbors, and those vertices' 4⋅2=84\cdot2=8 further neighbors, for 2+4+8=142+4+8=14 (fewer if cycles close up). In general the count is 2∑k=0p(D−1)k2\sum_{k=0}^{p}(D-1)^k.

Question 3

Where does the number 0.69240.6924 come from?

  1. The Goemans–Williamson guarantee on cubic graphs
  2. The fraction of edges cut by a random assignment on 3-regular graphs
  3. The limit of QAOA as p→∞p\to\infty on 3-regular graphs
  4. The optimal p=1p=1 edge-cut probability on triangle-free 3-regular graphs, 12+133\frac12+\frac{1}{3\sqrt3}, combined with MaxCut≤∣E∣\text{MaxCut}\le\abs E (and a check of edges in triangles)
Show the answer

D. The optimal p=1p=1 edge-cut probability on triangle-free 3-regular graphs, 12+133\frac12+\frac{1}{3\sqrt3}, combined with MaxCut≤∣E∣\text{MaxCut}\le\abs E (and a check of edges in triangles)

Maximizing 12+12sin⁡4βsin⁡γcos⁡2γ\frac12+\frac12\sin4\beta\sin\gamma\cos^2\gamma gives 12+133≈0.6925\frac12+\frac{1}{3\sqrt3}\approx0.6925 per edge; since the optimum cuts at most every edge, the ratio is at least that.

Question 4

In the adiabatic proof sketch, what guarantees a positive gap for 0≤s<10\le s<1?

  1. Perron–Frobenius: H(s)H(s) has non-negative off-diagonal entries that connect all bit strings
  2. The cost function being integer-valued
  3. The Trotter product formula
  4. The graph being bipartite
Show the answer

A. Perron–Frobenius: H(s)H(s) has non-negative off-diagonal entries that connect all bit strings

Non-negative off-diagonals plus irreducibility make the top eigenvalue simple. That does not make the gap large: it can be exponentially small, which is what makes hard instances hard.

Further reading

  • E. Farhi, J. Goldstone & S. Gutmann, "A quantum approximate optimization algorithm", arXiv:1411.4028 (2014).
  • Z. Wang, S. Hadfield, Z. Jiang & E. G. Rieffel, "Quantum approximate optimization algorithm for MaxCut: a fermionic view", Phys. Rev. A 97, 022304 (2018).
  • S. Bravyi, A. Kliesch, R. Koenig & E. Tang, "Obstacles to variational quantum optimization from symmetry protection", Phys. Rev. Lett. 125, 260505 (2020).
  • E. Farhi, D. Gamarnik & S. Gutmann, "The quantum approximate optimization algorithm needs to see the whole graph: a typical case" (2020).
  • A. Dembo, A. Montanari & S. Sen, "Extremal cuts of sparse random graphs", Annals of Probability (2017).