Reachability Deficits in Quantum Approximate Optimization
Open accessAbstract
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithm's ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio-this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.
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?
A large-scale evaluation on QAOA validated the theoretical properties and yielded further empirical performance bounds.
“Continuing with empirical studies on gate-based quantum CO approaches, a large-scale evaluation on QAOA [92, 121] validated the theoretical properties [4, 21, 43] and yielded further empirical performance bounds.”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [4]
The Reachability Deficits section (p. 2) reports numerical analysis of critical QAOA depth, and the figure captions (p. 5) describe averages over 100 randomly generated instances, supporting the claim of empirical performance limits. Calling this a large-scale evaluation overstates the reported tests, which used six-variable SAT instances for the cited plots. The sentence cites other papers for the theoretical properties, so their validation is not established by this source alone. (LLM, conf=0.84)
Experimental — accuracy not yet measuredThe strong limitations concerning the reachability of QAOA have been numerically validated.
“The strong limitations concerning the reachability of QAOA have been numerically validated [4].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [4]
The reachability issue of QAOA has been theoretically proven and empirically validated.
“It has been theoretically proven [4, 43, 44] and empirically validated [121].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [4]
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 26 · Cited by 151
- Authors
- Akshay, V., Philathong, H., Morales, M. E. S., & Biamonte, J. D.
- Affiliations
- Skolkovo Institute of Science and Technology (RU)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2020-03-05
- Volume
- 124
- Issue
- 9
- Pages
- 090504-090504
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2955435611
- Cited by
- 151
- References
- 26
- Citations by year
- 2026: 8 · 2025: 31 · 2024: 17 · 2023: 24 · 2022: 27 · 2021: 29 · 2020: 14 · 2019: 1
- FWCI
- 9.23
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- OPUS - Open Publications of UTS Scholars (University of Technology Sydney) (submittedVersion)
- arXiv (Cornell University)
- 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 › Metaheuristic Optimization Algorithms Research
- Keywords
- quantum approximate optimization algorithm, variational quantum algorithms, algorithmic limitations, barren plateaus, 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
