The DOI matches its Crossref record; 53 of the 55 references it cites were found in a registry or an index; 49 of the 81 sources its claims cite were checked for support.
Quantum annealing for combinatorial optimization: a benchmarking study
Open accessAbstract
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.
Overview
CoChat Summary
## TL;DR
This paper benchmarks quantum annealing (QA), hybrid QA (HQA), and several classical solvers on large, dense QUBO optimization problems meant to reflect real-world materials design tasks. The authors report that HQA was the best overall method, with about 0.013% higher accuracy and about 6561× faster solving time than the best classical solver on 10,000-variable problems.
## Key findings
- Across large and dense QUBO problems, HQA achieved the highest accuracy, reported as about 0.013% improvement over the best classical solver.
- For 10,000-dimensional QUBO problems, HQA was about 6561× faster than the best classical solver.
- Classical solvers (IP, SA, SD, TS, PT-ICM) generally became less accurate and slower as problem size increased; the paper notes that SA and PT-ICM struggled beyond 3000 variables.
- For one case at n = 7000, the IP solver still had an optimality gap of about 17.73% after 2 hours.
- Example solving times at n = 5000 were 0.0854 s for HQA, 74.59 s for QA-QBSolv, 167.4 s for SA-QBSolv, and 195.1 s for PT-ICM-QBSolv; at n = 10,000, times were 0.0855 s for HQA, 101 s for QA-QBSolv, and 561 s for SA-QBSolv.
## Methods
- Benchmarking study comparing seven solvers: QA, HQA, IP, SA, SD, TS, and PT-ICM, with decomposition variants using QBSolv where applicable.
- Two problem settings were used: real-world-inspired materials optimization QUBOs and systematically generated dense random QUBOs with sizes from 120 to 10,000 variables and four coefficient distributions (standard deviations 0.001, 0.01, 0.1, 1).
- Main analysis compared relative accuracy and computational time; QA was run on D-Wave Advantage 4.1 with 1000 reads and 20 μs annealing time, while classical solvers used specified default or fixed hyperparameters.
## Limitations
- The paper states that pure QA and QA with QUBO decomposition still have limitations for large problems because of current hardware limits, especially qubit count and qubit connectivity.
- The paper notes that the detailed algorithm of HQA is not publicly released.
- Evident from the text: the benchmarking is limited to QUBO formulations and the specific solver settings/software/hardware described, so the results may not generalize to other optimization formulations or implementations.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Figures




