Quantum Approximate Optimization Algorithm

The Quantum Approximate Optimization Algorithm is the sharpest test case for the promise of near-term quantum computing: can a shallow, noisy, gate-based circuit solve combinatorial optimization problems better than a classical machine? Introduced by Edward Farhi, Jeffrey Goldstone and Sam Gutmann in 2014, QAOA belongs to the family of variational quantum algorithms — a parameterized quantum circuit prepares a trial state, a measurement estimates the expected cost, and a classical optimizer nudges the parameters in a feedback loop. What sets QAOA apart from a generic variational ansatz is that its structure is not arbitrary: it is a Trotterized, bang-bang caricature of quantum annealing, in which the smooth adiabatic schedule that slowly turns a mixer into a cost Hamiltonian is chopped into $p$ alternating maximal pulses whose durations become the variational parameters. Concretely one encodes a classical objective $C(z)$ over bitstrings $z\in\{0,1\}^n$ into a diagonal cost operator $H_C$ with $H_C|z\rangle=C(z)|z\rangle$ , and pairs it with a non-commuting mixer $H_B=\sum_i X_i$ that hops amplitude between neighbouring strings. The depth- $p$ state $|\gamma,\beta\rangle$ is built by alternately applying $e^{-i\gamma_k H_C}$ and $e^{-i\beta_k H_B}$ to the uniform superposition, and the classical loop maximizes $F_p=\langle\gamma,\beta|H_C|\gamma,\beta\rangle$ over just $2p$ angles. Two theorems anchor the whole subject. First, an adiabatic limit: as $p\to\infty$ the ansatz can reproduce slow annealing, so the optimal $F_p$ converges to the true maximum. Second, locality: at fixed $p$ each edge's expectation depends only on a radius- $p$ neighbourhood, which makes shallow QAOA analytically tractable on bounded-degree graphs and, at the same time, provably blind to global structure. This article develops the formalism, derives the $p=1$ MaxCut result that gives the celebrated $0.6924$ guarantee, and lays out both the promise and the known obstructions.

Key takeaways

QAOA is a hybrid quantum–classical algorithm: it prepares $|\gamma,\beta\rangle$ by alternating a cost unitary $e^{-i\gamma_k H_C}$ and a mixer unitary $e^{-i\beta_k H_B}$ for $p$ rounds from $|+\rangle^{\otimes n}$ , then classically optimizes the $2p$ angles to maximize $\langle H_C\rangle$ .
The objective is encoded in a diagonal Ising-type cost operator $H_C$ ; for MaxCut $H_C=\sum_{\langle i,j\rangle}\tfrac12(I-Z_iZ_j)$ counts cut edges, and its largest eigenvalue is the optimum.
At $p=1$ on 3-regular MaxCut, QAOA provably reaches approximation ratio $r\ge0.6924$ , beating the random-guess value $0.5$ ; as $p\to\infty$ the ansatz recovers the adiabatic theorem and converges to the exact optimum.
Locality gives a light cone: each edge term spreads only to graph-distance $p$ , so shallow QAOA is analytically computable on small subgraphs — but also cannot "see" the whole graph, which is the root of its worst-case obstructions.
The catch is the classical outer loop: the landscape $F_p(\gamma,\beta)$ is non-convex and can suffer barren plateaus, so "deeper is better" holds for the ideal optimum, not for a fixed optimizer budget on hardware.
Key idea: QAOA replaces the smooth adiabatic schedule of quantum annealing with a finite bang-bang sequence of alternating cost and mixer unitaries whose pulse durations are variational parameters — turning an analog control problem into a low-dimensional classical optimization over $2p$ angles while retaining a provable adiabatic limit.

Where this lives today

QAOA is the most-run optimization algorithm on today's quantum hardware because its circuits are shallow and structured. Superconducting and trapped-ion processors implement the cost layer natively — the diagonal $Z_iZ_j$ terms map onto two-qubit entangling gates — and groups at Google, IBM, IonQ and QuEra have executed QAOA on tens to low hundreds of qubits as a stress test for gate fidelity, connectivity and error mitigation. Two research fronts dominate. The first is constrained QAOA: the Quantum Alternating Operator Ansatz swaps the $X$ -mixer for constraint-preserving mixers (XY-mixers that conserve Hamming weight) so the state never leaves the feasible subspace, handling Max- $k$ -Vertex-Cover, cardinality-constrained portfolios and routing without exploding penalty terms. The second is the advantage question: for MaxCut on high-girth regular graphs the overlap-gap property provably caps constant-depth QAOA, and strong classical algorithms (Goemans–Williamson at $0.878$ ) remain hard to beat at accessible depths. QAOA is also the canonical laboratory for barren plateaus, parameter concentration (good angles transfer across instances, so one can pre-train) and noise resilience — feeding the broader case for fault tolerance and magic-state distillation at scale.

