Quantum Approximate Optimization Algorithm

The Quantum Approximate Optimization Algorithm is the archetype of a family of near-term quantum heuristics: a shallow, structured circuit whose few parameters are tuned by a classical computer to attack a hard combinatorial problem. The setting is $\arg\max_z C(z)$ over bit strings $z\in\{0,1\}^n$ — MaxCut, Max-SAT, portfolio selection, any objective a classical processor would grind through by search. QAOA promotes the objective to a diagonal cost Hamiltonian $H_C|z\rangle = C(z)|z\rangle$ on $n$ qubits, then builds a state whose measurement in the computational basis returns high-cost strings with elevated probability. It is the optimization cousin of the Variational Quantum Eigensolver, sharing its hybrid loop: the quantum device prepares trial states and estimates $\langle H_C\rangle$ , while a classical optimizer nudges the angles. Two ideas make QAOA more than "another ansatz". First, its structure is not arbitrary — the alternating product $\prod_k e^{-i\beta_k H_B}e^{-i\gamma_k H_C}$ is a Trotterized adiabatic path with the schedule set free, so as $p\to\infty$ it solves the problem exactly and at finite $p$ it inherits adiabatic intuition. Second, at fixed $p$ the energy is local: each clause sees only its subgraph within distance $p$ , which is why the $p=1$ MaxCut energy is hand-computable and why Farhi, Goldstone, and Gutmann proved a worst-case ratio of $0.6924$ on 3-regular graphs. That locality is also a ceiling — a depth- $p$ circuit is blind beyond distance $p$ , so on expanders shallow QAOA cannot see the global structure it needs to win. The tension between provable guarantees, trainability, and hardware noise is the modern story of the algorithm.

Key takeaways

QAOA approximately solves combinatorial optimization by encoding the objective in a diagonal cost Hamiltonian $H_C$ and alternating its evolution with a non-commuting mixer $H_B=\sum_j X_j$ .
A depth- $p$ circuit $\prod_{k=1}^{p} e^{-i\beta_k H_B}e^{-i\gamma_k H_C}$ acts on $|{+}\rangle^{\otimes n}$ ; a classical optimizer tunes the $2p$ angles $(\boldsymbol\gamma,\boldsymbol\beta)$ to raise $\langle H_C\rangle$ .
Introduced by Farhi, Goldstone, and Gutmann (2014); for MaxCut on triangle-free 3-regular graphs the $p{=}1$ ansatz provably cuts a fraction $\ge 0.6924$ of edges, at $\beta=\pi/8$ and $\sin^2\gamma=\tfrac13$ .
As $p\to\infty$ QAOA reproduces any adiabatic schedule and reaches the exact optimum, since the ansatz is a first-order Trotterization of an adiabatic ramp.
QAOA is a flagship NISQ algorithm, but its usefulness is bounded from three sides: locality obstructions, barren plateaus and rugged landscapes in the outer loop, and hardware noise.
Key idea: encode the objective in a diagonal cost Hamiltonian and interleave its evolution with a transverse-field mixer; the alternating-operator ansatz is a discretized, parameter-optimized adiabatic path whose interference concentrates measurement probability on near-optimal bit strings.

The core insight

Encode the objective in a diagonal cost Hamiltonian and interleave its evolution with a non-commuting mixer; the alternating-operator ansatz is a discretized, parameter-optimized adiabatic path whose interference concentrates measurement probability on near-optimal bit strings.

Where this lives today

QAOA is the most-run algorithm on today's noisy processors because it is shallow and structured. Google's Sycamore team ran it on up to 23 superconducting qubits (Harrigan et al., Nature Physics 2021), finding hardware-native graphs tracked theory while non-native, long-range graphs degraded sharply once SWAP overhead inflated the depth — connectivity, not qubit count, is the near-term constraint. Trapped-ion and IBM groups have pushed to larger instances, and warm-started and recursive variants (RQAOA) now routinely beat vanilla QAOA at fixed depth by injecting classical relaxation. On the theory side the frontier is sobering: Farhi–Gamarnik–Jordan's typical-instance analyses on the Sherrington–Kirkpatrick model and large-girth graphs give sharp finite- $p$ performance, while Barak–Marwaha and related classical algorithms have matched or beaten shallow QAOA on exactly those families. The open problem is unchanged from 2014: is there a depth, a mixer, and an angle-finding strategy at which QAOA beats the best classical algorithm on an economically relevant problem, on real hardware?

