15412

Video URL

https://simons.berkeley.edu/talks/tbd-132

Power and Limitations of the QAOA

(2020). Power and Limitations of the QAOA. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/tbd-132

Power and Limitations of the QAOA. The Simons Institute for the Theory of Computing, Feb. 26, 2020, https://simons.berkeley.edu/talks/tbd-132 

          @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}}
          }
Adam Bouland (UC Berkeley)
Talk number15412
Source RepositorySimons Institute
Subject

Abstract

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.