The physical picture

Start with the uniform superposition $|+\rangle^{\otimes n}$ , equal amplitude on every one of the $2^n$ candidate bitstrings. The cost layer $e^{-i\gamma H_C}$ is diagonal: it stamps each bitstring $z$ with a phase $e^{-i\gamma C(z)}$ proportional to its objective value, separating good and bad solutions in phase but not yet in probability. The mixer $e^{-i\beta H_B}$ then makes those phases interfere by hopping amplitude between strings that differ by one bit flip. Choose the angles well and the interference is constructive on high-value strings and destructive on low-value ones; sampling the final state returns good solutions with boosted probability. QAOA is, in one line, a machine for turning objective-value phases into measurable amplitude. The deeper reading is bang-bang control of an annealer. Quantum annealing prepares the easy ground state of $H_B$ and then slowly turns $H_B$ off and $H_C$ on; go slowly enough and it ends in the ground state that encodes the optimum. QAOA chops that smooth schedule into $p$ alternating full-strength pulses and lets a classical optimizer choose their durations. The first figure contrasts the two schedules and shows how a QAOA layer is exactly one Trotter step of the anneal.

Figure

The QAOA feedback loop: a quantum circuit prepares the state by alternating a cost layer and a mixer layer p times from the uniform superposition, measurement estimates the expected cost F_p = ⟨H_C⟩, and a classical optimizer updates the 2p angles γ and β until F_p is maximized

Locality is both the secret to analytic tractability and the source of the deepest limitation. Because $H_B$ and $H_C$ are sums of geometrically local terms, after $p$ layers the Heisenberg-evolved operator $Z_iZ_j$ spreads only to qubits within graph-distance $p$ of the edge. So $\langle H_C\rangle$ splits into independent local contributions computable on small subgraphs — but by the same token, constant- $p$ QAOA cannot distinguish two graphs that look identical within radius $p$ , which is exactly what obstruction results exploit. The payoff of the local calculation is a hard number: the second figure shows how the achievable approximation ratio climbs from the random-guess floor at $p=0$ through the Farhi–Goldstone–Gutmann guarantee at $p=1$ up toward the exact optimum as $p\to\infty$ .

Figure

Approximation ratio r versus depth p for 3-regular triangle-free MaxCut: depth p = 0 gives the random-guess value r = 0.50, the p = 1 Farhi–Goldstone–Gutmann optimum gives r ≥ 0.6924, and as p grows the Trotterized adiabatic schedule drives r toward the exact optimum r = 1.00

The core equations

The whole algorithm is one state and one number to maximize. The state is built by alternating two unitaries generated by non-commuting Hamiltonians, starting from the uniform superposition, and the number is the expected cost of that state.

|\gamma,\beta\rangle = e^{-i\beta_p H_B}e^{-i\gamma_p H_C}\cdots e^{-i\beta_1 H_B}e^{-i\gamma_1 H_C}\,|+\rangle^{\otimes n} \qquad (1)

where: $p$ — number of alternating layers, the circuit-depth parameter; $H_C$ — diagonal cost Hamiltonian, $H_C|z\rangle=C(z)|z\rangle$ ; $H_B$ — mixer, standardly $H_B=\sum_{i=1}^n X_i$ ; $\gamma_k,\beta_k$ — the $2p$ real variational angles; $|+\rangle^{\otimes n}$ — the uniform superposition, ground state of $-H_B$ . Read it right-to-left: phase by cost, mix, repeat $p$ times. The classical outer loop maximizes the expected cost of this state over the angles. Because $H_C$ is diagonal, this expectation is just the average objective value weighted by the measured output distribution.

F_p(\gamma,\beta) = \langle\gamma,\beta|\,H_C\,|\gamma,\beta\rangle, \qquad (\gamma^*,\beta^*)=\arg\max_{\gamma,\beta}\,F_p \qquad (2)

where: $F_p$ — expected cost, the function the classical optimizer climbs; $(\gamma^*,\beta^*)$ — the optimal angle set found by a routine such as gradient ascent, COBYLA, or Nelder–Mead. Estimating $F_p$ needs many circuit repetitions and measurements; updating the angles is classical. For the canonical benchmark, MaxCut, the cost operator counts the edges that a bit assignment cuts. Each edge contributes a projector that reads $1$ when its endpoints disagree and $0$ when they agree.

