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
Items 201–279 of 279
Learning to Learn With Quantum Optimization Via Quantum Neural Networks
Chen, K., Matsuyama, H., & Huang, W. (2025) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce65121.2025.00172 · Cited by 3
Error Analysis of the Variational Quantum Eigensolver Algorithm
Brandhofer, S., Devitt, S. J., & Polian, I. (2021) · IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH) · doi:10.1109/nanoarch53687.2021.9642249 · Cited by 5
Machine-learning-inspired quantum control in many-body dynamics
Mao, M.-Y., Cheng, Z., Li, L., Wu, N., & You, W. (2024) · Physical Review A · doi:10.1103/physreva.109.042428 · Cited by 2
Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
Wagner, F., Nüßlein, J., & Liers, F. (2025) · ACM Transactions on Quantum Computing · doi:10.1145/3711935 · Cited by 13
An introduction to variational quantum algorithms for combinatorial optimization problemsPreprint
Grange, C., Poss, M., & Bourreau, E. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2212.11734 · Cited by 2
Efficient large-scale quantum optimization via counterdiabatic ansatz
Liu, J., & Wang, X. (2025) · Physical Review A · doi:10.1103/physreva.111.052628 · Cited by 1
The Symmetry‐Based Expressive QAOA for the MaxCut Problem
Xiumei, Z., Li, Y., Li, G., Shi, Y., Qin, S., & Gao, F. (2025) · Advanced Quantum Technologies · doi:10.1002/qute.202500199 · Cited by 2
Edge-based quantum approximate optimization algorithm for MAX-CUT problem
Seo, Y., & Heo, J. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04925-0 · Cited by 2
Mooney, G. J., Villanueva, J., Bardhan, B. R., Ghosh, J., Hill, C. D., & Hollenberg, L. C. L. (2026) · Physical Review Research · doi:10.1103/xv79-w3rs · Cited by 3
Theoretical approximation ratios for Warm-Started QAOA on 3-regular max-cut instances at depth p = 1
Tate, R., & Eidenbenz, S. (2025) · Theoretical Computer Science · doi:10.1016/j.tcs.2025.115571 · Cited by 1
Quantum optimization with classical chaos
Gaye, M. A., Shehab, O., Titum, P., & Quiroz, G. (2026) · Quantum Science and Technology · doi:10.1088/2058-9565/ae59ad · Cited by 2
Co-designed counterdiabatic quantum optimization on a photonic quantum processor
Shang, X.-W., Chen, X., Hegade, N. N., Lan, Z.-F., Tang, H., Dou, J.-P., Li, X.-K., Peng, Y.-Q., Solano, E., & Jin, X. (2026) · Physical Review Applied · doi:10.1103/7gl4-zrh6 · Cited by 3
Variational simulation of higher-spin systems on qubit-based quantum simulators
Lyu, C., Zou, Z., Xu, X., Yung, M., & Bayat, A. (2026) · Physical Review Research · doi:10.1103/lfc9-cjqd · Cited by 3
Progressive quantum algorithm for maximum independent set with quantum alternating operator ansatz
Ni, X., 李, L.-X. 凌. L., Song, Y., 金, Z.-P. 正. J., Qin, S., & Gao, F. (2025) · Chinese Physics B · doi:10.1088/1674-1056/addd83 · Cited by 7
Coreset Clustering on Small Quantum Computers
Tomesh, T., Gokhale, P., Anschuetz, E. R., & Chong, F. T. (2021) · Electronics · doi:10.3390/electronics10141690 · Cited by 27
An Automatic Approach for Combinational Problems on a Hybrid Quantum Architecture
Shu, G., Wang, J., Shan, Z., Liu, F., Liu, Z., & Guo, G. (2021) · SPIN · doi:10.1142/s2010324721400063 · Cited by 1
Solving a puzzle with atomic qubits
Schleier-Smith, M. (2022) · Science · doi:10.1126/science.abq3754 · Cited by 1
Improving the Quantum Approximate Optimization Algorithm with postselectionPreprint
Boulebnane, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.05425 · Cited by 3
Classical algorithms for ForrelationPreprint
Bravyi, S. B., Gosset, D., Grier, D., & Schaeffer, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.06963 · Cited by 17
Self-citationOptimized fermionic SWAP networks with equivalent circuit averaging for QAOAPreprint
Hashim, A., Rines, R., Omole, V., Naik, R., Kreikebaum, J. M., Santiago, D., Chong, F. T., Siddiqi, I. A., & Gokhale, P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.04572 · Cited by 1
Mitigating Noise-Induced Gradient Vanishing in Variational Quantum Algorithm TrainingPreprint
Wu, A., Li, G., Ding, Y., & Xie, Y. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.13209 · Cited by 7
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0003 · Cited by 1
Benchmarking the recursive quantum approximate optimization algorithm
Frederick, P., Rines, R., Chong, F. T., & Gokhale, P. (2023) · Quantum Computing, Communication, and Simulation · doi:10.1117/12.2648434
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0006
Microwave resonators for superconducting devices
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0013
(2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.002.0003
The rotating wave approximation
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0001
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0004
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0007
Quantum simulation of Hamiltonian eigenstates
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0012
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0002
Quantum simulation of Hamiltonian dynamics
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0011
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0009
The molecular Hamiltonian in second quantization
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0004
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0005
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0008
Oblivious amplitude amplification lemma
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0005
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0006
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0003
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0001
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0014
(2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.002.0005
(2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.002.0004
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.003.0010
MVITA, M. J., Zulu, N. G., Thethwayo, B., & Makhamisa, S. (2023) · International Conference on Industrial Engineering and Operations Management (IEOM) · doi:10.46254/eu6.20230207
A hybrid quantum-classical approach to warm-starting optimization
Dehn, V., & Wellens, T. (2024) · Quantum Computing, Communication, and Simulation · doi:10.1117/12.3002220
Qubit-efficient quantum combinatorial-optimization solver
Sundar, B., & Dupont, M. (2026) · Physical Review Applied · doi:10.1103/s5jv-jh24 · Cited by 2
Yoshioka, T., Sasada, K., Nakano, Y., & Fujii, K. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00061
XY-mixer ansatz assisted by counterdiabatic driving for combinational optimization
Ruan, Y., Chen, P., Li, Q., Yang, L., Yuan, Z., Xue, X., Li, X., & Liu, Z. (2025) · Physical Review Research · doi:10.1103/physrevresearch.7.013243 · Cited by 1
Quantum Amplitude‐Phase Judgment Circuits for Full Quantization Algorithms
Dong, Z., Wang, H., Zeng, Y., & Chang, S. (2025) · Advanced Quantum Technologies · doi:10.1002/qute.202400596
A quantum constraint generation framework for binary linear programs
Czégel, A., & G.-Tóth, B. (2025) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-025-00364-z · Cited by 1
A Recursive Estimation Algorithm for Fast Variational Quantum Algorithms
Kahani, S. S., & Nobakhti, A. (2025) · Lecture notes in networks and systems · doi:10.1007/978-3-031-92602-0_1
Mitigating the barren plateau problem in linear optics
Horner, M. D. (2026) · Physical Review A · doi:10.1103/xndq-ttdj
Wehbe, A., AlKhatib, S., & Ahmad, A. (2025) · Physica Scripta · doi:10.1088/1402-4896/ae22a2
An Adaptive Mixer Allocation Strategy for the Quantum Alternating Operator Ansatz
Ni, X., Wu, Y., Cai, B., Li, W., Qin, S., & Gao, F. (2025) · Advanced Quantum Technologies · doi:10.1002/qute.202500487 · Cited by 5
Exploring Beamforming Solutions Using Recursive Quantum Approximate Optimization Algorithm
Dhara, B., Agrawal, M., & Roy, S. D. (2025) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce65121.2025.00014
Quantum-Guided Cluster Algorithms for Combinatorial Optimization
Eder, P., Kerschbaumer, A., Finžgar, J. R., Medina, R. A., Schuetz, M. J. A., Katzgraber, H. G., Braun, S., & Mendl, C. B. (2025) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce65121.2025.00033
Q-CHOP: Quantum constrained Hamiltonian optimization
Perlin, M. A., Shaydulin, R., Hall, B., Minssen, P., Li, C., Dubey, K., Rines, R., Anschuetz, E. R., Pistoia, M., & Gokhale, P. (2025) · ACM Transactions on Quantum Computing · doi:10.1145/3778864 · Cited by 1
Encodings of the weighted MAX k-CUT problem on qubit systems
Fuchs, F. G., Bassa, R. P., & Lien, F. (2025) · Frontiers in Quantum Science and Technology · doi:10.3389/frqst.2025.1636042
Egger, D. J., Riel, H., Woerner, S., & Zoufal, C. (2025) · Springer eBooks · doi:10.1007/978-3-031-90727-2_6
Hao, Y. (2025) · 2025 5th International Conference on Electronic Information Engineering and Computer Technology (EIECT) · doi:10.1109/eiect68017.2025.11331653
Scalable Quantum Approximate Optimisation with Adaptive Bayesian Dimensionality Reduction
Alizadeh, A., Pourabdollah, A., & Lotfi, A. (2025) · IEEE International Conference on Quantum Artificial Intelligence (QAI) · doi:10.1109/qai63978.2025.00037
Ramos-Ruiz, P., Fuentes-Jiménez, A. M., Ramos-Ruiz, J. E., & Jiménez-Manchado, I. (2026) · AppliedMath · doi:10.3390/appliedmath6020024 · Cited by 2
Performance of parity QAOA for the signed Max-Cut problem
Weidinger, A., Mbeng, G. B., FELLNER, M. J., Khachatryan, D., & Lechner, W. (2026) · New Journal of Physics · doi:10.1088/1367-2630/ae49b6
Quantum algorithms for energy management optimization problems
Veshchezerova, M. (2022) · theses.fr (ABES) · doi:10.70675/f0d70a66z3066z4c81z8aa7zf9e72830f940 · Cited by 1
QAOA for Hard-to-solve Instances of Maximum Independent Set ProblemPreprint
Li, X., Hu, S., Liu, W., He, X., Wang, D., & Liu, Z. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.6669349
Quantum Optimization and Local Search on Conflict Graphs for Radio Resource Allocation
Gavrilovskaia, M., & Chen, K. (2026) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2026.3690424
Quantum optimization algorithms for strongly correlated many-body systems
Pexe, G. E. L., Rattighieri, L. A. M., Prado, P. B. B., Fritsch, A. R., & Fanchini, F. F. (2026) · Journal of Physics Condensed Matter · doi:10.1088/1361-648x/ae9dd5
Quantum-Inspired Fuzzy Committee Optimization for Blockchain Consensus
Sabeshuly, I., Yahia, S. B., & Akzhalova, A. Z. (2026) · Communications in computer and information science · doi:10.1007/978-3-032-28997-1_18
Current Technological Advances in Quantum Computing
Yadav, P., & Kumari, J. (2026) · Advances in computational intelligence and robotics book series · doi:10.4018/979-8-2600-0156-1.ch011
Daka, C., & Bhattacharyya, S. (2026) · New Journal of Physics · doi:10.1088/1367-2630/ae8053 · Cited by 1
MPE-Adam: Multi-Population Evolutionary Optimization with Adam Refinement for QAOA
Luu, C. Q., Vu, T., & Le, J. (2026) · 2026 IEEE International Conference on Quantum Software (QSW) · doi:10.1109/qsw72780.2026.00037
Sarkar, P., Hassan, M. M. U., Rambe, A. H., & Jusoh, M. (2026) · Archives of Computational Methods in Engineering · doi:10.1007/s11831-026-10716-2
Quantum Davis-Putnam-Logemann-Loveland and generalized constraints in iterative quantum algorithms
Anonymous, & Hadfield, S. (2026) · Physical Review A · doi:10.1103/8g3p-tyz1
Quantum-informed reduction algorithm for the maximum independent set problem
Schuetz, M. J. A., Yalovetzky, R., Andrist, R. S., Salton, G., Sun, Y., Raymond, R., Chakrabarti, S., Acharya, A., Shaydulin, R., Pistoia, M., et al. (2026) · Physical Review Research · doi:10.1103/nh3b-1wv5 · Cited by 3
A review of variational quantum algorithms: Insights into fault-tolerant quantum computing
Wang, Z., Huang, J., Ye, R., Li, Q., Ding, Q.-M., Huang, Y., Zhang, T., Zeng, Y., Gao, J., Yuan, X., et al. (2026) · Frontiers of Physics · doi:10.15302/frontphys.2027.023301 · Cited by 7
Núñez, J., & Fiorelli, R. (2026) · Neuromorphic Computing and Engineering · doi:10.1088/2634-4386/ae9006
Quantum Single-Path Transmission Optimization of Complex Networks
Wang, Z., Gao, F., Xu, Y., Wang, X., & Fang, J. (2026) · Entropy · doi:10.3390/e28080900
Lu, Y.-C., & Chen, T.-H. (2026) · International Conference on Big Data Computing Service and Applications · doi:10.1109/bigdataservice70481.2026.00030
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
