The DOI matches its Crossref record; 49 of the 50 references it cites were found in a registry or an index, and 1 are not checked yet; 13 of the 18 sources its claims cite were checked for support.
Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems
Open accessAbstract
The quantum approximate optimization algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters $${\{{\gamma }_{i},{\beta }_{i}\}}_{i = 0}^{p-1}$$ { γ i , β i } i = 0 p − 1 . While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to N q = 42 qubits and p = 400 layers suggest that the success probability scales as $$P({x}^{* })\approx {2}^{-\eta (p){N}_{q}+C}$$ P ( x * ) ≈ 2 − η ( p ) N q + C , where η ( p ) decreases with increasing p . For example, in Weighted Maxcut instances, η (10) = 0.22 improves to η (100) = 0.05. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to N q = 109 qubits, p = 100, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA.
Verified 2026-10-05 · 1 reference not checked yet
Overview
CoChat Summary
## TL;DR
This paper introduces a fixed linear-ramp QAOA protocol (LR-QAOA) and reports numerical and experimental evidence that it can solve several combinatorial optimization problems with good success probability, sometimes with a scaling advantage over classical heuristics. The authors also show that LR-QAOA is resilient to noise on real quantum hardware and present a simple two-qubit-gate-count noise model that matches experiments.
## Key findings
- Simulations on up to Nq = 42 qubits and p = 400 layers suggest the success probability follows \(P(x^*) \sim 2^{\eta(p)N_q + C}\), with \(\eta(p)\) decreasing as p increases.
- For Weighted Maxcut, the fitted scaling parameter changes from \(\eta(10)=0.22\) to \(\eta(100)=0.05\), indicating improved performance with more layers.
- In a scaling comparison on fully connected random WMaxcut, LR-QAOA shows a potential scaling advantage over simulated annealing, Tabu search, and CPLEX; the reported relative error of the perceived scaling is 0.011 for LR-QAOA versus 0.023 (SA), 0.019 (Tabu), and 0.211 (CPLEX).
- On hardware, the authors test LR-QAOA on IonQ, Quantinuum, and IBM devices with up to 109 qubits, p = 100, and circuits with up to 21,200 CNOT gates; for a 25-qubit WMaxcut instance, Quantinuum H2 reaches a maximum success probability of 0.10 at p = 75 and a maximum approximation ratio of 0.95 at p = 50.
- For a 30-qubit WMaxcut instance on ibm_brisbane, the paper reports finding the optimal solution 2 times at 13 layers using 10,000 samples and mitigation, corresponding to an improvement over random guessing of about 1732×.
## Methods
- The paper studies linear-ramp QAOA (LR-QAOA), a fixed-parameter version of QAOA characterized by three tunable values: \(\Delta\beta\), \(\Delta\gamma\), and p.
- Numerical experiments cover multiple combinatorial optimization problems, including MIS, BPP, TSP, Maxcut, WMaxcut, 3-Maxcut, KP, PO, Max-2-SAT, and Max-3-SAT, using random instances with sizes ranging from 4 to 42 qubits and depths from p = 3 to 400.
- For scaling comparisons, the authors benchmark LR-QAOA against simulated annealing, Tabu search, and CPLEX using time-to-solution (TTS); for experiments they also use a depolarizing noise model on 2-qubit gates and compare against real hardware results from ibm_fez, ibm_brisbane, ibm_kyoto, ibm_osaka, ionq_aria, and quantinuum_H2.
## Limitations
- The paper states that for the simulation protocol, \(\Delta\gamma\) and \(\Delta\beta\) were scanned on one instance per problem size and then reused for the other cases; the authors note this is “not optimal” because ideally parameters should be tuned for each instance.
- The authors explicitly say the observed scaling “still needs to be corroborated at a larger problem size” to confirm that the probability of success truly decreases exponentially.
- Evident from the text: several claims rely on empirical fits and problem-specific noise parameters (for example, the fitted parameter \(k_0=1.82\) for WMaxcut and the device-specific error rates), so the generality beyond the tested problems and hardware is not established in the paper.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
10 Valid · 6 Not valid · 3 Not checked · 66 Own results and interpretations
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“For instance, there is a case with 500 qubits and 6256 edges (see Table 7, R 500 005 1 in ref. 37) for which the optimal solution is not known.”
What the sources say
- Partly supportedcites [37] Koch, T. et al. Quantum optimization benchmark library—the intractable decathlon. Preprint at arXiv https://arxiv.org/abs/2504.03832 (2025). sourceExperimental — accuracy not yet measured
Table 1 (Main; page unavailable) lists a 500-variable Independent Set problem, and Results says that larger instances are more likely to lack a known optimal solution. Our copy does not identify an instance named R 500 005 1, give it 6,256 edges, or establish that its optimum is unknown. It also describes variables rather than a run using 500 qubits. (LLM, conf=0.78)
plainSingle case- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Partly supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“there is no guarantee that the optimal solution of the original problem is encoded in the ground state of the Hamiltonian (see also the discussion in ref. 39).”
What the sources say
- Supportedcites [39] Montanez-Barrera, A., Willsch, D., Maldonado-Romo, A. & Michielsen, K. Unbalanced penalization: a new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms. Quantum Sci. Technol. https://doi.org/10.1088/2058-9565/ad35e4 (2024). source
The Optimal solution distribution section (p. 7) explicitly says unbalanced penalization does not ensure that the optimal solution is the lowest eigenvalue of the cost Hamiltonian. The Quantum Annealing section (p. 8) likewise says the optimal solution cannot be guaranteed to be its ground state. (LLM, conf=0.95)
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA.”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Using p = Nq , we fi nd that on average, the probability ( x * ) remains nearly constant for WMaxcut, Maxcut, and Max-3-SAT.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
In the paper
“There is a high correlation coef fi cient (PCC = 0.7) 29 between the solvers ' TTS”
What the sources say
- Not checked — no full text of the sourcecites [29] Kirch, W. (ed). Pearson’s Correlation Coefficient, 1090–1091 (Springer Netherlands, Dordrecht, 2008). https://doi.org/10.1007/978-1-4020-5614-7_2569. source
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
34 more claims
Create a free account to see all 85 claims and every source verdict.
- It may state two separate claims as one. 27
- Probably not a substantial claim. 22
- The quote only partly states this claim. 1
Citations
Cites
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Quantum supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720
Self-citationVariational quantum algorithms
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00348-9 · Cited by 3,385 · cited 3×
“Deep QAOA circuits, when viewed through the lens of VQA, lead to a pessimistic conclusion regarding their universal applicability 13 .”
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Evidence for the utility of quantum computing before fault tolerance
Kim, Y., Eddins, A., Anand, S., Wei, K. X., van den Berg, E., Rosenblatt, S., Nayfeh, H., Wu, Y., Zaletel, M., Temme, K., et al. (2023) · Nature · doi:10.1038/s41586-023-06096-3 · Cited by 1,050
Randomized benchmarking of quantum gates
Knill, E., Leibfried, D., Reichle, R., Britton, J., Blakestad, R. B., Jost, J. D., Langer, C., Ozeri, R., Seidelin, S., & Wineland, D. J. (2008) · Physical Review A · doi:10.1103/physreva.77.012307 · Cited by 1,019 · cited 1×
“These errors are similar to the average 2-qubit gate error measured by Randomized benchmarking (RB) 32 , which is 36 × 10 − 4 for ibm_fez and 9 × 10 − 4 for H1-1.”
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913 · cited 17×
“WecompareSA,LR-QAOA,TABU,andCPLEX intermsofTTSfortheseproblems,observingabetterscalinginLR-QAOA.”
InfluentialQuantum approximate optimization of non-planar graph problems on a planar superconducting processor
Harrigan, M. P., Sung, K. J., Neeley, M., Satzinger, K. J., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Barends, R., Boixo, S., et al. (2021) · Nature Physics · doi:10.1038/s41567-020-01105-y · Cited by 564
Research works printed but not linked: 1
- Bliek, C., Bonami, P. & Lodi, A. Solving mixed-integer quadratic programming problems with ibm-cplex: a progress report https://api.semanticscholar.org/CorpusID:16208906 (2014).
Cited by
Quantum approximate multi-objective optimization
Kotil, A., Pelofske, E., Riedmüller, S., Egger, D. J., Eidenbenz, S., Koch, T., & Woerner, S. (2025) · Nature Computational Science · doi:10.1038/s43588-025-00873-y · Cited by 63
Penalty-free approach to accelerating constrained quantum optimization
Bucher, D., Stein, J., Feld, S., & Linnhoff–Popien, C. (2025) · Physical Review A · doi:10.1103/fb5m-cl9m · Cited by 30
Optimization via quantum preconditioning
Dupont, M., Oberoi, T., & Sundar, B. (2025) · Physical Review Applied · doi:10.1103/9prw-684p · Cited by 10
Krüger, T., & Mauerer, W. (2025) · Quantum · doi:10.22331/q-2025-11-06-1903 · Cited by 7
Dehn, V., Zaefferer, M., Hellstern, G., Jayadevan, K., Reiter, F., & Wellens, T. (2026) · Physical Review A · doi:10.1103/l5r4-zcqv · Cited by 12
Metadata
- Authors
- Montañez-Barrera, J. A., & Michielsen, K.
- Affiliations
- Forschungszentrum Jülich (DE)
- Corresponding author
- Montañez-Barrera, J. A.
- Venue
- npj Quantum Information
- Published
- 2025-08-04
- Volume
- 11
- Issue
- 1
- ISSN
- 2056-6387 (ISSN-L)
- OpenAlex
- W4412933107
- Cited by
- 34
- References
- 47
- Citations by year
- 2026: 20 · 2025: 14
- FWCI
- 13.75
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- Locations
- npj Quantum Information (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, cc-by)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- RWTH Publications (RWTH Aachen) (submittedVersion, other-oa)
- arXiv (Cornell University) (cc-by)
- JuSER Publikationsportal
- Funders
- Bundesministerium für Bildung und Forschung (13N16149)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum approximate optimization algorithm, combinatorial optimization, variational parameter optimization, noise models
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.
The claim verdicts this report counts are experimental: their accuracy is not yet measured.
A language model drew the claims from the paper on 2026-09-29, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-09-29 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Cited sources are checked with a language model’s help (gpt-6-sol).
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems. https://app.cochat.ai/papers/10.1038/s41534-025-01082-1
- The paper
- Montañez-Barrera, J. A., & Michielsen, K. (2025). Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems. npj Quantum Information. https://doi.org/10.1038/s41534-025-01082-1
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.