Obstacles to Variational Quantum Optimization from Symmetry Protection
Abstract
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.
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.Attached Files
Published - PhysRevLett.125.260505.pdf
Accepted Version - 1910.08980.pdf
Supplemental Material - Appendix_revised.pdf
Files
Additional details
- Alternative title
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Eprint ID
- 107288
- Resolver ID
- CaltechAUTHORS:20201224-134252357
- IBM Research Frontiers Institute
- W911NF-20-1-0014
- Army Research Office (ARO)
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- Institute for Quantum Information and Matter (IQIM)
- PHY-1733907
- NSF
- 2111
- Deutsche Forschungsgemeinschaft (DFG)
- Created
-
2021-01-04Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter