Quantum Approximate Optimization Algorithm (QAOA)

Core Idea

The Quantum Approximate Optimization Algorithm (QAOA) is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. It alternates between a problem Hamiltonian (encoding the objective function as phases) and a mixing Hamiltonian (creating transitions between candidate solutions), with p layers of parameterized rotations. The circuit depth grows linearly with p, and as p increases, QAOA interpolates between a single-round heuristic and the adiabatic algorithm (which is exact in the infinite-depth limit). QAOA is a leading candidate for near-term quantum advantage on optimization problems like MaxCut, satisfiability, and portfolio optimization.

Explainer

Combinatorial optimization problems — finding the best configuration among exponentially many candidates — are ubiquitous in logistics, finance, machine learning, and physics. Many are NP-hard, so no polynomial-time classical algorithm is expected. QAOA provides a quantum approach that may offer practical advantages for approximate solutions, even on near-term hardware without error correction.

The algorithm is defined by a problem Hamiltonian C (a diagonal operator whose eigenvalues are the objective function values on each computational basis state) and a mixing Hamiltonian B (typically the sum of Pauli X operators on all qubits, generating transitions between basis states). For MaxCut, C = sum over edges (i,j) of (1 - Z_i * Z_j)/2, which counts the number of cut edges for each bit-string assignment. The initial state is |+>^n (uniform superposition). The QAOA circuit applies p alternating layers: first e^-i*gamma_k*C (the problem unitary), then e^-i*beta_k*B (the mixer), for k = 1 to p. The 2p parameters {gamma_1,...,gamma_p, beta_1,...,beta_p} are optimized classically to maximize the expected value of C.

The QAOA circuit encodes a physical process: the problem unitary imprints the objective function as phases (good solutions get different phases than bad ones), and the mixer creates superpositions that allow interference between solutions. After p rounds, constructive interference at high-quality solutions and destructive interference at low-quality solutions biases the final measurement toward good answers. At depth p=1 for MaxCut on 3-regular graphs, QAOA provably achieves an approximation ratio of at least 0.6924 — better than random but short of the best classical algorithm (Goemans-Williamson at 0.878). As p increases, the approximation ratio improves.

In the limit p -> infinity, QAOA becomes equivalent to the quantum adiabatic algorithm: start in the ground state of B (the uniform superposition) and slowly interpolate the Hamiltonian from B to C. The adiabatic theorem guarantees that if the interpolation is slow enough, the system stays in the ground state, arriving at the optimal solution. QAOA with finite p is a Trotterized, variational version of this process. The open question is whether QAOA at moderate depth p = O(poly(n)) can achieve better approximation ratios than the best classical algorithms for specific problems. Recent results show that QAOA can outperform classical local algorithms on certain structured instances, but a definitive quantum advantage for optimization has not yet been demonstrated. QAOA remains one of the most studied algorithms for near-term quantum devices.