Key Takeaways: Chapter 20 — QAOA — The Quantum Approximate Optimization Algorithm for Combinatorial Problems
-
QAOA is a variational quantum algorithm for combinatorial optimization, designed for NISQ hardware with shallow alternating layers of cost and mixer unitaries.
-
Combinatorial optimization problems map to Ising Hamiltonians via the correspondence $z_i \leftrightarrow (I - Z_i)/2$. The cost Hamiltonian $H_C$ is diagonal in the computational basis, with eigenvalues equal to the cost function values.
-
The QAOA circuit alternates $e^{-i\gamma H_C}$ (phase imprinting) and $e^{-i\beta H_M}$ (state mixing). The cost layer applies phases proportional to solution quality; the mixer layer enables exploration of the solution space.
-
QAOA is a Trotterized approximation of adiabatic quantum computing. As $p \to \infty$, QAOA can reproduce adiabatic evolution exactly. For finite $p$, variational optimization can outperform a fixed adiabatic schedule.
-
Parameter concentration is a remarkable empirical phenomenon: optimal QAOA parameters for regular graphs are nearly independent of graph size, enabling transfer learning.
-
The approximation ratio improves with depth $p$, but gains diminish. For NISQ devices, $p \leq 3$ is typical. The Goemans-Williamson classical algorithm achieves 0.878 for MaxCut, setting a high bar.
-
Barren plateaus, local minima, and classical competition are the main challenges. No rigorous exponential speedup has been proven for QAOA on practical problems.
-
Custom mixer Hamiltonians can enforce problem constraints, restricting the search to feasible solutions and improving performance on constrained optimization problems.
-
QAOA's path to advantage lies in finding specific problem instances where quantum interference provides a genuine edge — not in universal speedups for all NP-hard problems.