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, times. At it inherits the adiabatic theorem; at 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 , and prove that each edge term depends only on its radius- neighborhood.
- Derive the MaxCut value on triangle-free regular graphs and the guarantee on 3-regular graphs.
- Prove convergence to the optimum as 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 , 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 , the Heisenberg calculation from the Excited State lesson extends to any graph. For an edge with degrees and triangles through it (Wang, Hadfield, Jiang & Rieffel, 2018):
The mixer maps (, ). Through the cost layer, an operator that anticommutes with a set of edge terms becomes , and only products reducing to 's survive in . For , is the set of edges at : the factor must contribute its term and each of the other edges its term:
The term survives only through pairs of edges to a common neighbor, i.e. triangles, and vanishes on triangle-free graphs. So for triangle-free -regular graphs
Maximize: , and gives . For , and :
Every edge is cut with probability about , while the maximum cut has at most edges, so the approximation ratio is at least 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 ) and proved a ratio of at least for every 3-regular graph.
Using the triangle-free formula, what is the optimal edge-cut probability on triangle-free 4-regular graphs?
Show the answer
0.662
gives and , so . Higher degree means weaker performance: for large the excess over shrinks like (about ).
| Algorithm | Guaranteed MaxCut ratio |
|---|---|
| Uniformly random assignment | |
| QAOA, , 3-regular graphs | |
| Goemans–Williamson SDP rounding (1995), all graphs | ; optimal for polynomial-time algorithms if the Unique Games Conjecture holds (Khot, Kindler, Mossel & O'Donnell, 2007) |
| Specialized classical algorithms for cubic graphs | (Halperin, Livnat & Zwick, 2004) |
| Any polynomial-time algorithm, unless P = NP | at most (Håstad, 2001) |
The adiabatic limit
Interpolate for . At , is the highest eigenstate of ; at , the highest eigenstates of are optimal bit strings.
For , has non-negative off-diagonal entries in the computational basis and is irreducible, because 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 :
By the adiabatic theorem, evolving under keeps the state in the top eigenspace provided (up to logarithmic factors and endpoint care, since the gap may close at where is degenerate, harmlessly, as every top eigenstate of is optimal)
Discretize the evolution into steps and split each with the Lie–Trotter formula:
As (with and ) the Trotter error vanishes, so some QAOA angles reproduce the adiabatic output and . Since is at least these values, .
The catch is the gap. For hard instances can be exponentially small, for example through perturbative level crossings in random instances (Altshuler, Krovi & Roland, 2010), making the required exponential. At moderate , 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 , 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 . Bravyi, Kliesch, Koenig & Tang (2020) used the symmetry of QAOA states (global bit flip) to show that on families of bipartite -regular graphs, QAOA achieves ratio at most for all below a threshold growing logarithmically with (roughly ). 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 : it "needs to see the whole graph".
Why does the locality obstruction not contradict ?
- The obstruction holds for fixed (or growing slowly with ), while convergence may require to grow with
- Bipartite graphs are excluded from the convergence theorem
- The convergence theorem assumes triangle-free graphs
- The obstruction concerns sampling, not expectation values
Show the answer
A. The obstruction holds for fixed (or growing slowly with ), while convergence may require to grow with
Once the light cone covers the graph, at depths comparable to its diameter ( for random regular graphs), QAOA can "see" bipartiteness, and the adiabatic argument may need much larger still. The obstructions bound what low depth can do.
Key takeaways
- QAOA is monotone in and local: each edge term depends only on its radius- neighborhood, so fixed- performance is classically computable.
- At on triangle-free -regular graphs, ; for this is , behind the guarantee.
- As , Trotterized adiabatic evolution with a Perron–Frobenius gap gives , but small gaps can make the needed exponential.
- Low depth is blind to global structure: on large-girth bipartite graphs the ratio is at most , and symmetry protection extends obstructions to .
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why is ?
- Deeper circuits are less affected by noise
- Setting the extra two angles to zero reproduces any QAOA state
- The adiabatic theorem guarantees it
- Because is diagonal
Show the answer
B. Setting the extra two angles to zero reproduces any QAOA state
QAOA states form a subset of QAOA states (take ), so the maximum cannot decrease. On real hardware, deeper circuits are noisier, and measured performance can drop.
At on a 3-regular graph, the expectation of one edge term depends on at most how many vertices?
- 6
- 14
- 30
- all
Show the answer
B. 14
On the tree: the edge's 2 endpoints, their other neighbors, and those vertices' further neighbors, for (fewer if cycles close up). In general the count is .
Where does the number come from?
- The Goemans–Williamson guarantee on cubic graphs
- The fraction of edges cut by a random assignment on 3-regular graphs
- The limit of QAOA as on 3-regular graphs
- The optimal edge-cut probability on triangle-free 3-regular graphs, , combined with (and a check of edges in triangles)
Show the answer
D. The optimal edge-cut probability on triangle-free 3-regular graphs, , combined with (and a check of edges in triangles)
Maximizing gives per edge; since the optimum cuts at most every edge, the ratio is at least that.
In the adiabatic proof sketch, what guarantees a positive gap for ?
- Perron–Frobenius: has non-negative off-diagonal entries that connect all bit strings
- The cost function being integer-valued
- The Trotter product formula
- The graph being bipartite
Show the answer
A. Perron–Frobenius: 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).