H_C = \sum_{\langle i,j\rangle\in E}\tfrac12\left(I - Z_iZ_j\right) \qquad (3)

where: $E$ — edge set, one term per edge; $Z_i$ — Pauli- $Z$ on qubit $i$ , eigenvalue $+1$ for bit $0$ and $-1$ for bit $1$ ; $\tfrac12(I-Z_iZ_j)$ — the cut projector, $1$ if endpoints differ. The largest eigenvalue of $H_C$ equals the size of the maximum cut. Since $|\gamma,\beta\rangle$ is just one state in Hilbert space, its expected cost can never exceed the largest eigenvalue — the variational (Rayleigh-quotient) bound. Dividing by that optimum defines the figure of merit.

\langle H_C\rangle \le C_{\max}=\lambda_{\max}(H_C), \qquad r=\frac{\langle H_C\rangle}{C_{\max}} \qquad (4)

where: $C_{\max}$ — the true optimum, the largest eigenvalue of $H_C$ ; $\lambda_{\max}$ — largest eigenvalue; $r$ — approximation ratio, $0\le r\le1$ , with $r=1$ iff the trial state is the optimal eigenstate. Equality in the bound holds only at the true optimum, which QAOA reaches only as $p\to\infty$ . The mixer acts qubit-by-qubit as a rotation about the $X$ -axis, and the exponential of a Pauli collapses to a simple cosine–sine form because $X$ squares to the identity.

e^{-i\beta X}=\cos\beta\,I - i\sin\beta\,X \qquad (5)

where: $\beta$ — mixer angle; $X$ — Pauli- $X$ , the bit-flip generator. This is (up to a global convention) the single-qubit rotation $R_x(2\beta)$ ; it is what physically hops amplitude between neighbouring bitstrings. At depth one the expectation of each edge, computed in the Heisenberg picture, closes into an elementary trigonometric formula that depends only on the local graph. For a $D$ -regular triangle-free graph it is a single term.

\langle Z_uZ_v\rangle_{p=1} = \sin(4\beta)\,\sin\gamma\,\cos^{\,D-1}\!\gamma \qquad (D\text{-regular, triangle-free}) \qquad (6)

where: $D$ — common degree of the endpoints; the exponent $D-1$ counts the other neighbours of each endpoint, whose incident cost terms each contribute a factor $\cos\gamma$ . The per-edge cut value is $\tfrac12(1-\langle Z_uZ_v\rangle)$ , and maximizing it drives the $0.6924$ guarantee.

Derivation AThe adiabatic limit — QAOA reaches the optimum as depth grows

The goal is to prove that the best achievable QAOA objective converges to the true maximum, $\max_{\gamma,\beta}F_p\to C_{\max}$ as $p\to\infty$ . The strategy is to exhibit one particular family of angles — not necessarily the optimal one — that makes the QAOA circuit approximate the slow adiabatic evolution from the mixer to the cost Hamiltonian. Since the adiabatic theorem guarantees that slow evolution ends in the ground state that encodes the optimum, and since the QAOA optimizer can only do at least as well as any specific angle choice, the boxed limit follows. The result is what makes QAOA a principled ansatz rather than an arbitrary circuit, and it is also why QAOA is universal for quantum computation in the unbounded-depth limit.

Result. $\displaystyle \lim_{p\to\infty}\max_{\gamma,\beta}F_p(\gamma,\beta)=C_{\max}$ .

Step 1. Define the interpolating Hamiltonian $H(s)=(1-s)H_B+sH_C$ for $s\in[0,1]$ . At $s=0$ its ground state is $|+\rangle^{\otimes n}$ , exactly the QAOA initial state; at $s=1$ its extremal eigenstate of $H_C$ encodes the optimal bitstring. Why: this straight-line path connects the state we can easily prepare to the state we want, with $H_B$ and $H_C$ as its two endpoints — the same two operators QAOA alternates.

Step 2. Invoke the adiabatic theorem: if $H(s)$ is traversed over a total time $T$ that is large compared with $1/\Delta_{\min}^2$ , where $\Delta_{\min}$ is the smallest spectral gap along the path, the system stays in the instantaneous ground state and ends at the optimum. Why: slow driving forbids transitions across an open gap, so the final state is the encoded solution — this is the entire logic of quantum annealing.

