⚛️ quantum physics

Quantum Optimization Benchmarking Library - The Intractable Decathlon

This paper introduces the Quantum Optimization Benchmarking Library (QOBLIB), a collection of ten challenging optimization problem classes designed to enable systematic, fair, and reproducible benchmarking of quantum algorithms against classical solvers to track progress toward quantum advantage.

Original authors: Thorsten Koch, David E. Bernal Neira, Ying Chen, Giorgio Cortiana, Daniel J. Egger, Raoul Heese, Narendra N. Hegade, Alejandro Gomez Cadavid, Rhea Huang, Toshinari Itoko, Thomas Kleinert, Pedro Maciel

Published 2026-07-21

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Thorsten Koch, David E. Bernal Neira, Ying Chen, Giorgio Cortiana, Daniel J. Egger, Raoul Heese, Narendra N. Hegade, Alejandro Gomez Cadavid, Rhea Huang, Toshinari Itoko, Thomas Kleinert, Pedro Maciel Xavier, Naeimeh Mohseni, Jhon A. Montanez-Barrera, Koji Nakano, Giacomo Nannicini, Corey O'Meara, Justin Pauckert, Manuel Proissl, Anurag Ramesh, Maximilian Schicker, Noriaki Shimada, Mitsuharu Takeori, Victor Valls, David Van Bulck, Stefan Woerner, Christa Zoufal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve the world's most complex puzzle. You have a box of pieces that represent a real-world problem, like planning a sports tournament, managing a stock portfolio, or routing delivery trucks. For decades, we've relied on super-fast classical computers to sort through these pieces. While these supercomputers are incredibly good at finding good solutions quickly for many scenarios, some puzzles are so tangled that finding the perfect answer or proving a solution is the absolute best takes an enormous amount of time, even for the most powerful machines. Enter the quantum computer. Think of it not as a faster calculator, but as a magical explorer that can look at the entire puzzle landscape at once, hopping between possibilities in a way that classical machines simply cannot. The big question scientists are asking right now is: Can these new quantum explorers actually beat the old supercomputers at these tough puzzles? This isn't just about winning a race; it's about finding a new way to solve problems that are currently "intractable" in the sense that proving optimality or finding the absolute best solution is too hard for our current technology to do efficiently.

This paper, titled "The Intractable Decathlon," is essentially a massive, organized playground designed to test exactly that. The authors, a huge team of researchers from universities and tech giants like IBM, have built a library called QOBLIB (Quantum Optimization Benchmarking Library). Inside this library, they've placed ten different types of "puzzles" (optimization problems) that are notoriously difficult for classical computers to solve perfectly or prove optimal, even when the puzzles are relatively small, often ranging from less than 100 to around 100,000 decision variables. They call this collection the "Intractable Decathlon" because, just like an athletic decathlon tests a runner's ability in ten different events, this collection tests quantum algorithms across ten different types of challenges.

The team didn't just throw random problems at the wall; they carefully selected ten specific categories, ranging from Market Split (dividing a group of items into two equal piles) to Sports Tournament Scheduling (figuring out who plays whom and when without conflicts). They created specific versions of these puzzles that are hard enough to stump today's best classical solvers when it comes to finding the proven optimal solution, but small enough that current quantum computers can actually try to tackle them. The paper provides a "rulebook" for how to measure who wins, ensuring that if a quantum computer solves a puzzle, we know exactly how long it took and how good the answer was, so we can compare it fairly against classical methods later.

The authors also ran some initial tests to set a "baseline," showing what happens when they try to solve a few of these puzzles with current quantum tools. For example, they tested a method called BF-DCQO on a "Low Autocorrelation Binary Sequence" puzzle (a problem about arranging a sequence of numbers to minimize interference). In these classically simulated results, which included idealized runtime estimates for quantum hardware, they found that their quantum approach could find the best solution in a reasonable amount of time, scaling better than some older classical methods for certain sizes. However, they are very careful to note that this isn't a total victory yet. They explicitly state that for many of these problems, classical computers are still incredibly fast and accurate at finding good solutions, even if proving they are the best takes too long. The paper doesn't claim that quantum computers have "won" or solved these problems for good; instead, it suggests that for specific types of hard puzzles, quantum methods are starting to show promise and are worth watching closely.

