Tutte Distinguished Lecture - Mario Szegedy

Title: QAOA Versus Classical

Abstract: 

There has been a back and forth about whether the QAOA algorithm of Farhi, Goldstone and Gutmann can in some sense be duplicated classically. For the MAX-k-XOR problem QAOA achieves a 1/2 + Omega(1/D^(3/4)) approximation ratio (here D is a bound on the number of constraints that each variable occurs in), which at first was celebrated as a quantum advantage, until authors Barak et. al. have constructed a classical algorithm with approximation ratio1/2 + Omega(1/sqrt(D)). Most recently Hastings has found classical algorithms with better approximation ratios than QAOA, that are in addition local. We investigate these claims, as well as an earlier result of Farhi and Harrow which tackles the different issue of the impossibility of classically simulating the distribution that arises by running a QAOA algorithm.