Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

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 access
Montañez-Barrera, J. A., Michielsen, Kristel · 2025 · npj Quantum Information

Abstract

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

Crossref · 10.1038/s41534-025-01082-1

Cites

49 of 50 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

10 Valid · 6 Not valid · 3 Not checked · 66 Own results and interpretations

34 more claims

Create a free account to see all 85 claims and every source verdict.

See all claims — free account
  • It may state two separate claims as one. 27
  • Probably not a substantial claim. 22
  • The quote only partly states this claim. 1

Create a free account to see these claims.

Citations

Cites

Show all 47 references

Research works printed but not linked: 1

  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

See all 34

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
Licence
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.