DQC Seminar Series: Recent updates on the Quantum Approximate Optimization Algorithm

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. 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. Furthermore QAOA performance guarantees can be turned into statements about the size of cuts in large girth 3-regular graphs and the QAOA is exponentially faster than the best known classical algorithms for finding these large cuts. --- Edward Farhi is a physicist working on quantum computation as a Principal Scientist at Google. In 2018 he retired from his position as Professor of Physics at the Massachusetts Institute of Technology where he served as the Director of Theoretical Physics for twelve years. Farhi was trained as a theoretical particle physicist with interests in astrophysics and general relativity where he made several notable contributions. Since the late 90's, he has been studying how to use quantum mechanics to gain algorithmic speedup in solving problems that are difficult for conventional computers. He along with collaborators introduced the idea of continuous time Hamiltonian based quantum computing which led to quantum walk algorithms and the quantum adiabatic algorithm. Farhi, Goldstone and Gutmann introduced the QAOA in 2014 and it has been the focus of many papers looking at shallow depth quantum algorithms for optimization. --- Spring 2025 Upcoming Speakers 23 Jan: Lu Qi 6 Feb: Andrei Ruskuc 20 Feb: Noah Shutty 6 Mar: TBA 20 Mar: Kristi Beck 27 Mar: Peter Shor 3 Apr: Ed Farhi 17 Apr: Anthony Ransford