Step 3. Trotterize the time-ordered evolution into $p$ short steps of size $\Delta t=T/p$ , giving $U(T)\approx\prod_{k=1}^{p}e^{-i\Delta t(1-s_k)H_B}\,e^{-i\Delta t\,s_k H_C}$ . This is precisely the QAOA layer structure under the identification $\beta_k=\Delta t(1-s_k)$ and $\gamma_k=\Delta t\,s_k$ . Why: a first-order product formula turns the continuous schedule into exactly the alternating cost-then-mixer pulses QAOA applies, so annealing is a special angle assignment inside the QAOA family.

Step 4. Conclude by nesting the inequalities. The optimal QAOA value is at least the value at these annealing-derived angles, $\max_{\gamma,\beta}F_p\ge\langle U(T)+|H_C|U(T)+\rangle$ , and the right side tends to $C_{\max}$ as $T$ and $p$ grow together with the gap kept open; since $F_p\le C_{\max}$ always, the limit is exactly $C_{\max}$ . Why: the variational optimizer can only improve on any fixed schedule, so QAOA inherits the annealer's asymptotic optimality — and, because arbitrary time evolution can be Trotterized this way, universality too. *Why both errors vanish: the Trotter error scales as $O(T^2/p)\to0$ and the adiabatic error as $O(1/(T\Delta_{\min}^2))\to0$ , so in the joint limit $p,T\to\infty$ both go to zero, confirming the convergence to $C_{\max}$ .*

Go deeper · Derivation B · 2 minThe p = 1 MaxCut edge expectation on a triangle-free graph

Derivation BThe p = 1 MaxCut edge expectation on a triangle-free graph

The goal is to compute one edge's contribution to $F_1$ for MaxCut and recover the Farhi–Goldstone–Gutmann formula $\langle Z_uZ_v\rangle=\sin4\beta\sin\gamma\cos^{D-1}\gamma$ for a $D$ -regular triangle-free graph. The method is to move the operator $Z_uZ_v$ into the Heisenberg picture, conjugating first by the mixer and then by the cost layer, and to use locality — the light cone reaches only nearest neighbours at $p=1$ — to keep the bookkeeping finite. Evaluating the resulting operator on $|+\rangle^{\otimes n}$ and discarding every term with a leftover $Z$ (which averages to zero) leaves the single surviving trigonometric product, whose maximization gives the celebrated $0.6924$ ratio for $D=3$ .

Result. $\langle Z_uZ_v\rangle_{p=1}=\sin(4\beta)\,\sin\gamma\,\cos^{\,D-1}\!\gamma$ for a $D$ -regular triangle-free graph.

Step 1. Conjugate by the mixer. Each $X_i$ rotates $Z_i$ within its own algebra, $e^{i\beta H_B}Z_ie^{-i\beta H_B}=\cos2\beta\,Z_i+\sin2\beta\,Y_i$ , so $Z_uZ_v$ becomes $(\cos2\beta\,Z_u+\sin2\beta\,Y_u)(\cos2\beta\,Z_v+\sin2\beta\,Y_v)$ . Why: only $X_u$ and $X_v$ act non-trivially on $Z_uZ_v$ , so this step is exact and touches only the two endpoints — locality at work.

Step 2. Conjugate by the cost layer. The pure- $Z$ pieces commute with the diagonal $H_C$ and pass through untouched, while each $Y$ factor is rotated by every cost term sharing its qubit, picking up a factor $\cos\gamma$ per incident edge; triangle-freeness means $u$ and $v$ share no neighbour, so there are no cross-terms. Why: a $Y$ on qubit $u$ fails to commute with the $Z_uZ_w$ term of every neighbour $w$ , and the exponential of that mismatch is exactly a $\cos\gamma$ weight — this is where the graph degree enters.

Step 3. Evaluate on $|+\rangle^{\otimes n}$ . Since $\langle+|Z|+\rangle=0$ and $\langle+|Y|+\rangle=0$ but $\langle+|X|+\rangle=1$ , every surviving term must reduce to $X$ -type operators on the initial state; the only such survivor is the cross term with one $Z$ and one $Y$ endpoint. Why: the uniform superposition is the $+1$ eigenstate of every $X_i$ , so it filters the operator down to its $X$ -aligned part and kills the rest.

