Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
Open accessAbstract
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
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
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?
Several quantum machine learning algorithms based on parameterized quantum circuits have demonstrated superior performance and computational abilities compared to conventional algorithms.
“Several QML algorithms based on PQC have been proposed [21–27], demonstrating superior performance and computational abilities compared to conventional algorithms [28–31].”
From Medical image diagnosis based on adaptive Hybrid Quantum CNN (2023) · cites this paper as [25]
The Introduction describes QAOA as a variational-circuit algorithm with performance guarantees and states that it is not efficiently simulatable by classical computers. But Section II calls an advantage over classical algorithms *potential*, and the large-problem implementation section says it remains to be seen whether QAOA can outperform a classical MaxCut algorithm. The paper therefore does not establish the claimed demonstrated superiority over conventional algorithms. (LLM, conf=0.87)
Experimental — accuracy not yet measuredInitial parameters for VQAs may be taken from previous, similar problems.
“Initial parameters for VQAs may be taken from previous, similar problems [123, 154] or be obtained by machine learning approaches, which additionally can be used for finding patterns in parameters and parameter optimization.”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [154]
Section III.B describes using optimized QAOA parameters at level p to initialize optimization at level p+1. This supports reusing parameters from an earlier, closely related optimization, but the passage concerns a different QAOA depth rather than a previous, similar problem. (LLM, conf=0.82)
Experimental — accuracy not yet measuredComparative evaluation studies have demonstrated the ability of QAOA to harness diabatic processes in contrast to QA.
“Last, comparative evaluation studies between VQAs and QA have demonstrated (i) the reachability issues of QAOA compared to VQE [10], (ii) the ability of QAOA to harness diabatic processes in contrast to QA [154], (iii) the superiority of QA in terms of performance [142], and (iv) the character of QAOA as a digitized version of QA [141].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [154]
In “Beyond the adiabatic mechanism: A case study,” the paper says QAOA can exploit diabatic transitions to overcome limitations of adiabatic QA. But it also says diabatic QA can overcome those limitations, and “Comparing QAOA with quantum annealing” suggests optimized QA could match QAOA. The contrast is supported for adiabatic QA, not QA generally. (LLM, conf=0.88)
Experimental — accuracy not yet measuredComparisons with classical algorithms, including simulated annealing, Tabu Search, branch-and-bound, and CPLEX, show a scaling advantage for LR-QAOA in time-to-solution for random WMaxcut instances.
“Comparisonswithclassical algorithms, including simulated annealing, Tabu Search, and branch-andbound, show a scaling advantage for LR-QAOA.”
From Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems (2025) · cites this paper as [14]
Section V compares QAOA with quantum annealing, not LR-QAOA with the named classical algorithms. Section VI.B mentions classical MaxCut solvers as potential benchmarks, but reports no time-to-solution scaling advantage for random weighted MaxCut instances. Searches for LR-QAOA, simulated annealing, Tabu Search, branch-and-bound, and CPLEX found no supporting comparison; page numbers were unavailable in our copy. (LLM, conf=0.76)
Experimental — accuracy not yet measuredThe cost landscape is flattened, and hence gradient magnitudes are reduced, by the presence of incoherent noise.
“As discussed in the section on BPs, the intuition behind this slowing down is that the cost landscape is flattened, and hence gradient magnitudes are reduced, by the presence of incoherent noise [202, 230, 231].”
From Variational quantum algorithms (2021) · cites this paper as [202]
The “Finite measurement samples” section discusses measurement projection noise, and Appendix G discusses calculating gradients, but neither links incoherent noise to a flattened cost landscape or reduced gradient magnitudes. Searches for incoherent noise, noise-induced barren plateaus, and landscape flattening found no passage making that claim. Page numbers were not available in our copy. (LLM, conf=0.73)
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.
The citation lists haven’t been fetched yet
References 55 · Cited by 913
Research works printed but not linked: 18
- E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028. · arXiv
- J. S. Otterbach et al., Unsupervised Machine Learning on a Hybrid Quantum Computer, arXiv:1712.05771. · arXiv
- G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C. Baldwin, L. T. Brady, A. Deshpande, F. Liu, S. Jordan, A. V. Gorshkov, and C. Monroe, Quantum Approximate Optimi- zation with a Trapped-Ion Quantum Simulator, arXiv: 1906.02700. · arXiv
- E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem, arXiv:1412.6062. · arXiv
- E. Farhi and A. W. Harrow, Quantum Supremacy through the Quantum Approximate Optimization Algorithm, arXiv: 1602.07674. · arXiv
- M. B. Hastings, Classical and Quantum Bounded Depth Approximation Algorithms, arXiv:1905.07047. · arXiv
- S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obstacles to State Preparation and Variational Optimization from Symmetry Protection, arXiv:1910.08980. · arXiv
- E. Crosson, E. Farhi, C. Y.-Yu. Lin, H.-H. Lin, and P. Shor, Different Strategies for Optimization Using the Quantum Adiabatic Algorithm, arXiv:1401.7320. · arXiv
- P. Berman and M. Karpinski, On Some Tighter Inapprox- imability Results (Extended Abstract) (Springer, Berlin, 1999), pp. 200-209.
- E. R. Anschuetz, J. P. Olson, A. Aspuru-Guzik, and Y. Cao, Variational Quantum Factoring, arXiv:1808.08927. · arXiv
- P. I. Frazier, A Tutorial on Bayesian Optimization, arXiv: 1807.02811. · arXiv
- L. D. Landau, Zur Theorie der Energieubertragung II, Z. Sowjetunion 2, 46 (1932);
- H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays, arXiv:1808.10816. · arXiv
- H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Computational Complexity of the Rydberg Blockade in Two Dimensions, arXiv:1809.04954. · arXiv
- G. G. Guerreschi and M. Smelyanskiy, Practical Optimi- zation for Hybrid Quantum-Classical Algorithms, arXiv: 1701.01450. · arXiv
- E. Cuthill and J. McKee, Reducing the Bandwidth of Sparse Symmetric Matrices, in Proceedings of the 24th National Conference, ACM '69 (Association for Computing Machinery, New York, 1969), pp. 157-172.
- A. Vahdatpour, F. Dabiri, M. Moazeni, and M. Sarrafzadeh, Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks, in Distri- buted Computing (Springer, Berlin, 2008), pp. 481-495.
- G. E. Crooks, Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem, arXiv:1811.08419. · arXiv
- Authors
- Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D.
- Affiliations
- Harvard University (US)
- Venue
- Physical Review X
- Publisher
- American Physical Society (APS)
- Published
- 2020-06-24
- Volume
- 10
- Issue
- 2
- ISSN
- 2160-3308 (ISSN-L)
- OpenAlex
- W2903058119
- Cited by
- 913
- References
- 55
- Citations by year
- 2026: 110 · 2025: 185 · 2024: 162 · 2023: 151 · 2022: 120 · 2021: 105 · 2020: 56 · 2019: 21 · 2018: 3
- FWCI
- 42.46
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- Locations
- Physical Review X (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- Funders
- National Science Foundation
- Air Force Office of Scientific Research
- U.S. Department of Energy
- Defense Advanced Research Projects Agency
- Adolph C. and Mary Sprague Miller Institute for Basic Research in Science, University of California Berkeley
- Institute for Theoretical Atomic, Molecular and Optical Physics, Harvard University
- Smithsonian Astrophysical Observatory
- Harvard University
- Center for Ultracold Atoms
- Vannevar Bush Faculty Fellowship
- Google Research Award
- 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 › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- quantum approximate optimization algorithm, MaxCut, combinatorial optimization, variational quantum algorithms, parameter optimization, spectral gap, quantum annealing, hybrid quantum-classical algorithms, neutral-atom quantum processors, quantum fluctuations, resource analysis, near-term quantum devices
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
