Talks
Spring 2020

Power and Limitations of the QAOA
Wednesday, Feb. 26, 2020 10:00 am – 10:30 am PST
Event:
Speaker:
Adam Bouland (UC Berkeley)
Location:
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.