Step 4. Collect the surviving factors: $\sin2\beta\cos2\beta$ from the two endpoints combines as $\tfrac12\sin4\beta$ (doubled by the two symmetric cross terms into $\sin4\beta$ ), $\sin\gamma$ from the endpoint edge, and $\cos^{D-1}\gamma$ from the $D-1$ other neighbours of each endpoint, giving $\langle Z_uZ_v\rangle=\sin4\beta\sin\gamma\cos^{D-1}\gamma$ . The per-edge cut value is then $\tfrac12(1-\sin4\beta\sin\gamma\cos^{D-1}\gamma)$ . Why: assembling the weights reproduces the FGG edge formula, and maximizing the cut over $\gamma,\beta$ at $D=3$ yields the number quoted in every QAOA paper. *Why the number is $0.6924$ : at $D=3$ , maximizing $\sin\gamma\cos^2\gamma$ gives $2/(3\sqrt3)=0.38490$ at $\sin^2\gamma=1/3$ ; with $\sin4\beta=1$ the cut fraction is $\tfrac12(1+0.38490)=0.69245$ , so $r\ge0.6924$ .*

Go deeper · Derivation C · 2 minThe light cone — why shallow QAOA is local

Derivation CThe light cone — why shallow QAOA is local

The goal is to show that conjugating a two-qubit operator $Z_iZ_j$ by $p$ QAOA layers spreads its support only to qubits within graph-distance $p$ of the edge, so that each term of $\langle H_C\rangle$ is computable on a bounded subgraph. The method is to track operator support layer by layer: the mixer never enlarges support because it is single-qubit, while each cost layer can grow support by exactly one graph step through its two-qubit $ZZ$ terms. Iterating $p$ times confines the Heisenberg-evolved operator to a radius- $p$ ball. This single fact is double-edged — it makes shallow QAOA analytically and classically tractable on bounded-degree graphs, and it is simultaneously the mechanism behind the algorithm's worst-case obstructions.

Result. $\operatorname{supp}\!\big(U^\dagger Z_iZ_j\,U\big)\subseteq B_p(i)\cup B_p(j)$ , the radius- $p$ balls around the endpoints.

Step 1. One mixer layer, $e^{i\beta H_B}\,O\,e^{-i\beta H_B}$ , rotates each qubit's operator inside its own single-qubit algebra without touching any other qubit. Why: $H_B=\sum_k X_k$ is a sum of commuting single-qubit terms, so it can rotate $Z\to Y$ locally but can never create a new multi-qubit correlation — support is unchanged.

Step 2. One cost layer, $e^{i\gamma H_C}\,O\,e^{-i\gamma H_C}$ , can grow the support of an operator on qubit $k$ to also cover qubit $l$ whenever the edge $(k,l)$ appears in $H_C$ . Why: the $Z_kZ_l$ term fails to commute with a $Y_k$ , and conjugation produces a term acting on both $k$ and $l$ — support advances by one graph step per cost layer.

Step 3. Iterate $p$ alternations. Support grows by at most one graph step per cost layer, so after $p$ layers it is contained in $\{m:d(m,\{i,j\})\le p\}$ . Why: the mixer never spreads support and each cost layer spreads it by one, giving a strict light cone of radius $p$ — a discrete Lieb–Robinson bound for finite-depth circuits.

Step 4. Read off both consequences. On a bounded-degree graph the ball $B_p$ has size independent of $n$ , so $\langle Z_iZ_j\rangle$ depends only on the local subgraph's degrees and cycle counts and can be evaluated exactly; but two graphs identical within radius $p$ are indistinguishable to depth- $p$ QAOA. Why: the same locality that lets you compute the expectation on a laptop also blinds constant-depth QAOA to global structure, which is what obstruction theorems exploit. *This finite-depth light-cone argument has two faces: the tractability side reproduces the FGG local-subgraph computation, and the limitation side underlies the Bravyi–Kliesch–Koenig–Tang and overlap-gap obstructions for low-depth QAOA on random instances.*

Limiting cases

QAOA is sharply characterized in a handful of regimes that bracket everything between the trivial floor and the exact ceiling.

Case	Result	Meaning
$p=0$ (no layers)	$F_0=\langle+\|^{\otimes n}H_C\|+\rangle^{\otimes n}=\mathbb{E}_z[C(z)]$	The uniform superposition gives the random-assignment average; for MaxCut this is $\\|E\\|/2$ , approximation ratio $0.5$ .
$p\to\infty$ (adiabatic limit)	$\lim_{p\to\infty}\max_{\gamma,\beta}F_p=C_{\max}$	Trotterized slow annealing recovers the exact optimum; QAOA becomes universal and asymptotically exact.
Fixed $p$ , bounded degree	$\langle Z_iZ_j\rangle$ set by the radius- $p$ subgraph of edge $(i,j)$	Locality and concentration: expectations are computable on local neighbourhoods and often concentrate across instances.
$p=1$ , 3-regular MaxCut	approximation ratio $\ge0.6924$	The original Farhi–Goldstone–Gutmann worst-case guarantee for the simplest nontrivial instance class.
High girth, low $p$	$r$ capped below $1$ by the overlap-gap property	Local view cannot exploit global structure of hard spin-glass instances; a genuine obstruction, not a numerical artefact.