The physical picture

QAOA does two things over and over. The cost unitary $e^{-i\gamma H_C}$ stamps every basis string with a phase proportional to its cost — invisible to a computational-basis measurement on its own. The mixer $e^{-i\beta H_B}$ , with $H_B=\sum_j X_j$ , is a tunable diffusion between strings differing by one bit flip, converting those phase differences into amplitude differences. Alternating the two engineers constructive interference toward high-cost strings — a programmable, Grover-like steering of amplitude — while a classical optimizer reads $\langle H_C\rangle$ and retunes the $2p$ angles. The first figure lays out that hybrid loop.

Figure

The QAOA loop: prepare the uniform superposition, alternate the cost unitary e^(−iγ H_C) and mixer e^(−iβ H_B) for p rounds, measure in the Z basis to sample a string z, and let a classical optimizer retune the 2p angles to raise the estimated energy ⟨H_C⟩

QAOA is best understood as a Trotterized adiabatic evolution with the schedule set free: the adiabatic algorithm slowly turns off the mixer and turns on the cost Hamiltonian along $H(t)=(1-t/T)H_B+(t/T)H_C$ , and chopping that ramp into $p$ steps gives exactly the alternating product. Because the optimizer may pick any angles, not just a smooth ramp, QAOA can beat a naive discretized schedule at the same depth. A second structural fact governs everything analytic: at depth $p$ , $\langle H_C\rangle$ decomposes clause by clause, each clause seeing only its subgraph within distance $p$ . That is why the $p=1$ MaxCut energy is a hand-computable function of two angles — the curve plotted below, whose peak is the Farhi–Goldstone–Gutmann guarantee.

Figure

The p = 1 MaxCut per-edge energy on a triangle-free 3-regular graph, F₁ = ½ + ½ sin4β sinγ cos²γ at the optimal mixer β = π/8, versus the cost angle γ. The two symmetric peaks reach ½ + 1/(3√3) = 0.6925 at γ* = 0.6155 rad = 35.26°, the provable approximation-ratio bound of 0.6924

The core equations

QAOA prepares a single state, fixed by the two Hamiltonians and the $2p$ angles. Reading right to left, it starts from the uniform superposition — the mixer's top eigenstate — and applies $p$ cost-then-mixer rounds.

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

where: $H_C$ — diagonal cost Hamiltonian, $H_C|z\rangle=C(z)|z\rangle$ ; $H_B=\sum_{j=1}^n X_j$ — mixer; $\gamma_k,\beta_k$ — layer- $k$ angles; $p$ — depth; $|{+}\rangle^{\otimes n}$ — uniform superposition, top eigenstate of $H_B$ . Because $[H_C,H_B]\neq 0$ , the alternation generates interference. The scalar the optimizer sees is the energy expectation — the mean cost of the output distribution; maximizing it drives probability toward good strings.

F_p(\boldsymbol\gamma,\boldsymbol\beta) = \langle \boldsymbol\gamma,\boldsymbol\beta|\,H_C\,|\boldsymbol\gamma,\boldsymbol\beta\rangle = \sum_z \big|\langle z|\boldsymbol\gamma,\boldsymbol\beta\rangle\big|^2\,C(z) \qquad (2)

where: $F_p$ — expected cost of the depth- $p$ ansatz; $|\langle z|\boldsymbol\gamma,\boldsymbol\beta\rangle|^2$ — probability of sampling $z$ . Since the max dominates the mean, sampling yields cost- $\ge F_p$ strings with constant probability, so raising $F_p$ pushes good samples. For MaxCut, the cost operator is a sum of two-local edge terms; each contributes $1$ when its endpoints lie on opposite sides of the cut and $0$ otherwise, so the maximum of $H_C$ is the MaxCut value.

