Adam Bouland (UC Berkeley)
Calvin Lab Auditorium
I will survey recent works highlighting the power and limitations of the quantum approximate optimization algorithm (QAOA). First I will discuss a recent paper of Hastings (arXiv:1905.07047) describing a local classical algorithm which outperforms p=1 QAOA on MAXCUT instances and which matches its performance on MAX-3LIN2. I will also discuss a recent paper of Bravyi, Kliesch, Koeing, and Tang (arXiv:1910.08980) which uses symmetries of the QAOA to prove that it will not outperform the Goemans-Williamson algorithm for MAXCUT for any value of p.