The paper also rules out the idea that we can just take any problem and slap a quantum algorithm on it to get a magic result. They explain that turning a real-world problem into a format a quantum computer understands (like a QUBO) can sometimes make the problem much bigger and harder to handle, adding a layer of complexity that might cancel out any speed gains. They emphasize that we need to be smart about how we translate these problems.

Ultimately, this paper is a call to action and a toolkit for the scientific community. It says, "Here are ten tough puzzles, here is how we measure success, and here is our first attempt at solving them with quantum tools." It doesn't promise that quantum computers will replace classical ones tomorrow, but it provides the first solid, fair ground to track progress. By giving everyone the same set of difficult problems and the same rules for measuring results, the authors hope to track the slow, steady climb toward a future where quantum computers can genuinely outperform classical ones in solving the world's most stubborn optimization headaches.

Technical Summary: The Intractable Decathlon – A Quantum Optimization Benchmarking Library

Problem Definition

The paper addresses the critical need for systematic, fair, and comparable benchmarking of heuristic quantum optimization algorithms against state-of-the-art classical solvers. While quantum hardware has advanced to a point where large-scale benchmarking is feasible, the field lacks a standardized set of problem instances that are simultaneously difficult for classical methods at manageable scales and relevant to practical applications.

The authors introduce the Intractable Decathlon, a collection of ten distinct combinatorial optimization problem classes. These problems are selected because they:

Are difficult for existing classical solvers (often requiring proof of optimality or finding feasible solutions) at system sizes ranging from fewer than 100 to approximately 100,000 decision variables.
Are predominantly "primal difficult," meaning finding a good solution is hard, which aligns with the capabilities of current heuristic quantum algorithms.
Map to practically relevant applications in logistics, finance, network design, and physics.
Can be modeled using integer variables (preferably binary) with integer coefficients, mitigating numerical precision issues common in quantum formulations.

The ten problem classes are:

Market Split: Multi-dimensional subset-sum problems.
Low Autocorrelation Binary Sequences (LABS): Finding binary sequences with minimal autocorrelation.
Minimum Birkhoff Decomposition: Decomposing doubly stochastic matrices into the minimum number of permutation matrices.
Steiner Tree Packing: Packing node-disjoint Steiner trees in a graph.
Sports Tournament Scheduling: Scheduling double round-robin tournaments with complex constraints.
Portfolio Optimization: Multi-period mean-variance optimization with transaction costs.
Maximum Independent Set (MIS): Finding the largest set of non-adjacent vertices in a graph.
Network Design: Constructing directed graphs to minimize maximum edge load.
Vehicle Routing Problem (CVRP): Capacitated vehicle routing with fixed fleet size.
Topology Design: Minimizing network diameter given order and degree constraints (Order Degree Problem).

Methodology

The authors propose a model-independent benchmarking framework to allow maximal flexibility in choosing algorithms, models, and hardware platforms. The methodology includes:

1. Problem Formulation and Modeling

Integer Focus: Problems are defined over integer decision variables $x \in \mathbb{Z}^n$ with linear or quadratic objectives and constraints. Coefficients are rescaled to integers to avoid numerical inaccuracies.
Model Agnosticism: While the library provides standard Mixed Integer Programming (MIP) and Quadratic Unconstrained Binary Optimization (QUBO) formulations, the benchmarking goal is not tied to a specific formulation. This acknowledges that reformulating a problem (e.g., ILP to QUBO) can drastically change problem size and density, potentially introducing new challenges or advantages for specific solvers.
Feasibility vs. Optimization: The framework distinguishes between feasibility problems (finding any valid solution) and optimization problems (finding the best solution). Given that most quantum algorithms are heuristics without optimality guarantees, the benchmark focuses on finding high-quality feasible solutions rather than proving global optimality.

2. Metrics and Reporting

To ensure reproducibility and comparability, the authors define specific metrics:

Solution Quality: Best objective value found across repetitions. For stochastic algorithms, the number of successful runs (finding a solution within a tolerance $\epsilon$ of the best-found solution) is reported.
Computational Resources:
- Total Runtime: Wall-clock time excluding queuing/idling times.
- Hardware Breakdown: Separation of time spent on CPUs, GPUs, Quantum Processing Units (QPUs), and other hardware.
- Quantum Runtime Definition: Specifically defined for the IBM Quantum Platform as the time from payload receipt to sample extraction, including circuit preparation and execution but excluding classical transpilation time (which is attributed to pre-processing).
Submission Guidelines: A standardized template (Table 10) is provided for the Quantum Optimization Benchmarking Library (QOBLIB) to ensure all necessary details (modeling approach, variable counts, coefficient ranges, workflow steps) are captured.

