(2020). Power and Limitations of the QAOA. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/tbd-132
MLA
Power and Limitations of the QAOA. The Simons Institute for the Theory of Computing, Feb. 26, 2020, https://simons.berkeley.edu/talks/tbd-132
BibTex
@misc{ scivideos_15412,
doi = {},
url = {https://simons.berkeley.edu/talks/tbd-132},
author = {},
keywords = {},
language = {en},
title = {Power and Limitations of the QAOA},
publisher = {The Simons Institute for the Theory of Computing},
year = {2020},
month = {feb},
note = {15412 see, \url{https://scivideos.org/Simons-Institute/15412}}
}
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.