A Caltech Library Service

Obstacles to Variational Quantum Optimization from Symmetry Protection

Bravyi, Sergey and Kliesch, Alexander and Koenig, Robert and Tang, Eugene (2020) Obstacles to Variational Quantum Optimization from Symmetry Protection. Physical Review Letters, 125 (26). Art. No. 260505. ISSN 0031-9007. doi:10.1103/physrevlett.125.260505.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Accepted Version
See Usage Policy.

[img] PDF - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


The quantum approximate optimization algorithm (QAOA) employs variational states generated by a parameterized quantum circuit to maximize the expected value of a Hamiltonian encoding a classical cost function. Whether or not the QAOA can outperform classical algorithms in some tasks is an actively debated question. Our work exposes fundamental limitations of the QAOA resulting from the symmetry and the locality of variational states. A surprising consequence of our results is that the classical Goemans-Williamson algorithm outperforms the QAOA for certain instances of MaxCut, at any constant level. To overcome these limitations, we propose a nonlocal version of the QAOA and give numerical evidence that it significantly outperforms the standard QAOA for frustrated Ising models.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Bravyi, Sergey0000-0002-4032-470X
Kliesch, Alexander0000-0001-7973-9665
Koenig, Robert0000-0002-0563-1229
Alternate Title:Obstacles to State Preparation and Variational Optimization from Symmetry Protection
Additional Information:© 2020 American Physical Society. (Received 22 October 2019; revised 16 September 2020; accepted 3 December 2020; published 24 December 2020) The authors thank Giacomo Nannicini and Kristan Temme for helpful discussions. S. B. was partially supported by the IBM Research Frontiers Institute and by the Army Research Office (ARO) under Grant No. W911NF-20-1-0014. E. T. acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) and funding provided by the Institute for Quantum Information and Matter, an National Science Foundation (NSF) Physics Frontiers Center (NSF Grant No. PHY-1733907). R. K. and A. K. gratefully acknowledge support by the Deutsche Forschungsgemeinschaft cluster of excellence 2111 (Munich Center for Quantum Science and Technology) and by IBM.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
IBM Research Frontiers InstituteUNSPECIFIED
Army Research Office (ARO)W911NF-20-1-0014
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Deutsche Forschungsgemeinschaft (DFG)2111
Issue or Number:26
Record Number:CaltechAUTHORS:20201224-134252357
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:107288
Deposited By: George Porter
Deposited On:04 Jan 2021 17:48
Last Modified:16 Nov 2021 19:01

Repository Staff Only: item control page