Edward Farhi: An Update on the Quantum Approximate Optimization Algorithm
0The QAOA is a quantum algorithm designed to find good solutions to combinatorial optimization problems. It consists of an alternation of simple-to-implement unitary transformations. Worst case performance guarantees have been proven for MaxCut and other problems. For the Sherrington Kirkpatrick model, which has random all-to-all connections, QAOA performance has been established (up to depth 20) on typical instances in the infinite size limit. The QAOA has quantum supremacy at its shallowest depth both in worst case and for typical instances coming from the SK model. Obstacles to performance have been established using locality and the Overlap Gap property but these set in only at depth log n which in practice is millions of qubits. In general there is no hint from extensive numerical studies that the QAOA fails to improve performance as the depth is increased. Recently it has been shown that for MaxCut on 3-regular graphs, instance-independent parameters can be chosen in advance that work well on all instances at high sizes. This eliminates the necessity of searching for good parameters when running the algorithm.