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

The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index; none of the 26 sources its claims cite is checked for support yet.

Assessing quantum and classical approaches to combinatorial optimization: Testing quadratic speed-ups for heuristic algorithms

Open access

Abstract

Many recent investigations have concluded, based on asymptotic complexity analyses, that quantum computers could accelerate combinatorial optimization (CO) tasks relative to a purely classical computer. However, asymptotic analysis alone cannot support a credible claim of quantum advantage. Here, we highlight the challenges involved in benchmarking quantum and classical heuristics for CO, with a focus on the Sherrington-Kirkpatrick problem. Whereas hope remains that a quadratic quantum advantage is possible, our numerical analysis casts doubt on the idea that current methods exhibit any quantum advantage at all. This doubt arises because even a simple classical approach can match with quantum methods we investigated. We conclude that more careful numerical investigations are needed to evaluate the potential for quantum advantage in CO, and we give some possible future directions for such investigations.

Overview

CoChat Summary

TL;DR

This paper benchmarks classical and quantum heuristics on Sherrington-Kirkpatrick optimization instances and finds no clear numerical evidence of quantum advantage for the structured methods studied. Although unstructured Grover Adaptive Search shows the expected quadratic scaling over brute force, a simple classical Metropolis-Hastings approach matches or slightly outperforms its quantum analog in the tested setting.

Key findings

  • For unstructured methods, fitted scaling was roughly \(2^n\) for brute force (\(c \approx 1\)), \(2^{n/\sqrt{2}}\) for random sampling (\(c \approx 1/\sqrt{2}\)), and \(2^{n/2}\) for Grover Adaptive Search (\(c \approx 0.5\)).
  • For structured methods, the fitted \(c\) values for classical Metropolis-Hastings and quantum LHPST were “quite similar,” with a small advantage given to the classical version; the authors state their analysis does not show clear evidence either way.
  • Estimated times for \(n=128\) spins were \(1.70\times10^{-3}\) days for classical Metropolis-Hastings, \(4.88\times10^5\) days for LHPST, and \(1.42\times10^{20}\) days for GAS, under the paper’s hardware assumptions.
  • The paper reports that GAS’s quadratic speedup over brute force is consistent with Grover’s algorithm but is less predictable when the number of solutions is unknown.

Methods

  • The authors numerically benchmarked classical brute force, random sampling, and Metropolis-Hastings against quantum Grover Adaptive Search and LHPST on random Sherrington-Kirkpatrick instances, using 100 randomly chosen problem instances and spin sizes discussed in the appendices.
  • They fixed solution quality using a \(0.9\)-average energy approximation ratio (\(\alpha\)-AEAR) for approximate methods, or optimal-solution success for GAS with success probability \(1-\varepsilon\), \(\varepsilon=0.016\), and counted main subroutine steps until that quality was reached.
  • They fitted exponential scaling \(b \times N^c\) with \(N=2^n\), then estimated clock times using Toffoli counts for quantum methods and floating-point operations for classical methods, assuming an iPhone 12 at 11 TFLOPS for classical hardware.

Limitations

  • Stated: the numerical analysis cannot determine that classical is actually better than quantum, only that it does not provide clear evidence one way or another.
  • Stated: the \(\alpha=0.9\) approximation corresponds to solutions between the ground and first excited state for the considered SK instances; larger system sizes would require a higher \(\alpha\).
  • Stated: GAS results are optimistic because the implementation first found each instance’s solution and then used standard Grover; QAOA and quantum simulated annealing were excluded for stated practical reasons, and the authors did not analyze spectral gaps or guarantee convergence to the final Gibbs distribution.
  • Evident from the text: large-system conclusions rely on extrapolating fits from small-system numerical data, and the classical time estimates assume smartphone-level rather than supercomputer hardware.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1103/hm1z-z9p2

Cites

30 of 30 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 4 Not valid · 21 Not checked · 55 Own results and interpretations

23 more claims

Create a free account to see all 80 claims and to verify the 2 references still open.

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

Create a free account to see these claims.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

3 of 3

Citations

Cites

Show all 26 references

Research works printed but not linked: 4

  1. W. G. Macready, 2006, Complex Syst., 15, 117
  2. 10.1002/(SICI)1521-3978(199806)46:4/5%3C493::AID-PROP493%3E3.0.CO;2-P · doi:10.1002/(sici)1521-3978(199806)46:4/5<493::aid-prop493>3.0.co;2-p
  3. A. Bärtschi, 2020, Proceedings of the 2020 IEEE International Conference on Quantum Computing and Engineering (QCE)
  4. P. R. Bevington, 2003, Data Reduction and Error Analysis for the Physical Sciences (3rd ed.)

Metadata

Authors
Costa, P. C. S., Morales, M. E. S., An, D., & Sanders, Y. R.
Affiliations
  • University of Technology Sydney (AU)
  • University of Maryland, College Park (US)
  • Peking University (CN)
Corresponding author
Costa, Pedro C. S.
Venue
Physical Review A
Published
2025-08-25
Volume
112
Issue
2
ISSN
  • 0556-2791 (ISSN-L)
  • 2469-9926
  • 2469-9934
OpenAlex
W4413503464
Cited by
0
References
26
FWCI
0.00
Type
journal article
Language
en
Open access
Locations
  • Physical Review A (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • OPUS - Open Publications of UTS Scholars (University of Technology Sydney) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • U.S. Department of Defense
  • NSW Defence Innovation Network
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 advantage, combinatorial optimization, heuristic algorithms, spin glass

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.

A language model drew the claims from the paper on 2026-10-29, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-29 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

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: Assessing quantum and classical approaches to combinatorial optimization: Testing quadratic speed-ups for heuristic algorithms. https://app.cochat.ai/papers/10.1103/hm1z-z9p2
The paper
Costa, P. C. S., Morales, M. E. S., An, D., & Sanders, Y. R. (2025). Assessing quantum and classical approaches to combinatorial optimization: Testing quadratic speed-ups for heuristic algorithms. Physical Review A. https://doi.org/10.1103/hm1z-z9p2

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.