University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

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


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.

MC - Mathematics & Computer Building
200 University Avenue West

Waterloo, ON N2L 3G1