H_C = \sum_{\langle i,j\rangle\in E}\tfrac{1}{2}\big(I - Z_i Z_j\big) \qquad (3)

where: $E$ — edge set; $Z_i$ — Pauli- $Z$ on qubit $i$ ; $\langle i,j\rangle$ — an edge. For a $\pm1$ assignment $\tfrac12(1-z_iz_j)=1$ iff $z_i\neq z_j$ , so $\langle H_C\rangle$ counts cut edges; any QUBO generalizes to $H_C=\sum_i h_iZ_i+\sum_{i<j}J_{ij}Z_iZ_j$ . The two evolutions factor into hardware-native gates: the cost unitary is a product of commuting two-qubit $ZZ$ -phase rotations, the mixer of independent single-qubit $X$ -rotations.

U_C(\gamma)=\prod_{\langle i,j\rangle} e^{-i\tfrac{\gamma}{2}(I-Z_iZ_j)},\qquad U_B(\beta)=\prod_{j} e^{-i\beta X_j}=\prod_j R_X(2\beta) \qquad (4)

where: $e^{-i\gamma Z_iZ_j/2}$ — hardware-native two-qubit $ZZ$ -phase gate; $R_X(2\beta)$ — single-qubit $X$ -rotation. All terms in $U_C$ commute, so it is exact (not Trotterized) at each layer. The angles live on a compact domain. For integer-eigenvalue $H_C$ (as MaxCut) the cost phase is $2\pi$ -periodic; the mixer is $\pi$ -periodic because $e^{-i\pi X}=-I$ is a global phase that leaves all observables unchanged.

\gamma\in[0,2\pi),\qquad \beta\in[0,\pi) \qquad (5)

where: $\gamma$ — cost angle, period $2\pi$ for integer $H_C$ ; $\beta$ — mixer angle, period $\pi$ . Graph symmetries shrink the search region further, so good angles are cheap to locate. Training uses exact analytic gradients, not finite differences. Every angle's generator has eigenvalues $\pm1$ after rescaling, so $F_p$ is a single-frequency sinusoid and two shifted evaluations recover the derivative exactly.

\frac{\partial F_p}{\partial\theta} = \tfrac{1}{2}\Big[F_p\big(\theta+\tfrac{\pi}{2}\big)-F_p\big(\theta-\tfrac{\pi}{2}\big)\Big] \qquad (6)

where: $\theta$ — any single angle $\gamma_k$ or $\beta_k$ (with the appropriate generator scaling). The two evaluations are themselves QAOA circuits, so gradients cost the same as energies. (The adiabatic schedule $H(t)=(1-t/T)H_B+(t/T)H_C$ whose Trotterization is the ansatz is developed in the third derivation below.)

Derivation AThe single-edge p equals one MaxCut expectation

The goal is to derive the closed form of one edge's contribution to $F_1$ — the trigonometric building block of every analytic QAOA guarantee — and then optimize it to the $0.6924$ approximation ratio. We take a single edge $\langle u,v\rangle$ with $C_{uv}=\tfrac12(1-Z_uZ_v)$ in the $p=1$ state $U_B(\beta)U_C(\gamma)|{+}\rangle^{\otimes n}$ , and compute $\langle C_{uv}\rangle$ by conjugating $Z_uZ_v$ through the two unitaries in the Heisenberg picture.

Step 1. Push the observable through the circuit: $\langle C_{uv}\rangle = \langle {+}|\,U_C^\dagger U_B^\dagger\,\tfrac12(I-Z_uZ_v)\,U_B U_C\,|{+}\rangle$ . Conjugation by the mixer touches only $X_u,X_v$ ; by the cost unitary, only edges incident to $u$ or $v$ . Why: the transformed operator lives on the distance-one subgraph, so $\langle C_{uv}\rangle$ depends only on the two degrees and the triangle count — the locality that makes $p=1$ tractable.

