Comparing classical and quantum QUBO solvers: optimality, trajectory diagnostics, and limits of solver selection
Abstract
Comparing solvers for quadratic unconstrained binary optimization (QUBO) requires distinguishing solution quality from optimality certification. We compare classical, tensor-network, and fixed-schedule quantum approaches on 180 benchmark instances from ten families with 14-48 variables, supplemented by harder synthetic instances with known optimal solutions, extending to 128 variables. On the main benchmark, a general-purpose branch-and-cut solver matches all reference energies and certifies 176 instances within a 600,s cap. When the known optima are moved to randomly chosen bitstrings, the search comparison changes: at n = 48 the branch-and-cut solver finds only four of ten optima and certifies none, whereas parallel tempering reaches every optimum in every tested run at a 60,s budget. Structural and trajectory diagnostics explain aspects of tensor-network performance. A treewidth bound ranks trajectory bond-dimension demand at Spearman ρ= 0.78 in sample and $0.73$ out of sample, but provides only a coarse runtime estimate. Controlled experiments identify excited-state trapping during warm-started density-matrix renormalization group (DMRG) sweeps and demonstrate mitigation by restarting the variational search. These diagnostics do not yield a validated solver-selection rule. The tested linear-ramp quantum approximate optimization algorithm (LR-QAOA) runs offer no solution-quality improvement over the classical comparators. In the separate Wishart scaling study, on the harder setting, none of the classical methods tested reaches the optimum at the sampled sizes from n = 72 onward within the tested budgets. While this does not provide evidence for quantum advantage, it identifies a domain for further investigation.
Related
- Exact Clifford Optimality for Two-Sided Locally Randomized Classical Shadows
- DolphinQCT: The Light-Weighted, Python Based Quasi-Classical Trajectory Setup Tool for ORCA
- A classical trajectory method for diatom-atom-atom ternary association reactions
- Comparing Classical and Quantum Machine Learning for Regression in High Energy Physics Collision Data
- Dynamic Quantum Wormholes: Path-Integral State Selection and the Quantum Throat Trajectory in an Exactly Solvable Thin-Shell Model
BibTeX
@misc{hellstern2026comparing,
title = {{Comparing classical and quantum QUBO solvers: optimality, trajectory diagnostics, and limits of solver selection}},
author = {Gerhard Hellstern and Cedric Schacht and Martin Zaefferer},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35126},
eprint = {2610.35126},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35126},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Comparing classical and quantum QUBO solvers: optimality, trajectory diagnostics, and limits of solver selection
AU - Gerhard Hellstern
AU - Cedric Schacht
AU - Martin Zaefferer
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35126
UR - https://arxiv.org/abs/2610.35126
AB - Comparing solvers for quadratic unconstrained binary optimization (QUBO) requires distinguishing solution quality from optimality certification. We compare classical, tensor-network, and fixed-schedule quantum approaches on 180 benchmark instances from ten families with 14-48 variables, supplemented by harder synthetic instances with known optimal solutions, extending to 128 variables. On the main benchmark, a general-purpose branch-and-cut solver matches all reference energies and certifies 176 instances within a 600,s cap. When the known optima are moved to randomly chosen bitstrings, the search comparison changes: at n = 48 the branch-and-cut solver finds only four of ten optima and certifies none, whereas parallel tempering reaches every optimum in every tested run at a 60,s budget. Structural and trajectory diagnostics explain aspects of tensor-network performance. A treewidth bound ranks trajectory bond-dimension demand at Spearman ρ= 0.78 in sample and $0.73$ out of sample, but provides only a coarse runtime estimate. Controlled experiments identify excited-state trapping during warm-started density-matrix renormalization group (DMRG) sweeps and demonstrate mitigation by restarting the variational search. These diagnostics do not yield a validated solver-selection rule. The tested linear-ramp quantum approximate optimization algorithm (LR-QAOA) runs offer no solution-quality improvement over the classical comparators. In the separate Wishart scaling study, on the harder setting, none of the classical methods tested reaches the optimum at the sampled sizes from n = 72 onward within the tested budgets. While this does not provide evidence for quantum advantage, it identifies a domain for further investigation.
ER -