The Quantum Approximate Optimization Algorithm (QAOA), introduced by Farhi, Goldstone, and Gutmann in 2014, is a variational algorithm designed for combinatorial optimization problems such as MaxCut, portfolio optimization, vehicle routing, and scheduling. It applies alternating layers of a problem-specific cost Hamiltonian and a mixing Hamiltonian to a uniform superposition state, with layer angles optimized classically to maximize the expected quality of the solution.
At depth p (number of alternating layers), QAOA interpolates between a purely classical solution (p=0, random guess) and the optimal solution (p→∞, equivalent to quantum adiabatic computation). Low-depth QAOA (p=1-5) produces approximate solutions that may not be optimal but can be generated quickly on NISQ hardware. The quality of approximation generally improves with depth, but deeper circuits are more susceptible to noise, creating a tension between solution quality and hardware limitations.
QAOA has attracted significant commercial interest because combinatorial optimization problems are ubiquitous in industry — logistics, finance, supply chain, drug discovery, and telecommunications all involve NP-hard optimization problems where even modest improvements have large economic value. However, rigorous evidence that QAOA provides speedup over classical optimization heuristics for practical problem sizes is lacking. Classical algorithms like simulated annealing, branch-and-bound, and modern SAT solvers are extremely well-optimized and continue to improve. The honest assessment is that demonstrating practical quantum advantage for optimization remains an open challenge.