Step 2. Apply the mixer conjugation $U_B^\dagger Z_u U_B = \cos(2\beta)Z_u + \sin(2\beta)Y_u$ (rotating $Z$ about $X$ ), and likewise for $v$ . Why: the mixer rotates the diagonal $Z$ operators out of the computational basis, producing the $\sin2\beta,\cos2\beta$ envelope the cost phases then act on.

Step 3. Apply the cost conjugation. Each incident $e^{-i\gamma Z_iZ_j/2}$ on a shared-qubit $Y$ or $Z$ either leaves it ( $\cos\gamma$ ) or rotates it into a new Pauli ( $\sin\gamma$ ), so the $d$ non-partner neighbours contribute $\cos^{d}\gamma$ ; triangles give the $\cos^{f}2\gamma$ correction. Why: commuting $ZZ$ phases turn the neighbourhood into simple cosine powers, one per neighbour.

Step 4. Average the surviving strings in $|{+}\rangle^{\otimes n}$ , the $+1$ eigenstate of every $X_j$ . Only $X$ -diagonal terms survive, collapsing the polynomial to the boxed form with $d_u,d_v$ the non-partner neighbour counts and $f$ the triangle count:

\langle C_{uv}\rangle = \tfrac12 + \tfrac14\sin(4\beta)\sin\gamma\big(\cos^{d_u}\!\gamma+\cos^{d_v}\!\gamma\big) - \tfrac14\sin^2(2\beta)\,\cos^{d_u+d_v-2f}\!\gamma\,\big(1-\cos^{f}\!2\gamma\big)

Why: the all-plus average is a projector onto $X$ -diagonal terms, which is what turns a messy operator sum into three clean trigonometric pieces.

Step 5. For a triangle-free 3-regular graph $d_u=d_v=2$ , $f=0$ , killing the third term and leaving $\langle C_{uv}\rangle = \tfrac12 + \tfrac12\sin(4\beta)\sin\gamma\cos^2\gamma$ . Maximizing ( $\beta=\pi/8$ , $\sin^2\gamma=\tfrac13$ , $\gamma^\star=0.6155$ rad) gives $\tfrac12+\tfrac{1}{3\sqrt3}=0.69245$ . Why: the bound holds edge by edge and every edge is identical on a regular graph, so summing gives the whole-graph ratio $\ge 0.6924$ — no instance-specific computation. *Verified numerically: optimum $0.6924500\ldots$ at $\beta=\pi/8,\ \gamma=0.61548$ ; $\beta=0$ gives $\tfrac12$ (no mixing) as required; matches Farhi–Goldstone–Gutmann (2014). Note the convention $d_u=d_v=2$ (neighbours excluding the partner), not the full degree 3 — using 3 would give $\cos^3\gamma$ and the wrong ratio $0.662$ .*

Go deeper · Derivation B · 1 minWhy the cost unitary alone does nothing

Derivation BWhy the cost unitary alone does nothing

The goal is to prove that the cost unitary can never, by itself, change what a computational-basis measurement returns — so the non-commuting mixer is a structural necessity, not an optional refinement. We take an arbitrary $|\psi\rangle$ , apply only $U_C(\gamma)=e^{-i\gamma H_C}$ (diagonal in the computational basis), and compute its output distribution.

Step 1. Because $H_C$ is diagonal, $e^{-i\gamma H_C}|z\rangle=e^{-i\gamma C(z)}|z\rangle$ — each basis state picks up a pure phase. Why: a diagonal exponential acts entrywise, so $U_C$ is a phase gate that commutes with every $Z$ -basis projector.

Step 2. Then $\Pr[z\,|\,U_C\psi] = |e^{-i\gamma C(z)}\langle z|\psi\rangle|^2 = |\langle z|\psi\rangle|^2 = \Pr[z\,|\,\psi]$ — the phase cancels in the square. Why: probabilities are moduli-squared, and a phase has modulus one, so it is invisible to measurement.