Common trapThe myth that QAOA always improves as you add layers

It is tempting to read the adiabatic limit as a promise that deeper circuits always help, and to assume the classical outer loop is a solved problem. Both are false in practice. The ideal optimum $\max_{\gamma,\beta}F_p$ is indeed non-decreasing in $p$ , because a $p$ -layer circuit contains every $(p{-}1)$ -layer circuit as a special case (set the extra angles to zero). But the achieved value with a finite optimizer budget can stagnate or even regress: the landscape $F_p(\gamma,\beta)$ is non-convex, riddled with local optima, and for many ansätze and cost functions it exhibits barren plateaus where gradients vanish exponentially in system size, so a gradient-based optimizer wanders on an almost-flat surface. A second, subtler trap: $H_C$ is diagonal, so "measuring the cost" is classically trivial — but $\langle H_C\rangle$ is only an average. Maximizing the average is not the same as producing the optimum; you still have to sample the final state many times to actually extract a high-value bitstring.

Worked examples

1 · MaxCut on the 6-cycle at p = 1 (fully worked)

Take the ring graph $C_6$ — six vertices $0,1,\dots,5$ in a cycle, so every vertex has degree $D=2$ and there are no triangles. Run QAOA at depth $p=1$ . Find the optimal angles, the best expected cut $F_1$ , and the approximation ratio.

Step 1. Fix the target. $C_6$ is bipartite, so the maximum cut colours the ring alternately and cuts every edge: $C_{\max}=|E|=6$ . This is the denominator for the approximation ratio.

Step 2. Write the per-edge expectation. With $D=2$ , equation (6) gives $\langle Z_uZ_v\rangle=\sin4\beta\,\sin\gamma\,\cos\gamma=\tfrac12\sin4\beta\,\sin2\gamma$ . The per-edge cut value is $\tfrac12\big(1-\tfrac12\sin4\beta\sin2\gamma\big)$ , and every one of the six edges is equivalent by symmetry, so $F_1=6\cdot\tfrac12\big(1-\tfrac12\sin4\beta\sin2\gamma\big)=3\big(1-\tfrac12\sin4\beta\sin2\gamma\big)$ .

Step 3. Optimize the angles. $F_1$ is largest when $\sin4\beta\,\sin2\gamma$ is most negative, i.e. $=-1$ . Take $\sin2\gamma=+1\Rightarrow\gamma=\pi/4$ and $\sin4\beta=-1\Rightarrow\beta=3\pi/8$ . Then $\langle Z_uZ_v\rangle=\tfrac12(-1)=-\tfrac12$ , so each edge is cut with value $\tfrac12(1+\tfrac12)=\tfrac34$ .

Step 4. Assemble. $F_1=6\cdot\tfrac34=\mathbf{4.5}$ cut edges, and the ratio is $r=F_1/C_{\max}=4.5/6=\mathbf{0.75}$ . A brute-force simulation over the full $(\gamma,\beta)$ grid confirms $F_1=4.499$ at these angles — the closed form is exact. Optimal γ = π/4, β = 3π/8, F₁ = 4.5, r = 0.75, a clear jump over the p = 0 floor of 0.5.

2 · The 0.6924 guarantee for 3-regular MaxCut (fully worked)

On any 3-regular triangle-free graph, run QAOA at $p=1$ . Show the worst-case per-edge cut fraction is at least $0.6924$ , and hence $r\ge0.6924$ .

Step 1. Specialize equation (6) to $D=3$ : $\langle Z_uZ_v\rangle=\sin4\beta\,\sin\gamma\,\cos^2\gamma$ . The per-edge cut value is $\tfrac12(1-\sin4\beta\sin\gamma\cos^2\gamma)$ , and every edge sees the same local structure, so maximizing one edge maximizes the total.

Step 2. Separate the two angles. The factor $\sin4\beta$ ranges over $[-1,1]$ , so its optimal magnitude is $1$ ; the whole problem reduces to maximizing $g(\gamma)=\sin\gamma\cos^2\gamma$ over $\gamma$ .

