The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Obstacles to Variational Quantum Optimization from Symmetry Protection
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“An empirical evaluation of recursive QAOA has demonstrated its superiority compared to the standard version as well as its competitiveness compared to the Newman benchmark algorithm [203] for the Max-Cut problem [23].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [23]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Quantum information and computation
Bennett, C. H., & DiVincenzo, D. P. (2000) · Nature · doi:10.1038/35005001 · Cited by 3,263
Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets
Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., & Gambetta, J. M. (2017) · Nature · doi:10.1038/nature23879 · Cited by 2,982
Barren plateaus in quantum neural network training landscapes
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2018) · Nature Communications · doi:10.1038/s41467-018-07090-4 · Cited by 2,329
Entanglement spectrum of a topological phase in one dimension
Pollmann, F., Turner, A. M., Berg, E., & Oshikawa, M. (2010) · Physical Review B · doi:10.1103/physrevb.81.064439 · Cited by 1,341
On the computational complexity of Ising spin glass models
Barahona, F. (1982) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/15/10/028 · Cited by 1,303
Tensor-entanglement-filtering renormalization approach and symmetry-protected topological order
Gu, Z., & Wen, X.-G. (2009) · Physical Review B · doi:10.1103/physrevb.80.155131 · Cited by 1,002
Classifying quantum phases using matrix product states and projected entangled pair states
Schuch, N., Pérez-Garcı́a, D., & Cirac, J. I. (2011) · Physical Review B · doi:10.1103/physrevb.84.165139 · Cited by 794
Research works printed but not linked: 3
- R. Shaydulin, 2019, Evaluating quantum approximate optimization algorithm: A case study, in 2019 Tenth International Green and Sustainable Computing Conference (IGSC)
- A. W. Marcus, 2015, Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science
- L. Eldar, 2017, Proceedings of the 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
Cited by
Sorted by citations
Variational quantum algorithms
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00348-9 · Cited by 3,385
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
Noise-induced barren plateaus in variational quantum algorithms
Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., & Coles, P. J. (2021) · Nature Communications · doi:10.1038/s41467-021-27045-6 · Cited by 773
A review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 563
Warm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269
Metadata
- Authors
- Bravyi, S., Kliesch, A., Koenig, R., & Tang, E.
- Affiliations
- IBM (United States) (US)
- Technical University of Munich (DE)
- California Institute of Technology (US)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2020-12-24
- Volume
- 125
- Issue
- 26
- Pages
- 260505-260505
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2980835754
- Cited by
- 278
- References
- 22
- Citations by year
- 2026: 23 · 2025: 50 · 2024: 52 · 2023: 71 · 2022: 42 · 2021: 31 · 2020: 8
- FWCI
- 14.93
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CaltechAUTHORS (California Institute of Technology) (submittedVersion)
- mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Army Research Office (W911NF-20-1-0014)
- Natural Sciences and Engineering Research Council of Canada
- National Science Foundation (PHY-1733907)
- Deutsche Forschungsgemeinschaft
- IBM Research Frontiers Institute
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Keywords
- quantum approximate optimization algorithm, variational quantum optimization, symmetry protection, Goemans-Williamson algorithm, MaxCut, frustrated Ising model
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
