Source-verifiedLevel 3

Quantum Approximate Optimization Algorithm (QAOA)

QAOA is a hybrid quantum-classical algorithm for combinatorial optimization: it alternates parameterized cost and mixer layers on a quantum circuit while a classical optimizer tunes the parameters to maximize the expected solution quality.

What it means

QAOA (Farhi, Goldstone, Gutmann, 2014) targets combinatorial problems such as MaxCut.Starting from the uniform superposition |+>^n, the circuit alternates p layers of two operations: evolution under a cost Hamiltonian C that encodes the objective function, exp(-i*gamma_k*C), and evolution under a mixer Hamiltonian B (typically a sum of Pauli-X terms), exp(-i*beta_k*B).A classical optimizer adjusts the 2p angles (gamma, beta) to maximize the measured expectation of C.Measuring the final state yields candidate bit strings; the best ones approximate the optimal solution.As p grows, the achievable approximation quality is non-decreasing, and in the p-to-infinity limit QAOA can recover the adiabatic algorithm's behavior.Like VQE, it is designed with near-term noisy hardware in mind because shallow depths (small p) are already meaningful.

Everyday analogy

It is like kneading dough in rounds: one move presses the dough toward the shape you want (cost layer), the next move folds and mixes it (mixer layer), and after several careful rounds the dough is much closer to the shape you asked for.
Think of the classical optimizer as a coach and the quantum circuit as an athlete: the athlete runs a routine with certain settings, the coach watches the score and adjusts the settings for the next run.

Common misconceptions

  • QAOA is NOT guaranteed to outperform classical optimization algorithms -- no general provable speedup for combinatorial optimization is known, and for some settings classical algorithms match or beat low-depth QAOA.
  • QAOA at finite depth p is an APPROXIMATE method -- it returns good candidate solutions with some probability, not a certified optimum.
  • QAOA is not purely quantum -- it is a hybrid loop that requires a classical optimizer, like VQE.

Key takeaways

  • Alternates cost layers exp(-i*gamma*C) and mixer layers exp(-i*beta*B) for p rounds, starting from |+>^n.
  • A classical optimizer tunes the 2p angles to maximize the expected objective value.
  • Approximation quality is non-decreasing in p; connects to the adiabatic algorithm as p goes to infinity.

Check your understanding

Which two operations alternate in each QAOA layer?

  1. A.Oracle and diffusion
  2. B.Cost-Hamiltonian evolution and mixer-Hamiltonian evolution
  3. C.QFT and inverse QFT
  4. D.Encoding and error correction
Show the answer

Answer: B. Cost-Hamiltonian evolution and mixer-Hamiltonian evolution

Why: Each QAOA layer applies evolution under the cost Hamiltonian C (encoding the objective) followed by evolution under the mixer Hamiltonian B (typically sum of Pauli-X), with angles gamma and beta tuned classically.

Builds on

QubitSuperpositionQuantum MeasurementHybrid Quantum-Classical ComputingVariational Quantum Eigensolver (VQE)

Primary source: Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014)

Graded 2026-07-10 (human sign-off): established per Farhi, Goldstone, Gutmann arXiv:1411.4028 (2014).

Learn it hands-on

This concept is part of a 46-level curriculum with an interactive simulator and Lumen, a tutor whose answers are verified before you see them. Levels 1–5 are free.

Start freeSee the curriculum