The Quantum Optimization Benchmarking Library
Top Cited Papers
Open Access
- 23 June 2026
- journal article
- Published by Springer Nature in Nature Computational Science
- Vol. 6 (6) , 653-671
Abstract
Recent progress has brought benchmarking of (heuristic) quantum algorithms at scale within reach. Particularly in combinatorial optimization, it is key to empirically analyze and track progress towards quantum advantage. This work introduces a systematic, fair and comparable benchmarking framework for quantum optimization methods by presenting ten model-independent problem classes that are challenging for classical methods. Track records of specific instances and solutions are given in an accompanying open-source repository. While the individual properties of the problem classes vary, they all become challenging from less than 100 to, at most, an order of 100,000 decision variables. We reference results from state-of-the-art solvers for instances across all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems, which illustrate standardized benchmark reporting. The presented problem instances may be approached with classical or quantum algorithms executed on varying hardware platforms to drive the field towards quantum advantage.Keywords
Funding Information
- Bundesministerium für Forschung, Technologie und Raumfahrt (05M20ZBM)
- Bundesministerium für Forschung, Technologie und Raumfahrt (05M2025)
- Bundesministerium für Forschung, Technologie und Raumfahrt (05M14ZAM)
- Bundesministerium für Forschung, Technologie und Raumfahrt (05M20ZBM)
- Bundesministerium für Forschung, Technologie und Raumfahrt (05M2025)
- Ministry of Education - Singapore (A-8000339-01-00)
- National Research Foundation Singapore (A-8000014-00-00)
- Office of Naval Research (N000142312585)
- Fonds Wetenschappelijk Onderzoek (23AXE35N)
This publication has 124 references indexed in Scilit:
- Exploring the Capacitated Vehicle Routing Problem Using the Power of Machine Learning: A Literature Review2024
- Qubit Efficient Quantum Algorithms for the Vehicle Routing Problem on Noisy Intermediate‐Scale Quantum ProcessorsAdvanced Quantum Technologies, 2024
- SPEC Benchmarks2011
- There are 1,132,835,421,602,062,347 nonisomorphic one‐factorizations of K14Journal of Combinatorial Designs, 2008
- SteinLib: An Updated Library on Steiner Tree Problems in Graphs2001
- Simple heuristics for unit disk graphsNetworks, 1995
- Complexity of vehicle routing and scheduling problemsNetworks, 1981
- A lower bound on the average shortest path length in regular graphsNetworks, 1974
- Reducibility among Combinatorial Problems1972
- Steiner's problem in graphs and its implicationsNetworks, 1971