QAOA (Quantum Approximate Optimization Algorithm) is a hybrid quantum-classical algorithm for combinatorial optimization problems. It was introduced by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann in 2014 and is one of the leading candidates for near-term quantum advantage on NISQ devices.

QAOA is a variational algorithm. It uses a parameterized quantum circuit of $p$ alternating layers to prepare a trial state, measures the expected value of a cost function, and uses a classical optimizer to update the circuit parameters $(\boldsymbol\gamma, \boldsymbol\beta)$ to minimize the cost.

The QAOA circuit starts from the uniform superposition $\lvert s\rangle = H^{\otimes n}\lvert 0\rangle^{\otimes n}$ and alternates between applying the problem Hamiltonian $H_C$ (encoding the cost function) and a mixing Hamiltonian $H_B = \sum_i X_i$ for $p$ layers.

$$\lvert\boldsymbol{\gamma},\boldsymbol{\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}\lvert s\rangle$$

The classical optimizer minimizes the expected cost $\langle\boldsymbol{\gamma},\boldsymbol{\beta}\rvert H_C\lvert\boldsymbol{\gamma},\boldsymbol{\beta}\rangle$ by choosing optimal angles. As $p \to \infty$, QAOA converges to the exact ground state of $H_C$ (the optimal solution). For finite $p$, it gives an approximation.

QAOA is applied to combinatorial optimization problems such as MaxCut, graph coloring, travelling salesman, satisfiability (SAT), and portfolio optimization. For MaxCut, QAOA with $p = 1$ provably achieves an approximation ratio of at least $0.6924$, slightly below the classical Goemans-Williamson bound of $0.878$. Whether large-$p$ QAOA can surpass the best classical approximation algorithms for any problem remains an active research question.