Step 3. Maximize $g$ . Setting $g'(\gamma)=\cos\gamma(1-3\sin^2\gamma)=0$ gives $\sin^2\gamma=\tfrac13$ , so $\sin\gamma=1/\sqrt3$ , $\cos^2\gamma=\tfrac23$ , and $g_{\max}=\tfrac{1}{\sqrt3}\cdot\tfrac23=\dfrac{2}{3\sqrt3}=\mathbf{0.38490}$ .

Step 4. Convert to a cut fraction. Choosing $\sin4\beta=1$ makes $\langle Z_uZ_v\rangle=-0.38490$ , so each edge is cut with fraction $\tfrac12(1+0.38490)=\mathbf{0.69245}$ . Because $C_{\max}\le|E|$ , the expected cut divided by the true optimum satisfies $r=F_1/C_{\max}\ge F_1/|E|=0.69245$ . Thus r ≥ 0.6924 at p = 1 — the Farhi–Goldstone–Gutmann bound, comfortably beating random guessing (0.5) but still short of the classical Goemans–Williamson 0.878.

Physics of the portrait

QAOA is where quantum complexity theory, condensed-matter physics and hands-on device engineering meet — and it carries the fingerprints of one group that spent two decades asking whether adiabatic ideas could be made practical.

Origins · 1 minEdward Farhi and how this was discovered

Edward Farhi

born 1952 · MIT theoretical physicist, architect of adiabatic quantum computing and QAOA

Edward Farhi began in high-energy theory — quark jets, the Standard Model, the early universe — before turning to quantum computation in the late 1990s. With Jeffrey Goldstone, Sam Gutmann and Michael Sipser he proposed adiabatic quantum computation in 2000: solve hard problems by preparing the easy ground state of a mixer Hamiltonian and slowly deforming it into a problem Hamiltonian whose ground state encodes the answer. That analog paradigm ran into the hard question of spectral gaps, but it planted the seed. In 2014, again with Goldstone and Gutmann, Farhi distilled the idea into a gate-model recipe built for shallow, imperfect hardware: QAOA. Unusually, the paper proved a concrete worst-case guarantee — the $0.6924$ ratio for 3-regular MaxCut at depth one — giving the field a hard number to beat. Farhi and Aram Harrow then argued that even low-depth QAOA sampling is classically intractable under plausible assumptions, sharpening the advantage stakes. As director of MIT's Center for Theoretical Physics and later at Google, Farhi made QAOA the standard testbed for near-term optimization. His signature is to take a grand analog idea and compile it into something you can run on the machines that exist.

History

2000

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

2001

— the adiabatic algorithm is tested numerically on random NP-complete instances

2014

— Farhi, Goldstone and Gutmann introduce QAOA with the 0.6924 MaxCut guarantee

2016

— Farhi and Harrow argue low-depth QAOA sampling is classically hard

2019

— Hadfield and collaborators generalize to the Quantum Alternating Operator Ansatz

Going further

References. Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014) · Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018) · Nielsen and Chuang, Quantum Computation and Quantum Information, 10th Anniv. Ed., Ch. 4 (Pauli algebra) and Ch. 6 · Kitaev, Shen, Vyalyi, Classical and Quantum Computation, AMS (2002), adiabatic and Hamiltonian complexity · Hadfield et al., From the QAOA to a Quantum Alternating Operator Ansatz, Algorithms 12, 34 (2019) · Bravyi, Kliesch, Koenig, Tang, obstructions to variational optimization from symmetry and locality (2020). The key checkpoints across this article are: the $p=1$ triangle-free edge expectation $\langle Z_uZ_v\rangle=\sin4\beta\sin\gamma\cos^{D-1}\gamma$ , with $\sin\gamma\cos^2\gamma=2/(3\sqrt3)=0.38490$ at $D=3$ confirming $r\ge0.6924$ ; the $p=0$ result $F_0=|E|/2$ giving $r=0.5$ ; the $C_6$ worked example with $\gamma=\pi/4$ , $\beta=3\pi/8$ , $F_1=4.5$ , $r=0.75$ ; the mixer identity $e^{-i\beta X}=\cos\beta\,I-i\sin\beta\,X$ from the $X^2=I$ series; the adiabatic/Trotter convergence argument; the radius- $p$ light-cone bound for finite-depth circuits; and the variational inequality $\langle H_C\rangle\le\lambda_{\max}$ , the Rayleigh-quotient bound.

Prerequisites. Pauli Operators and the Computational Basis · Quantum Adiabatic Theorem and Quantum Annealing · Variational Principle and Expectation Values · Trotter–Suzuki Decomposition. Leads to. Measurement-Based Quantum Computation · Magic State Distillation · Topological Quantum Computation.

