The DOI matches its Crossref record; 39 of the 42 references it cites were found in a registry or an index.
QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
Open accessAbstract
Computational quantum technologies are entering a new phase in which noisy intermediate-scale quantum computers are available, but are still too small to benefit from active error correction. Even with a finite coherence budget to invest in quantum information processing, noisy devices with about 50 qubits are expected to experimentally demonstrate quantum supremacy in the next few years. Defined in terms of artificial tasks, current proposals for quantum supremacy, even if successful, will not help to provide solutions to practical problems. Instead, we believe that future users of quantum computers are interested in actual applications and that noisy quantum devices may still provide value by approximately solving hard combinatorial problems via hybrid classical-quantum algorithms. To lower bound the size of quantum computers with practical utility, we perform realistic simulations of the Quantum Approximate Optimization Algorithm and conclude that quantum speedup will not be attainable, at least for a representative combinatorial problem, until several hundreds of qubits are available.
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
Figures
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 cited source doesn’t support the claim as written.
In the citing paper
“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 [24]
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“With such peculiarities in mind, one should also view the results of Guerreschi and Matsuura, who found the point of quantum supremacy for QAOA to be in the order of several hundred to thousand of qubits [56] and further raised scaling issues [60].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [56]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“Noisy computation leads to scaling issues for QAOA [56, 60].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [56]
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
Braun, W. J., & Murdoch, D. J. (2021) · Cambridge University Press eBooks · doi:10.1017/9781108993456.011 · Cited by 14,099
Nocedal, J., & Wright, S. J. (1999) · Springer eBooks · doi:10.1007/b98874 · Cited by 9,563
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · cited 1×
“Since quantum algorithms have a computational cost that is either polynomially [4] or exponentially lower [5] than their classical counterparts, for larger problem instances quantum algorithms provide an increasing advantage over classical approaches.”
BackgroundPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
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
Superconducting Circuits for Quantum Information: An Outlook
Devoret, M., & Schoelkopf, R. J. (2013) · Science · doi:10.1126/science.1231930 · Cited by 2,197
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789
Superconducting quantum circuits at the surface code threshold for fault tolerance
Barends, R., Kelly, J., Megrant, A., Veitia, A., Sank, D., Jeffrey, E., White, T. C., Mutus, J., Fowler, A. G., Campbell, B., et al. (2014) · Nature · doi:10.1038/nature13171 · Cited by 1,733
Research works printed but not linked: 1
- Mack, C. A. Learning and Intelligent Optimization. Springer-Verlag Berlin Heidelberg (2011).
Cited by
Sorted by citations
Parameterized quantum circuits as machine learning models
Benedetti, M., Lloyd, E., Sack, S., & Fiorentini, M. (2019) · Quantum Science and Technology · doi:10.1088/2058-9565/ab4eb5 · Cited by 1,528
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
Quantum Computing for Finance: State-of-the-Art and Future Prospects
Egger, D. J., Gambella, C., Marecek, J., McFaddin, S., Mevissen, M., Raymond, R., Simonetto, A., Woerner, S., & Yndurain, E. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3030314 · Cited by 466
Zhu, L., Tang, H. L., Barron, G. S., Calderon-Vargas, F. A., Mayhall, N. J., Barnes, E., & Economou, S. E. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.033029 · Cited by 293
Combinatorial optimization with physics-inspired graph neural networks
Schuetz, M. J. A., Brubaker, J. K., & Katzgraber, H. G. (2022) · Nature Machine Intelligence · doi:10.1038/s42256-022-00468-6 · Cited by 233
Metadata
- Authors
- Guerreschi, G. G., & Matsuura, A. Y.
- Affiliations
- Intel (United States) (US)
- Corresponding author
- Guerreschi, G. G.
- Venue
- Scientific Reports
- Published
- 2019-05-06
- Volume
- 9
- Issue
- 1
- Pages
- 6903-6903
- ISSN
- 2045-2322 (ISSN-L)
- PMC
- PMC6502860
- OpenAlex
- W2951211905
- Cited by
- 337
- References
- 42
- Citations by year
- 2026: 18 · 2025: 57 · 2024: 45 · 2023: 88 · 2022: 50 · 2021: 47 · 2020: 24 · 2019: 8
- FWCI
- 14.71
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Scientific Reports (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Department of Energy (-AC02-05CH11231, Contract No. DE-AC02-05-CH11231, 05CH11231, No. DE-AC02-05-CH11231, DE AC02 05CH11231, DE-AC02-)
- University of Texas at Austin
- National Energy Research Scientific Computing Center (DE–AC02–05CH11231, 05CH11231, AC02-05CH11231, Contract No. DE-AC02-05CH11231)
- Office of Science (No. DE-AC02- 05-CH11231, DEAC02–05CH11231, AC02-05CH11231, DE-AC02, 05CH11231, Contract No. DE-AC02-05CH11231)
- Department of Mechanical Engineering, University of Texas at Austin
- 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, MaxCut, quantum advantage, qubit requirements, NISQ devices, hybrid quantum-classical algorithms, combinatorial optimization
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
