Table of Contents
QAOA
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 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 to minimize the cost.
Circuit
The QAOA circuit starts from the uniform superposition and alternates between applying the problem Hamiltonian (encoding the cost function) and a mixing Hamiltonian for layers.
The classical optimizer minimizes the expected cost by choosing optimal angles. As , QAOA converges to the exact ground state of (the optimal solution). For finite , it gives an approximation.
Applications
QAOA is applied to combinatorial optimization problems such as MaxCut, graph coloring, travelling salesman, satisfiability (SAT), and portfolio optimization. For MaxCut, QAOA with provably achieves an approximation ratio of at least , slightly below the classical Goemans-Williamson bound of . Whether large- QAOA can surpass the best classical approximation algorithms for any problem remains an active research question.
