skip to main content

IQIM Postdoctoral and Graduate Student Seminar

Monday, June 3, 2024
4:00pm to 5:00pm
Add to Cal
East Bridge 114
The Virtues of the Quantum Approximate Optimization Algorithm
Edward Farhi, Principal Scientist, Google, & MIT,

Note this talk begins at 4 pm on Monday, June 3

Abstract: 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.

For more information, please contact Marcia Brown by phone at 626-395-4013 or by email at [email protected].