QAOA
QAOA is a circuit template for combinatorial optimization: alternating layers of a cost step, which writes each candidate solution's quality into its phase, and a mixer step, which lets those phases interfere so better solutions become more likely — with a classical optimizer tuning the layer angles. It runs on today's hardware at modest scale, but no advantage over classical optimizers has been demonstrated or proven.
| Task | Best classical | Quantum |
|---|---|---|
| MaxCut, exact solution | NP-hard — exponential worst case | Still NP-hard — QAOA does not change the complexity class |
| MaxCut, approximation guarantee | 0.878 of optimal in polynomial time (Goemans–Williamson, 1995) | 0.692 for depth-1 QAOA on 3-regular graphs — below the classical bar; whether any fixed depth beats it is open |
What problem is QAOA for?
Combinatorial optimization: MaxCut, scheduling, routing, portfolio selection — problems where you pick the best of exponentially many discrete configurations. These are commercially enormous, which explains QAOA's popularity, and NP-hard, which frames the honest expectation: quantum computers are not expected to solve NP-hard problems efficiently. There is no exponential speedup on offer here even in theory.
The realistic question QAOA asks is narrower: can a shallow quantum circuit find better approximate answers, or find them faster, than classical heuristics? So far the answer on every published benchmark is no — but the template is simple, hardware-friendly, and heavily studied.
The classical competition
Brutally strong. Simulated annealing, tabu search and local solvers handle instances with millions of variables; industrial solvers (Gurobi, CPLEX) certify optimality on large real-world problems; and for MaxCut specifically, the Goemans–Williamson algorithm guarantees 87.8% of the optimal cut in polynomial time. Any quantum claim must beat these, not brute force — a bar that marketing copy routinely forgets.
The quantum approach
Encode the cost function so each bitstring's quality becomes a phase. One QAOA layer is:
- Cost step: for each edge or clause, a small circuit (here CX–RZ–CX) rotates the phase of each basis state in proportion to how that state scores, by an adjustable angle γ.
- Mixer step: RX rotations on every qubit, angle β, which make the phase differences interfere — transferring probability between bitstrings.
Phases alone are invisible to measurement (see amplitudes and phase); the mixer is what converts them into measurable bias. Stack p layers, sample, and let a classical optimizer tune the 2p angles. As p → ∞ the template can represent the exact optimum; at the small p noise allows, it is a heuristic whose output quality depends entirely on the angles.
Run it: MaxCut on a triangle, unoptimized angles
Same circuit, tuned angles
Identical template with γ=2π/3, β=π/6: now the six optimal strings collect ~89% of shots, well above the 75% random baseline. Finding angles like these is the classical optimizer's job, and its cost — many circuit evaluations per candidate angle pair — belongs in any honest accounting of QAOA's runtime.
Limitations
- No proven advantage. After a decade of study there is no optimization problem where QAOA provably or empirically beats the best classical method. Worse, theory shows low-depth QAOA is outperformed by simple classical local algorithms on known graph families.
- The angle search is itself hard. The parameter landscape suffers the same barren-plateau and local-minimum pathologies as VQE — QAOA is exactly VQE with a cost-Hamiltonian ansatz.
- Connectivity tax. Every edge in your problem graph needs a two-qubit interaction; on hardware with sparse connectivity, non-adjacent pairs cost SWAP chains that inflate depth quickly — see connectivity costs. Dense problem graphs are punishing.
- Depth vs noise. Better approximation needs more layers p, but noise caps usable depth at small p on current machines — precisely the regime where classical methods dominate and where the circuits are often classically simulable anyway.
On hardware today
QAOA runs regularly on real devices: a 23-qubit MaxCut study on Google's Sycamore (2020) — where performance dropped sharply once the problem graph stopped matching the chip's native connectivity — and more recent demonstrations in the 100+ qubit range on superconducting and trapped-ion hardware with error mitigation. These are genuine executions of the algorithm at meaningful width; check the machines on the hardware comparison.
What none of them show is advantage: in every published comparison, classical solvers matched or beat the quantum result, usually by a wide margin and at a tiny fraction of the cost. QAOA today is a research probe and a hardware benchmark. Try both angle settings above in the lab and watch how completely the histogram depends on two numbers.