CoChat
Sign Up
Cited by 337Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

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 access
Guerreschi, G. G., Matsuura, A. Y.·2019·Scientific Reports
DOI 10.1038/s41598-019-43176-9PMC PMC6502860
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/s41598-019-43176-9

Cites

39 of 39 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 Schematic diagram of the QAOA algorithm and auxiliary tasks to solve a single Max-Cut instance. The two branches, labelled “simulation” and “experiment” respectively, distinguish between the operations to simulate the variational algorithm with classical computers and those to perform it experimentally with quantum devices. In our study, 10000 samples are used to estimate the value of the cost function 〈γ,β|C|γ,β〉 at each variational iteration.
Figure 1 Schematic diagram of the QAOA algorithm and auxiliary tasks to solve a single Max-Cut instance. The two branches, labelled “simulation” and “experiment” respectively, distinguish between the operations to simulate the variational algorithm with classical computers and those to perform it experimentally with quantum devices. In our study, 10000 samples are used to estimate the value of the cost function 〈γ,β|C|γ,β〉 at each variational iteration.CC BY · PubMed Central
Figure 2 Main panel: Computational cost of solving a single Max-Cut instance on random 3-regular graphs. Blue markers correspond to the classical baseline (AKMAXSAT solver) while red and green marks correspond to the experimental time required by the quantum algorithm QAOA, with p = 4 and p = 8 respectively. The error bars for the single data points are smaller than the markers (see Supplementary Information). Notice that in the time needed by QAOA to partition graphs with 20 vertices, AKMAXSAT partitions graphs about 20 times larger. The blue dashed line is the result of a fitting procedure with an exponential function. The red and green areas are associated with a 95% confidence interval for the prediction of the QAOA cost based on a linear regression of log10(T) as a function of the number of qubits (here T is the computational time per instance). This extrapolation should be seen as suggesting a qualitative behavior due to the uncertainty in the extrapolation from relatively small system sizes. Insert panel: Magnification of QAOA datapoints. Notice that exponential curves, and smooth curves in general, locally resemble straight lines and this makes it difficult to exclude other functional forms for the extrapolation. It is, however, believed that even quantum computers will not be able to solve NP-hard problems in polynomial time.
Figure 2 Main panel: Computational cost of solving a single Max-Cut instance on random 3-regular graphs. Blue markers correspond to the classical baseline (AKMAXSAT solver) while red and green marks correspond to the experimental time required by the quantum algorithm QAOA, with p = 4 and p = 8 respectively. The error bars for the single data points are smaller than the markers (see Supplementary Information). Notice that in the time needed by QAOA to partition graphs with 20 vertices, AKMAXSAT partitions graphs about 20 times larger. The blue dashed line is the result of a fitting procedure with an exponential function. The red and green areas are associated with a 95% confidence interval for the prediction of the QAOA cost based on a linear regression of log10(T) as a function of the number of qubits (here T is the computational time per instance). This extrapolation should be seen as suggesting a qualitative behavior due to the uncertainty in the extrapolation from relatively small system sizes. Insert panel: Magnification of QAOA datapoints. Notice that exponential curves, and smooth curves in general, locally resemble straight lines and this makes it difficult to exclude other functional forms for the extrapolation. It is, however, believed that even quantum computers will not be able to solve NP-hard problems in polynomial time.CC BY · PubMed Central

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.

A few free checks a day · papers already verified open instantly · results are public

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?

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

Show all 42 references

Research works printed but not linked: 1

  1. Mack, C. A. Learning and Intelligent Optimization. Springer-Verlag Berlin Heidelberg (2011).

Cited by

Sorted by citations

Related

See all

Metadata

Authors
Guerreschi, G. G., & Matsuura, A. Y.
Affiliations
Intel (United States) (US)
Corresponding author
Guerreschi, G. G.
ORCID
Venue
Scientific Reports
Publisher
Springer Science and Business Media LLC
Published
2019-05-06
Volume
9
Issue
1
Pages
6903-6903
ISSN
2045-2322 (ISSN-L)
DOI
10.1038/s41598-019-43176-9
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
Licence
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