Algorithm Zoo · Optimization
QAOA
Also known as: Quantum Approximate Optimization Algorithm
First described: Farhi, Goldstone, Gutmann, 2014
The problem
Heuristically find good solutions to combinatorial optimization problems (MaxCut, MaxSAT, ...).
Apply alternating problem-Hamiltonian and mixer-Hamiltonian rotations to |+⟩^n with classical-optimizer-tuned parameters β, γ. p layers; in the p→∞ limit, QAOA recovers adiabatic optimization.
Best classical
Goemans-Williamson (≈0.878 for MaxCut), SDPs, simulated annealing, branch-and-bound. Strong.
Quantum complexity
O(p · m) gates per call for an m-edge graph; classical optimization layer on top.
Our verdict
A research vehicle, not an optimization tool. Ten years of attempts have not produced a QAOA result that beats a strong classical baseline on a problem instance anyone cares about. The interesting research now is understanding *why* — Goemans-Williamson rounding of an SDP appears to be inherently hard to beat with a polynomial-depth quantum circuit.
When to use it
- Studying variational ansätze and their training dynamics (research).
- Benchmarking real hardware on instances small enough that the noise doesn't eat the signal.
When not to use it
- Real optimization workloads — modern classical solvers (Gurobi, CPLEX, Hexaly) crush every benchmarked QAOA instance.
- When you would deploy this in production. There is no QAOA result that beats a tuned classical baseline at problem sizes anyone cares about.
Classical baseline
Goemans-Williamson gives 0.878-approximation for MaxCut in polynomial time. Empirically, modern QAOA at p=10 underperforms simulated annealing on most graph instances; large meta-analyses (Lykov et al. 2023, Bechtold et al. 2025) find no instance class where QAOA wins.
Hardware cost
Per layer: 2|E| two-qubit gates (problem) plus n single-qubit rotations (mixer). At p=10, 20 qubits: ≈400 gates, deep enough that 2026 NISQ noise kills the signal.
Key papers
- A Quantum Approximate Optimization Algorithm ↗
Farhi, Goldstone, Gutmann · 2014 · arXiv
- Sampling Frequency Thresholds for the Quantum Advantage of QAOA ↗
Lykov, Wurtz, Poole, Saffman, Noel, Alexeev · 2023 · npj Quantum Information
Deep-dive tutorials
Last verified: 2026-05-24