Step 3. Only interleaving the mixer $U_B(\beta)$ , which rotates amplitudes out of the computational basis, can convert $U_C$ 's phases into probability differences. Why: exactly Grover's principle — a phase oracle does nothing until diffusion reflects it into amplitude. *Verified: a direct consequence of $[H_C,\,|z\rangle\langle z|]=0$ for all $z$ ; phase oracles require a separate mixing step.*

Go deeper · Derivation C · 1 minQAOA as a Trotterized adiabatic path

Derivation CQAOA as a Trotterized adiabatic path

The goal is to make precise how QAOA contains the adiabatic algorithm — reaching the exact optimum as $p\to\infty$ — and why finite- $p$ QAOA can beat a naive discretized ramp. We start from the adiabatic interpolation, split its evolution by first-order Trotter, and identify the factors with QAOA layers.

Step 1. The adiabatic theorem: evolving under $H(t)=(1-t/T)H_B+(t/T)H_C$ from the ground state of $H(0)=H_B$ (which is $|{+}\rangle^{\otimes n}$ ), slowly relative to the inverse minimum gap, ends in the ground state of $H(T)=H_C$ — the optimum. Why: this fixes both the initial state and the target, and is why QAOA begins in $|{+}\rangle^{\otimes n}$ .

Step 2. Discretize into $p$ slices of width $\Delta t=T/p$ and Trotter each: $e^{-i\Delta t\,H(t_k)} \approx e^{-i\Delta t\,s_k H_C}\,e^{-i\Delta t(1-s_k)H_B}$ , $s_k=t_k/T$ . The product is exactly the QAOA circuit with $\gamma_k=\Delta t\,s_k$ , $\beta_k=\Delta t(1-s_k)$ . Why: it exhibits the alternating product as the discretization of a physical evolution, so QAOA inherits adiabatic intuition.

Step 3. Now free the angles. Any adiabatic schedule maps to some angle sequence, so the best depth- $p$ QAOA is at least as good as the best $p$ -step ramp — and generally better, since the optimizer is not confined to a smooth monotone schedule. As $p\to\infty$ a slow enough embedded schedule exists, so $\max_{\boldsymbol\gamma,\boldsymbol\beta}\langle H_C\rangle \to C_{\max}$ . Why: the large-depth exactness guarantee, and why good QAOA angles often look like a smooth ramp plus corrections. *Verified: reproduces the adiabatic limit of Farhi et al. (2000); the $p\to\infty$ convergence rate is set by the minimum gap of $H(t)$ .*

Limiting cases

QAOA interpolates between well-understood regimes as depth, graph class, and mixer vary:

Case	Result	Meaning
Depth $p=1$ , triangle-free 3-regular MaxCut	$\alpha \ge 0.6924$	Farhi–Goldstone–Gutmann's worst-case ratio, from the local edge formula at $\beta=\pi/8,\ \sin^2\gamma=\tfrac13$ .
Depth $p=1$ , large-girth ring	$\langle H_C\rangle/m \to \tfrac34$	On $C_n$ each vertex has one non-partner neighbour ( $d=1,f=0$ ), giving $\tfrac34$ — beats random's $\tfrac12$ but exposes $p=1$ 's ceiling on tree-like graphs.
Adiabatic limit	$\lim_{p\to\infty}\max\langle H_C\rangle = C_{\max}$	The ansatz reproduces any adiabatic schedule, reaching the exact optimum; rate set by the minimum gap.
$\beta=0$ (no mixing)	$\langle H_C\rangle = \langle H_C\rangle_{\|+\rangle}$	The cost unitary alone leaves the uniform distribution untouched — inert without the mixer.
Bounded depth vs. classical hardness	$p=O(\log n)$ insufficient on some families	Locality obstructions (Bravyi–Kliesch–Koenig–Tang) show fixed shallow QAOA cannot beat the best classical algorithms on some symmetric/expander instances; depth must grow with $n$ .

Common trapQAOA descends the energy gate by gate, and ⟨H_C⟩ is the answer

