REVIEW 16 cited by
Quantum Optimization Benchmarking Library - The Intractable Decathlon
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Quantum Optimization Benchmarking Library - The Intractable Decathlon
read the original abstract
Through recent progress in hardware development, quantum computers have advanced to the point where benchmarking of (heuristic) quantum algorithms at scale is within reach. Particularly in combinatorial optimization - where most algorithms are heuristics - it is key to empirically analyze their performance on hardware and track progress towards quantum advantage. To this extent, we present ten optimization problem classes that are difficult for existing classical algorithms and can (mostly) be linked to practically relevant applications, with the goal to enable systematic, fair, and comparable benchmarks for quantum optimization methods. Further, we introduce the Quantum Optimization Benchmarking Library (QOBLIB) where the problem instances and solution track records can be found. The individual properties of the problem classes vary in terms of objective and variable type, coefficient ranges, and density. Crucially, they all become challenging for established classical methods already at system sizes ranging from less than 100 to, at most, an order of 100,000 decision variables, allowing to approach them with today's quantum computers. We reference the results from state-of-the-art solvers for instances from all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems. The baseline results illustrate a standardized form to present benchmarking solutions, which has been designed to ensure comparability of the used methods, reproducibility of the respective results, and trackability of algorithmic and hardware improvements over time. We encourage the optimization community to explore the performance of available classical or quantum algorithms and hardware platforms with the benchmarking problem instances presented in this work toward demonstrating quantum advantage in optimization.
Forward citations
Cited by 16 Pith papers
-
Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods
Block-Gibbs MCMC matches DQI approximation ratios on max-XORSAT and OPI, with OPI runtime empirically ~1.1^n, without refuting asymptotic quantum-advantage claims.
-
Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Variational quantum methods with spectral preprocessing, CVaR optimization, and ancilla-assisted superposition solve maximum independent set to optimality on graphs up to 180 vertices, claimed as the largest such gate...
-
Spectral Gap Informed Ramp QAOA
SGIR-QAOA uses spectral gap information to create non-linear parameter schedules that outperform linear ramps on Grover's problem and MIS, achieving target probabilities at lower depths even under mild noise.
-
Efficient Classical Simulation of Heuristic Peaked Quantum Circuits
Peaked quantum circuits claimed to show quantum advantage can be classically simulated in one hour on a GPU via mirrored MPO contraction and unswapping.
-
Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting
Bitflip-gauge warm-start QAOA that aligns the ansatz with amplitude-damping noise improves 100-qubit Ising approximation ratios over non-gauge iterative warm-start at no extra circuit cost.
-
Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Ancilla-assisted multi-seed superposition plus excitation-preserving VQE and classical post-processing recovers exact MIS on 64-, 99-, and 180-node graphs, with partial hardware transfer.
-
Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Variational quantum methods with spectral reordering, sparsification, CVaR optimization, and ancilla-assisted superposition solve MIS to optimality on 64-, 99-, and 180-vertex graphs, the largest such gate-based demon...
-
Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization
Fourier-based LCU decomposes diagonal and non-diagonal unitaries into hardware-friendly forms for QAOA-style optimization, trading circuit depth for sampling overhead with performance guarantees.
-
Spectral Gap Informed Ramp QAOA
SGIR-QAOA uses spectral gap information to construct QAOA parameter schedules, showing better performance than linear-ramp QAOA on Grover's problem at fixed depth, shorter depths for equivalent success probability, ex...
-
A quantum wire approach to weighted combinatorial graph optimisation problems
Demonstrates a quantum wire encoding using Rydberg atom chains to solve MWIS and QUBO problems on neutral atom arrays with reduced ancilla overhead and experimental validation.
-
Efficient Circuit Transpilation of Commuting Gates on 2D Grids
Greedy, problem-dependent SWAP-layer sequences on 2D grids roughly halve QAOA circuit depth and CZ count for sparse MaxCut and MIS graphs, improving hardware approximation ratios by up to ~6–9%.
-
Recent quantum runtime (dis)advantages
End-to-end runtime definitions and strong classical baselines show that three recent quantum advantage claims in annealing, Simon's problem, and hybrid algorithms do not hold on NISQ hardware.
-
Quantum optimization beyond QUBO for industrial logistics and scheduling
HUBO formulations for logistics problems offer qubit savings over QUBO at the expense of higher circuit depth, validated classically and simulated quantumly for small cases.
-
Experimental Workflows for Combinatorial Optimization: Towards Quantum Advantage
A sandbox platform enables end-to-end hybrid workflows that reduce graph problems, run QAOA on IBM hardware up to 128 qubits, and refine outputs classically for problems including vertex cover and clique.
-
GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem
A hybrid CPU-GPU algorithm derived from Schroeppel-Shamir's subset sum method solves market split feasibility instances with up to 10 constraints and 90 variables, with reported runtimes under 15 minutes for (9,80) an...
-
Setting angles in quantum approximate optimization at utility-scale
The paper benchmarks approximation techniques and transfer learning for setting QAOA angles at utility scale and extracts operational guidance from hardware-validated results.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.