Verification
Claims the paper makes
24 Valid · 5 Not valid · 8 Not checked · 54 Own results and interpretations
Some cited sources support this claim and some don’t — read each source’s verdict below.
In the paper
“The adiabatic theorem of quantum mechanics ensures that QA identi fi es the optimal solution regardless of the size and landscape of the combinatorial parametric space, highlighting QA as a powerful and practical solver 11 -14 .”
What the sources say
- Partly supportedcites [11] Santoro, G. E., Martonák, R., Tosatti, E. & Car, R. Theory of quantum annealing of an Ising spin glass. Science 295, 2427–2430 (2002). sourceExperimental — accuracy not yet measured
The Fig. 3 caption (p. 6) says the system follows the ground state adiabatically at a crossing only if the field is reduced sufficiently slowly. The Landau–Zener discussion (p. 3) describes failures to follow the ground state and resulting residual energy; the conclusion (p. 4) predicts logarithmically slow convergence for the Ising spin glass. These passages support conditional ground-state tracking, not a guarantee of a practical optimal solution regardless of problem size or landscape. (LLM, conf=0.88)
- Partly supportedcites [12] Hen, I. & Spedalieri, F. M. Quantum annealing for constrained optimization. Phys. Rev. Appl. 5, 034007 (2016). sourceExperimental — accuracy not yet measured
The Introduction (p. 1) says the adiabatic theorem keeps the system close to the ground state if evolution is slow enough, yielding the solution with high probability. It does not guarantee success regardless of problem size or landscape: the required running time depends on the minimum energy gap, and Graph Partitioning (p. 3) explicitly examines how that gap scales with problem size. (LLM, conf=0.90)
- Disputedcites [13] Kadowaki, T. & Nishimori, H. Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355–5363 (1998). sourceExperimental — accuracy not yet measured
The discussion of the annealing model says the system should approach the ground state when the transverse field is reduced sufficiently slowly, not that QA is guaranteed to find it. The Summary and Discussions reports that the ground state was not reached perfectly under the schedules studied and identifies unresolved difficulties for larger systems and other optimization problems. These findings contradict the claimed unconditional guarantee regardless of size or landscape. (LLM, conf=0.88)
Checked by a reasoning model — may be wrong.
- Not checked yetcites [14] Morita, S. & Nishimori, H. Mathematical foundation of quantum annealing. J. Math. Phys. 49, 125210 (2008). source
Checked before — its earlier verdict is held back until a new check runs.
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: unclear — It is unclear why the paper says it holds.
- Partly supported
Every source the paper cites for this claim was checked and supports it.
In the paper
“For example, O ' Malley et al. 17 compared the performance of QA with classical methods (mathematical programming), but they limited the number of binary variables to 35 due to the QA hardware limitation.”
What the sources say
- Supportedcites [17] O’Malley, D., Vesselinov, V. V., Alexandrov, B. S. & Alexandrov, L. B. Nonnegative/Binary matrix factorization with a D-Wave quantum annealer. PLoS ONE 13, e0206653 (2018). source
The Methods section (“Programming the D-Wave”) explicitly says the study was limited to 35 binary variables because of D-Wave 2X embedding constraints and poor performance when more physical qubits represent each variable. The Results compare D-Wave annealing time with Gurobi, a classical optimization tool. (LLM, conf=0.94)
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.
- Supported
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“During this process, entangled qubits naturally evolve into the ground state of a given Hamiltonian to fi nd the optimal vector of binary decisions for the corresponding quadratic unconstrained binary optimization (QUBO) problem 8 -10 .”
What the sources say
- Partly supportedcites [8] Santoro, G. E. & Tosatti, E. Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A Math. Gen. 39, R393–R431 (2006). sourceExperimental — accuracy not yet measured
Section 1.1 explains that annealing aims to reach the ground state of a Hamiltonian encoding an optimization problem, and §1.3 says the system follows that ground state if the annealing is sufficiently slow. The paper does not specifically describe a QUBO problem or an optimal vector of binary decisions. It also describes the initial spin state as a product state, not as entangled qubits that naturally reach the optimum without an adiabaticity condition. Page numbers are unavailable in our copy. (LLM, conf=0.86)
- Partly supportedcites [9] Mandra, S., Zhu, Z. & Katzgraber, H. G. Exponentially biased ground-state sampling of quantum annealing machines with transverse-field driving hamiltonians. Phys. Rev. Lett. 118, 070502 (2017). sourceExperimental — accuracy not yet measured
The paper reports that the D-Wave 2X quantum annealer can find the ground-state energy of its spin-glass benchmark problems (p. 1) and describes a Hamiltonian built from binary Ising variables (p. 2). It does not describe entangled qubits naturally evolving to a ground state or identify the problems as QUBO problems; its account of reaching an optimum is more qualified than the citing sentence. (LLM, conf=0.84)
- Partly supportedcites [10] Kitai, K. et al. Designing metamaterials with quantum annealing and factorization machines. Phys. Rev. Res. 2, 013319 (2020). sourceExperimental — accuracy not yet measured
In “C. Learning by FM” (page not specified), the paper says a quantum annealer searches lower-energy states of a QUBO over binary bits. In “D. Selection by the D-Wave quantum annealer” (page not specified), it calls the outputs ground-state candidates and selects the lowest-energy one. Our copy does not say that entangled qubits evolve adiabatically into the ground state or that this process necessarily finds the optimal binary vector. (LLM, conf=0.86)
plainstates a cause- 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.
- Partly supported
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“Consequently, these benchmarking studies show that QA methods and their classical counterparts can exhibit similar solution quality and time complexity.”
What the sources say
- Partly supportedcites [17] O’Malley, D., Vesselinov, V. V., Alexandrov, B. S. & Alexandrov, L. B. Nonnegative/Binary matrix factorization with a D-Wave quantum annealer. PLoS ONE 13, e0206653 (2018). sourceExperimental — accuracy not yet measured
The Methods section defines a benchmark in which classical solvers seek solutions at least as good as the D-Wave’s, and the Results report mixed relative running times. But the paper does not show that the quantum annealer and classical solvers have similar time complexity; its complexity analysis concerns the components of its own factorization algorithm, not a comparison of their complexity. (LLM, conf=0.84)
- Supportedcites [18] Tasseff, B. et al. On the emerging potential of quantum annealing hardware for combinatorial optimization. J. Heuristics. 30, 325–358 (2024). source
The Introduction (page unavailable) says that previous benchmarking studies found established algorithms outperformed or were competitive with QA hardware in both solution quality and computation time. This supports the claim about comparable benchmark performance; the paper describes measured computation time rather than formal asymptotic time complexity. (LLM, conf=0.90)
- Partly supportedcites [19] Haba, R., Ohzeki, M. & Tanaka, K. Travel time optimization on multi-AGV routing by reverse annealing. Sci. Rep. 12, 17753 (2022). sourceExperimental — accuracy not yet measured
The Results (page unavailable) report that reverse annealing achieved almost the same task scores as Gurobi, supporting similar solution quality in the tested multi-AGV setting. They compare time-to-solution, not time complexity: reverse annealing was faster for small problems, while Gurobi was faster as problem size increased. The paper therefore does not establish similar time complexity. (LLM, conf=0.85)
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.
- Partly supported
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“However,duetothelimitednumberofqubitsandtheirconnectivity, the QAhardwaredidnot show such an advantage over classical methods in past benchmarking studies.”
- Also stated in: § Introduction · plain
“Whilepreviousbenchmarkingstudiesshowedsomeadvantages of QA, most used low-dimensional or the sparse con fi gurations of QUBO matrices due to the lack of available qubits in the QA hardware and poor topology to connect qubits 17 -19 .”
What the sources say
- Partly supportedcites [17] O’Malley, D., Vesselinov, V. V., Alexandrov, B. S. & Alexandrov, L. B. Nonnegative/Binary matrix factorization with a D-Wave quantum annealer. PLoS ONE 13, e0206653 (2018). sourceExperimental — accuracy not yet measured
The Introduction (page unavailable) reports that a recent benchmark found D-Wave did not outperform the best classical heuristics. But it does not attribute that result to limited qubit numbers or connectivity. The Discussion and Methods describe hardware constraints, while the paper’s own benchmark found a short-time regime in which D-Wave outperformed two classical approaches. (LLM, conf=0.85)
- Partly supportedcites [18] Tasseff, B. et al. On the emerging potential of quantum annealing hardware for combinatorial optimization. J. Heuristics. 30, 325–358 (2024). sourceExperimental — accuracy not yet measured
The Introduction (page not available) says earlier benchmarks found established classical algorithms outperformed or matched available QA hardware. The paper also describes limits on qubit count and connectivity and, in §4 (page not available), expects improvements in both to increase future performance. It does not establish that those limits caused the lack of advantage in past benchmarks. (LLM, conf=0.86)
- Partly supportedcites [19] Haba, R., Ohzeki, M. & Tanaka, K. Travel time optimization on multi-AGV routing by reverse annealing. Sci. Rep. 12, 17753 (2022). sourceExperimental — accuracy not yet measured
The Results (page unavailable) report that Gurobi outperformed reverse annealing as problem size increased, but that reverse annealing was faster for small problems. The Introduction attributes imperfect annealer performance to hardware and environmental effects; it does not identify limited qubit count or connectivity as the cause, or establish that past benchmarking studies generally found no advantage over classical methods. (LLM, conf=0.84)
plainstates a cause- 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.
- Also stated in: § Introduction · plain
30 more claims · 3 with their cited sources checked
Create a free account to see all 91 claims and to verify the 1 reference still open.
- Probably not a substantial claim. 32
- It may state two separate claims as one. 33
Citations
Cites
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 · cited 1×
“Quantum computers mark a paradigm shift to tackle challenging tasks that classical computers cannot solve in a practical timescale 1,2 .”
Future paths for integer programming and links to artificial intelligence
Glover, F. (1986) · Computers & Operations Research · doi:10.1016/0305-0548(86)90048-1 · Cited by 4,181
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891 · cited 2×
“The quantum annealer is a special quantum computer designed to solve combinatorial optimization problems with problem-size-independent time complexity 3 – 5 .”
Pyomo — Optimization Modeling in Python
Bynum, M. L., Hackebeil, G. A., Hart, W. E., Laird, C. D., Nicholson, B. L., Siirola, J. D., Watson, J.-P., & Woodruff, D. L. (2021) · Springer Optimization and Its Applications · doi:10.1007/978-3-030-68928-5 · Cited by 806
Theory of Quantum Annealing of an Ising Spin Glass
Santoro, G. E., Martoňák, R., Tosatti, E., & Car, R. (2002) · Science · doi:10.1126/science.1068774 · Cited by 734 · cited 1×
“The adiabatic theorem of quantum mechanics ensures that QA identi fi es the optimal solution regardless of the size and landscape of the combinatorial parametric space, highlighting QA as a powerful and practical solver 11 – 14 .”
Practical quantum advantage in quantum simulation
Daley, A. J., Bloch, I., Kokail, C., Flannigan, S., Pearson, N., Troyer, M., & Zoller, P. (2022) · Nature · doi:10.1038/s41586-022-04940-6 · Cited by 669
Perspectives of quantum annealing: methods and implementations
Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H., & Oliver, W. D. (2020) · Reports on Progress in Physics · doi:10.1088/1361-6633/ab85b8 · Cited by 507 · cited 1×
“Suf fi cientlyslowevolutionfrom H 0 to H p enablesthe quantumsystemtostayatthegroundstate,whichleadstotheidenti fi cation of the optimal solution of a given combinatorial optimization problem 3,40 .”
Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., & Katzgraber, H. G. (2019) · Frontiers in Physics · doi:10.3389/fphy.2019.00048 · Cited by 442 · cited 4×
“While it can work well for sparse problems, its effectiveness decreases for denser problems 28 .”
InfluentialMathematical foundation of quantum annealing
Morita, S., & Nishimori, H. (2008) · Journal of Mathematical Physics · doi:10.1063/1.2995837 · Cited by 381 · cited 1×
“The adiabatic theorem of quantum mechanics ensures that QA identi fi es the optimal solution regardless of the size and landscape of the combinatorial parametric space, highlighting QA as a powerful and practical solver 11 – 14 .”
Research works printed but not linked: 3
- Tao, M. et al. Towards Stability in the Chapel Language. In Proc. IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) 557–566 (IEEE, 2020).
- Hansen, P. B. Simulated annealing. Electrical Eng. Comput. Sci. Tech. Rep. 170, 1–12 (1992).
- Dupin, N., Nielsen, F. & Talbi, E. Dynamic Programming heuristic for k-means Clustering among a 2-dimensional Pareto Frontier. In Proc. 7th International Conference on Metaheuristics and Nature Inspired Computing, Springer (2018).
Cited by
Harnessing Quantum Computing for Energy Materials: Opportunities and Challenges
Kim, S., Suh, I., Humble, T. S., Beck, T. L., lee, E., & Luo, T. (2026) · ACS Energy Letters · doi:10.1021/acsenergylett.5c04009 · Cited by 6
“24,41 Although quantum annealing cannot address all scientific problems since only QUBO-type formulations can be directly solved, it represent a practical QC approach for large-scale and practical optimization tasks relevant to energy applications.”
InfluentialSelf-citationKansara, R., Kyriakidis, L., & Serrano, M. I. R. (2025) · Energies · doi:10.3390/en18164258 · Cited by 2
Quantum annealing for remote sensing data processing: A review of optimization based applications
Misra, I., Moorthi, S. M., & Dhar, D. (2026) · Remote Sensing Applications Society and Environment · doi:10.1016/j.rsase.2026.101936 · Cited by 3
Rotman Lens Design Using Factorization Machine and Simulated Annealing
Son, Y., Park, J., Lee, S., Lee, E., & Kim, S. (2025) · IEEE Antennas and Wireless Propagation Letters · doi:10.1109/lawp.2025.3596227 · Cited by 1
Self-citationPandya, K., & Maiti, A. (2025) · Information Sciences · doi:10.1016/j.ins.2025.122584 · Cited by 1
Metadata
- Authors
- Kim, S., Ahn, S.-W., Suh, I.-S., Dowling, A. W., Lee, E., & Luo, T.
- Affiliations
- University of Notre Dame (US)
- Kyung Hee University (KR)
- Oak Ridge National Laboratory (US)
- Corresponding author
- Dowling, Alexander W.
- Lee, Eungkyu
- Luo, Tengfei
- Venue
- npj Quantum Information
- Published
- 2025-05-16
- Volume
- 11
- Issue
- 1
- ISSN
- 2056-6387 (ISSN-L)
- OpenAlex
- W4410453046
- Cited by
- 46
- References
- 55
- Citations by year
- 2026: 35 · 2025: 11
- FWCI
- 18.31
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- cc-by-nc-nd
- creativecommons.org/licenses/by-nc-nd/4.0 (tdm)
- creativecommons.org/licenses/by-nc-nd/4.0 (vor)
- Locations
- npj Quantum Information (publishedVersion, cc-by-nc-nd)
- arXiv (Cornell University) (submittedVersion, cc-by-nc-nd)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Department of Energy (DE-AC05-00OR22725)
- National Research Foundation of Korea (RS-2023-00255442)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- quantum annealing, combinatorial optimization, benchmarking, quantum advantage, hybrid quantum-classical solvers, qubit connectivity, solution accuracy, problem-solving time, large-scale optimization problems
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-30, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-09-30 (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: Quantum annealing for combinatorial optimization: a benchmarking study. https://app.cochat.ai/papers/10.1038/s41534-025-01020-1
- The paper
- Kim, S., Ahn, S.-W., Suh, I.-S., Dowling, A. W., Lee, E., & Luo, T. (2025). Quantum annealing for combinatorial optimization: a benchmarking study. npj Quantum Information. https://doi.org/10.1038/s41534-025-01020-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.