REVIEW 9 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
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 9 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 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...
-
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.
-
Resource-efficient variational quantum solver for the travelling salesman problem and its silicon photonics implementation
A variational quantum solver encodes TSP routes in the correlation matrix of two entangled registers, using O(log N) qubits, and is demonstrated for four cities on a silicon photonic chip.
-
Quantum Portfolio Optimization: An Extensive Benchmark
On a new 260-instance real-world benchmark, classical MIP and heuristics clearly outperform quantum annealing and QAOA for a volatility-minimizing portfolio optimization variant.
-
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%.
-
Enhanced Prediction of CAR T-Cell Cytotoxicity with Quantum-Kernel Methods
A 61-qubit projected quantum kernel classifier modestly outperforms a classical SVM at predicting high versus low CAR T-cell cytotoxicity, with the largest per-motif gains in data-poor positions.
-
Protein folding with an all-to-all trapped-ion quantum computer
BF-DCQO on IonQ's trapped-ion processors solves dense HUBO instances (protein folding up to 33 qubits, MAX 4-SAT and spin-glasses at 36 qubits) when followed by classical post-processing.
-
A Framework for Quantum Advantage
A framework defining quantum advantage as verifiable plus classically superior, with a conclusion that random circuit sampling is not yet a satisfactory path.
Discussion (0). Continue with ORCID to comment.