Ask the tutor: Ask me to run the $p=1$ edge calculation on your own graph, or to show exactly where the overlap-gap property caps shallow QAOA.

Is QAOA the same thing as quantum annealing?

They are close cousins with an important difference. Quantum annealing is an analog protocol: you physically prepare the ground state of a mixer Hamiltonian and then continuously deform it into the cost Hamiltonian over some schedule, hoping the adiabatic theorem keeps you in the ground state. QAOA is a digital, gate-model recipe that Trotterizes that schedule into $p$ discrete alternating pulses and — crucially — lets a classical optimizer choose the pulse durations rather than fixing them by a predetermined schedule. So annealing is one particular point inside the QAOA family (Derivation A makes this precise), but QAOA's freedom to pick bang-bang controls means that at small $p$ it can outperform a naive linear anneal of the same resource. QAOA also runs on error-correctable gate hardware, while annealing is typically analog.

Why start in the state |+⟩ rather than |0⟩?

Because $|+\rangle^{\otimes n}$ is the extremal eigenstate of the mixer $H_B=\sum_iX_i$ , and the adiabatic-limit argument requires beginning in an eigenstate of $H_B$ : the interpolation $H(s)=(1-s)H_B+sH_C$ starts at $s=0$ in the mixer's ground state. It is also the least-biased starting point — equal amplitude on all $2^n$ candidate bitstrings, so no solution is favoured before optimization. Starting in $|0\rangle^{\otimes n}$ , an eigenstate of $Z$ rather than $X$ , would break the annealing correspondence and make a poorer ansatz. The uniform superposition is prepared trivially by one layer of Hadamard gates.

Does adding more layers always give a better answer in practice?

In theory yes, in practice not necessarily. The best possible value $\max_{\gamma,\beta}F_p$ never decreases with $p$ , because a deeper circuit can always reproduce a shallower one by zeroing the extra angles. But the value you actually achieve depends on whether your classical optimizer finds that global maximum, and the landscape $F_p(\gamma,\beta)$ is non-convex, dotted with local optima, and prone to barren plateaus where gradients shrink exponentially with system size. With a fixed optimization budget the achieved ratio can plateau or even drop as $p$ grows and the parameter space balloons. This gap between the theoretical monotonicity and the practical result is one of the central open challenges of the field, and it motivates tricks like parameter transfer and warm-starting.

What is a barren plateau and why does it threaten QAOA?

A barren plateau is a region of the variational landscape where the objective's gradient is exponentially small in the number of qubits, so the cost surface looks essentially flat almost everywhere. A gradient-based optimizer then has no signal to follow: it would need exponentially many measurement shots just to resolve which way is uphill, wiping out any speedup. Plateaus arise from over-expressive or highly entangling ansätze and from noise. QAOA's structured, problem-informed ansatz is somewhat protected compared with hardware-efficient random circuits, and good angles often concentrate across instances so they can be reused — but plateaus remain a real obstruction at large depth and width, and diagnosing when a problem class is safe is an active research question.

How does QAOA compare with the best classical algorithm for MaxCut?

For MaxCut the classical bar is high. The Goemans–Williamson semidefinite-programming algorithm guarantees a cut of at least $0.878$ times the optimum on any graph — well above QAOA's $0.6924$ at depth one. To beat Goemans–Williamson, QAOA needs larger $p$ , and here the news is mixed: on some instances moderate depth suffices, but on high-girth regular graphs the overlap-gap property provably caps constant-depth QAOA below the optimum, and matching or beating strong classical methods has not been demonstrated at experimentally accessible depths and sizes. So QAOA at $p=1$ is a clean provable improvement over random guessing, not a claim of classical supremacy. Whether some depth and problem class yields a genuine, scalable quantum advantage for optimization is the open question the whole subject orbits.

Why is the light cone both a blessing and a curse?

The light cone says that after $p$ layers an edge operator only "feels" the graph within distance $p$ of its endpoints. On the blessing side, this makes shallow QAOA tractable: on a bounded-degree graph you can compute each edge's expectation exactly on a small fixed subgraph, independent of the total qubit count — which is how the $0.6924$ bound is proved with pen and paper. On the curse side, constant-depth QAOA is literally unable to distinguish two graphs identical within radius $p$ , so if the optimal solution depends on global structure beyond that radius, shallow QAOA cannot find it. Obstruction results like the overlap-gap property turn this locality into a provable performance ceiling for low-depth circuits on certain random instances.