IQIM Postdoctoral and Graduate Student Seminar

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 https://caltech.zoom.us/j/88407627311?pwd=RGx4MlpSUnBLbDJvdE4rS1FHbWZvUT09