Two linked misconceptions. First, QAOA does not "lower the energy" step by step: the cost unitary is diagonal and only adds phases, changing no measurement probability — without the mixer the circuit does nothing to the output distribution, and the energy moves only because phases and mixing interfere. Second, $\langle H_C\rangle$ is a training signal, not the deliverable. The output is a bit string from measuring the final state many times and keeping the best sample; a state with a mediocre mean can still place enough weight on the optimum to find it by sampling. So both the approximation ratio and the shot count (growing as $1/\varepsilon^2$ ) matter — a good $F_p$ with an unaffordable sampling overhead is not a solved problem.

Worked examples

1 · The 0.6924 bound on a 3-regular graph (fully worked)

Take MaxCut on any triangle-free 3-regular graph with $m$ edges. Find the optimal $p=1$ angles, the per-edge energy, the expected cut, and the guaranteed approximation ratio.

Step 1. Every edge is locally identical: both endpoints have degree 3, so $d_u=d_v=2$ non-partner neighbours and $f=0$ . The third term vanishes, leaving $\langle C_{uv}\rangle = \tfrac12 + \tfrac12\sin(4\beta)\sin\gamma\cos^2\gamma$ .

Step 2. Mixer: $\sin(4\beta)$ is maximal at $4\beta=\pi/2$ , so $\boldsymbol{\beta^\star=\pi/8}$ . Cost angle: $\cos\gamma(1-3\sin^2\gamma)=0$ in $(0,\pi/2)$ gives $\sin^2\gamma=\tfrac13$ , so $\boldsymbol{\gamma^\star=\arcsin(1/\sqrt3)=0.6155}$ rad $=35.26^\circ$ .

Step 3. Evaluate: $\sin\gamma^\star\cos^2\gamma^\star=\tfrac{1}{\sqrt3}\cdot\tfrac23=\tfrac{2}{3\sqrt3}$ , so $\langle C_{uv}\rangle=\tfrac12+\tfrac{1}{3\sqrt3}=\mathbf{0.69245}$ .

Step 4. Sum over all $m$ identical edges: $F_1=m\cdot 0.69245$ . Since $C_{\max}\le m$ , the ratio is $F_1/C_{\max}\ge 0.6924$ , independent of graph size — proved without solving an instance. β⋆ = π/8, γ⋆ = 0.6155 rad, per-edge 0.6925, ratio ≥ 0.6924.

2 · The ring of disagrees (why p = 1 is weak on tree-like graphs)

Run $p=1$ QAOA on the cycle graph $C_n$ for large $n$ . What fraction of edges does it cut, and how does that compare with the exact MaxCut?

Step 1. On a cycle every vertex has degree 2, so each edge's endpoints have one non-partner neighbour each: $d_u=d_v=1$ , $f=0$ . The formula gives $\langle C_{uv}\rangle=\tfrac12+\tfrac12\sin(4\beta)\sin\gamma\cos\gamma=\tfrac12+\tfrac14\sin(4\beta)\sin(2\gamma)$ .

Step 2. Maximize both: $\sin(4\beta)=1$ and $\sin(2\gamma)=1$ give $\langle C_{uv}\rangle=\tfrac12+\tfrac14=\tfrac34$ , so $p=1$ QAOA cuts on average $\tfrac34$ of the edges.

Step 3. An even cycle is bipartite, so the exact MaxCut is all $n$ edges and the ratio is $\tfrac34$ . This beats random ( $\tfrac12$ ) but leaves a quarter of the cut on the table, and no angle tuning at $p=1$ improves it — the circuit cannot see beyond immediate neighbours. p = 1 cuts 3/4 of the ring's edges; the ceiling is locality, not bad optimization.

3 · Resource count for a NISQ-scale run (why it is "near-term")

Estimate the cost of $p=3$ QAOA on a 3-regular MaxCut instance with $n=100$ vertices.

Step 1. A 3-regular graph on $n=100$ vertices has $m=\tfrac{3n}{2}=\mathbf{150}$ edges. Each layer needs one $ZZ$ -gate per edge plus one $X$ -rotation per qubit ( $250$ gates), so $p=3$ gives $\mathbf{750}$ parameterized gates and $2p=\mathbf{6}$ angles.

