Tutte Distinguished Lecture - Mario SzegedyExport this event to calendar

Friday, July 19, 2019 — 3:30 PM EDT

Mario Szegedy headshot

Title: QAOA Versus Classical

Speaker: Mario Szegedy
Affiliation: Alibaba Quantum Laboratory
Room: MC 5501

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.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada