skip to main content

IQIM Postdoctoral and Graduate Student Seminar

Friday, February 11, 2022
11:00am to 12:00pm
Add to Cal
Online Event
Quantum Approximate Optimization Algorithm: MaxCut, Spin Glass, and Beyond
Leo Zhou, Dubridge Postdoctoral Scholar, Preskill Group,

Abstract: The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth p, although most analytic results are limited to small constant p. In this talk, we analyze the QAOA to MaxCut on large-girth D-regular graphs, where we give an iterative formula to evaluate its performance for any D at any depth p. Looking at random D-regular graphs, at optimal parameters and as D goes to infinity, we find that the p=11 QAOA beats all assumption-free classical algorithms (known to us). While our iterative formula is derived from looking at a single tree subgraph, we show that it also gives the ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick spin glass defined on the complete graph. This suggests that quantum quench dynamics on the complete graph can be studied using the Bethe lattice. We also discuss generalization of our results to other problems such as Max-q-XORSAT.

Attend by zoom at

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