Step 2. Estimating $\langle H_C\rangle$ to error $\varepsilon$ needs $\sim\mathrm{Var}(H_C)/\varepsilon^2$ shots; with per-edge variance $\lesssim\tfrac14$ , $\mathrm{Var}(H_C)\sim 38$ , so $\varepsilon=1$ cut edge costs $\approx\mathbf{40}$ shots per point — times hundreds of optimizer steps. The circuit is shallow; the nonconvex outer loop and its shot budget dominate. ≈ 750 gates, 6 angles, ~40 shots per point; the outer loop, not the depth, is the bottleneck.

Physics of the portrait

QAOA sits at the confluence of adiabatic quantum computation, variational methods, and combinatorial approximation — and one group tied them together.

Origins · 1 minEdward Farhi and how this was discovered

Edward Farhi

b. 1952 · quantum computation, adiabatic algorithms, and the QAOA

Edward Farhi is an American theoretical physicist who spent most of his career at MIT's Center for Theoretical Physics before leading Google's quantum-algorithms effort. His early work was in particle physics and cosmology, but from the late 1990s he became an architect of a distinctively physical approach to computing. With Goldstone, Gutmann, and Sipser he introduced quantum computation by adiabatic evolution in 2000 — encoding a problem in a Hamiltonian's ground state and reaching it by slow interpolation from an easy Hamiltonian. Fourteen years later, with Goldstone and Gutmann, he distilled that idea into a circuit near-term hardware could run: the QAOA. Two features of the 2014 paper set the agenda: a provable worst-case guarantee — the $0.6924$ MaxCut ratio on 3-regular graphs, computed by hand from circuit locality, showing a quantum heuristic could carry a theorem — and the framing of depth $p$ as a knob between a cheap local heuristic and the exact adiabatic algorithm. Farhi and Harrow soon argued even $p=1$ QAOA produces classically hard-to-sample distributions, tying it to quantum-advantage debates. QAOA became the reference point for the whole near-term variational program: custom mixers, warm starts, recursive variants, and barren-plateau analyses are all framed as modifications of the original alternating operators.

History

2000

— Farhi, Goldstone, Gutmann and Sipser introduce quantum computation by adiabatic evolution

2014

— Farhi, Goldstone and Gutmann introduce the QAOA and prove the 0.6924 MaxCut bound

2016

— Farhi and Harrow argue the QAOA is hard to simulate classically even at p equals one

2018

— Preskill names the NISQ era, placing the QAOA at its centre

2019

— Hadfield and coworkers extend it to the Quantum Alternating Operator Ansatz

Going further

Texts and papers. Farhi, Goldstone, Gutmann, "A Quantum Approximate Optimization Algorithm", arXiv:1411.4028 (2014) · Farhi, Goldstone, Gutmann, arXiv:1412.6062 (2014, bounded-occurrence constraint problem) · Hadfield et al., "From the QAOA to a Quantum Alternating Operator Ansatz", Algorithms 12, 34 (2019) · Preskill, "Quantum Computing in the NISQ Era and Beyond", Quantum 2, 79 (2018) · Cerezo et al., "Variational Quantum Algorithms", Nature Reviews Physics 3, 625 (2021) · Harrigan et al., Nature Physics 17, 332 (2021) · Nielsen & Chuang, Quantum Computation and Quantum Information, 10th Anniversary Ed.

Provenance. The QAOA state, MaxCut encoding, and angle periodicity are textbook (Nielsen & Chuang; Hadfield et al. 2019). The single-edge $p=1$ formula and $\ge 0.6924$ bound follow Farhi–Goldstone–Gutmann (arXiv:1411.4028); a verifier should reproduce the boxed expectation by Pauli conjugation and confirm the optimum $0.69245$ at $\beta=\pi/8,\ \sin^2\gamma=\tfrac13$ — note the convention $d_u=d_v=2$ (degree minus one), which this article uses and the migrated source stated as $3$ . The ring $\tfrac34$ follows with $d=1$ ; the parameter-shift identity follows Mitarai et al. (2018) and Schuld et al. (2019); barren-plateau scaling cites McClean et al. (2018). All numbers were re-verified numerically.