3. Instance Generation

The library contains instances generated to be "primal difficult." For problems where finding a feasible solution is trivial, instances are constructed by reverse-engineering from known solutions to ensure difficulty. The instances vary in density, coefficient ranges, and variable counts to test different algorithmic bottlenecks.

Key Contributions

The QOBLIB Repository: An open-source library containing problem instances, models (MIP/QUBO), solution checkers, and baseline results.
The Intractable Decathlon: A curated set of ten problem classes that bridge the gap between theoretical hardness and practical relevance, specifically selected to be challenging for classical solvers at sizes accessible to near-term quantum hardware.
Standardized Benchmarking Protocol: A rigorous set of definitions for metrics, runtime measurement (especially for quantum hardware), and reporting formats to facilitate fair comparison across different quantum and classical approaches.
Baseline Results: The paper provides extensive classical baseline results using state-of-the-art solvers (e.g., Gurobi, CPLEX, specialized heuristics) to establish performance floors. It also presents illustrative quantum baseline results for three specific problems using different quantum algorithms.

Results and Illustrative Examples

The paper presents classical baselines for all ten problem classes, demonstrating that many instances are currently unsolvable to proven optimality by classical solvers within reasonable timeframes, or require significant computational resources.

Illustrative Quantum Baselines:
The authors provide preliminary results for three problem classes using specific quantum algorithms to demonstrate the submission format and current capabilities:

Low Autocorrelation Binary Sequences (LABS):
- Algorithm: Bias-field Digitized Counter-Diabatic Quantum Optimization (BF-DCQO).
- Result: On a sequence length of $n=20$ (exceeding previous quantum implementations of $n=18$ ), the algorithm found optimal solutions on the ibm marrakesh device. The average runtime was ~61 seconds (including pre/post-processing), with the QPU runtime being ~60.8 seconds.
- Comparison: The scaling of BF-DCQO was comparable to QAOA with $p=12$ layers but required six times fewer entangling gates. It outperformed exact classical solvers (Gurobi, CPLEX) in time-to-solution for the specific instance tested, though the classical solvers eventually found optimal solutions for smaller instances.
Minimum Birkhoff Decomposition:
- Algorithm: Variational Quantum Algorithm (VQA) using a parameterized quantum circuit to sample permutation matrices.
- Result: Tested on $n=4$ and $n=5$ doubly stochastic matrices. For $n=4$ , the algorithm consistently found exact decompositions with 3–4 permutations, matching or exceeding classical approximate solvers (Birkhoff+, Blended FW). For $n=5$ , performance degraded, with only a few instances reaching sparse decompositions, highlighting the current limitations of variational approaches on larger, more complex instances.
Maximum Independent Set (MIS):
- Algorithm: Heuristic solver (ABS2) on GPU hardware.
- Result: Provided baseline performance data for graphs up to 4000 nodes, showing the gap between heuristic solutions and optimal bounds, serving as a target for quantum heuristics.

Significance and Claims

The paper claims that the QOBLIB and the Intractable Decathlon provide the necessary infrastructure to move beyond component-level benchmarking (e.g., gate fidelity) toward application-level benchmarking.

Demonstrating Quantum Advantage: The authors state that only by solving problem instances that are difficult for classical computers (primal difficulty) can a true quantum advantage be demonstrated. The selected instances are designed to be intractable for classical solvers at sizes where near-term quantum devices can operate.
Community Collaboration: The work is framed as a call to action for the optimization community to use these instances to track progress in algorithms, software, and hardware.
Modesty on Current Capabilities: The paper is modest regarding current quantum performance. It acknowledges that while quantum algorithms show promise in scaling and specific instances (like LABS $n=20$ ), they do not yet consistently outperform the best classical heuristics across the board. The primary goal is to establish a standardized form to present benchmarking solutions that ensures comparability, reproducibility, and the ability to track improvements over time.

The authors conclude that this framework is essential for verifying algorithm correctness, identifying bottlenecks, and ultimately determining whether quantum computers can offer a practical advantage in solving real-world combinatorial optimization problems.