The Virtues of the Quantum Approximate Optimization Algorithm
4Edward Farhi (Google)
https://simons.berkeley.edu/talks/edward-farhi-google-2024-04-24
Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms
The 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 properly. However these limitations are shown only at small constant times log(n) depth. In practice these limitations mean that at, say, one million logical qubits the QAOA is limited for certain problems if the depth is less than ten. In general there is no hint from extensive numerical studies that the QAOA fails to improve performance as the depth is increased. It is possible that the QAOA at sufficient and experimentally realizable depth will be of computational use.