Builds on: Variational Quantum Eigensolver · Parameterized Quantum Circuits · Cost-Function and Measurement Estimation. Leads to: QAOA Performance Bounds and Concentration · Classical Optimizers for VQAs · Barren Plateaus.

Ask the tutor: Ask me to walk through the $p=1$ MaxCut edge derivation term by term, or to work out the optimal angles and cut fraction for a small graph you have in mind.

Is QAOA guaranteed to beat classical algorithms?

No — this is the central open question, not a settled advantage. QAOA has a provable worst-case guarantee ( $0.6924$ for $p=1$ MaxCut on 3-regular graphs), but classical algorithms often match or beat shallow QAOA on exactly the families where its performance is known: Goemans–Williamson cuts $\ge 0.878$ of the optimum in polynomial time, well above $p=1$ QAOA, and local classical algorithms (Barak–Marwaha) keep pace on large-girth and Sherrington–Kirkpatrick instances. A genuine advantage, if it exists, likely needs larger $p$ , tailored mixers, or classically resistant structure — and must survive noise. QAOA is a leading candidate, not a proven winner.

What is the difference between QAOA and VQE?

They share the hybrid loop but differ in target and ansatz. VQE estimates ground-state energies of physical or chemical Hamiltonians (whose terms generally do not commute) with a hardware-efficient or chemistry-inspired ansatz, and its answer is the energy itself. QAOA targets a classical objective in a diagonal cost Hamiltonian, uses the specific alternating cost–mixer ansatz from adiabatic evolution, and delivers a sampled bit string, not the energy — a structured special case where ansatz and initial state are dictated by the problem.

Why start in the uniform superposition |+⟩^⊗n?

Because it is the top eigenstate of the mixer $H_B=\sum_j X_j$ — the analogue of starting the adiabatic algorithm in the ground state of the easy Hamiltonian, which the adiabatic theorem requires. It is also maximally unbiased: every bit string has equal amplitude, so the algorithm sculpts probability from a flat prior rather than committing to any assignment. Warm-start QAOA deliberately breaks this symmetry, seeding a biased state from a classical relaxation — which can help, but requires a matching modified mixer to preserve the adiabatic connection.

How do you find good angles without paying the full optimization cost?

Two properties rescue the outer loop. First, parameter concentration: optimal angles for one instance of a class tend to be nearly optimal for others of the same class and size, so they can be precomputed on small instances and transferred. Second, good angles often resemble a smooth adiabatic schedule, so a linear-ramp initial guess lands near the optimum's basin. With exact parameter-shift gradients, the nonconvex landscape is far more navigable than its worst case suggests. When these fail — deep circuits, barren plateaus — angle finding becomes the dominant cost.

What is the Quantum Alternating Operator Ansatz, and how does it differ?

Hadfield and coworkers (2019) generalized QAOA by keeping the alternating structure but replacing the transverse-field mixer with one tailored to the problem's constraints — hence the reinterpreted acronym, "Alternating Operator Ansatz". Hard constraints (say, "exactly $k$ items selected") are enforced by a mixer whose evolution never leaves the feasible subspace, rather than by penalty terms in $H_C$ that waste amplitude on infeasible strings. This trades a universal mixer for a problem-specific one, often improving constrained problems like graph colouring, routing, and scheduling. Original transverse-field QAOA is the special case where the feasible space is the whole Hilbert space.

Does hardware noise destroy QAOA's advantage?

Noise is a serious threat but not an automatic death sentence at shallow depth. Short circuits accumulate less error than deep ones — a large part of QAOA's near-term appeal — but every two-qubit $ZZ$ gate and measurement carries error, and without native long-range connectivity SWAP networks inflate depth and noise (as Sycamore showed for non-planar graphs). Noise also flattens the landscape, worsening barren plateaus, and biases the distribution. Mitigation partially recovers the signal, but whether the residual advantage survives at sizes that matter is what current experiments probe.