TL;DR: QAOA (Farhi et al., 2014) is a hybrid quantum-classical algorithm for combinatorial optimization. It alternates between problem and mixer Hamiltonians, with parameters optimized classically. At p→∞, Q
QAOA (Farhi et al., 2014) is a hybrid quantum-classical algorithm for combinatorial optimization. It alternates between problem and mixer Hamiltonians, with parameters optimized classically. At p→∞, QAOA converges to the optimal solution. In practice, low-depth QAOA (p=1-10) is used on NISQ devices. Whether QAOA provides practical advantage over classical heuristics remains open.
Type
Combinatorial Optimization
Complexity
Heuristic - no proven speedup; competitive with classical for some problems
Application
Max-Cut, portfolio optimization, scheduling, logistics, vehicle routing