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.
AI Summary
The paper asks how QUBO solver comparisons change when solution search, optimality certification, and computational cost are evaluated separately, and whether structural or quantum-state diagnostics support solver selection. It benchmarks Gurobi branch-and-cut, simulated annealing (SA), parallel tempering (PT), a DMRG-based MPS anneal, and classically simulated fixed-schedule linear-ramp QAOA. The main dataset contains 180 benchmark entries across ten synthetic families at $n=14$–$48$ (156 distinct matrices), supplemented by gauge-randomised planted Wishart instances extending to $n=128$.
On the main benchmark, Gurobi matches all reference energies and returns 176 optimal statuses within 600 seconds; 179 references are independently established as optimal or solver-certified. Randomising the planted optimum’s location changes the search comparison: on ten gauged Wishart instances at $n=48$, Gurobi finds four optima and certifies none, whereas PT finds every optimum in all tested 60-second runs. A heuristic treewidth bound correlates with diagnostic trajectory bond-dimension demand at Spearman $\rho=0.78$ in calibration and $0.73$ out of sample, but predicts runtime only coarsely. Spectral comparisons identify excited-state trapping in warm-started DMRG; cold-start resets cure the targeted failures. Neither these diagnostics nor fitted runtime models improve solver selection over always choosing SA.
The 105 main-benchmark LR-QAOA simulations never improve on the better of SA and DMRG. Larger dense-instance simulations lack demonstrated convergence, and small-size probability measurements do not establish efficient scaling. Harder Wishart instances defeat all tested classical methods from $n=72$ onward within the budgets tested, but this is not evidence of quantum advantage. Limitations include small samples, implementation-dependent timings, and restricted solver configurations.
Likely largely AI-generatedAI use disclosedIncrementalMissing comparison
AI assistance (Claude, Anthropic) was used for code development, running analysis and verification scripts, and drafting;
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper asks how QUBO solver comparisons change when solution search, optimality certification, and computational cost are evaluated separately, and whether structural or quantum-state diagnostics support solver selection. It benchmarks Gurobi branch-and-cut, simulated annealing (SA), parallel tempering (PT), a DMRG-based MPS anneal, and classically simulated fixed-schedule linear-ramp QAOA. The main dataset contains 180 benchmark entries across ten synthetic families at n=14–48 (156 distinct matrices), supplemented by gauge-randomised planted Wishart instances extending to n=128.
On the main benchmark, Gurobi matches all reference energies and returns 176 optimal statuses within 600 seconds; 179 references are independently established as optimal or solver-certified. Randomising the planted optimum’s location changes the search comparison: on ten gauged Wishart instances at n=48, Gurobi finds four optima and certifies none, whereas PT finds every optimum in all tested 60-second runs. A heuristic treewidth bound correlates with diagnostic trajectory bond-dimension demand at Spearman ρ=0.78 in calibration and 0.73 out of sample, but predicts runtime only coarsely. Spectral comparisons identify excited-state trapping in warm-started DMRG; cold-start resets cure the targeted failures. Neither these diagnostics nor fitted runtime models improve solver selection over always choosing SA.
The 105 main-benchmark LR-QAOA simulations never improve on the better of SA and DMRG. Larger dense-instance simulations lack demonstrated convergence, and small-size probability measurements do not establish efficient scaling. Harder Wishart instances defeat all tested classical methods from n=72 onward within the budgets tested, but this is not evidence of quantum advantage. Limitations include small samples, implementation-dependent timings, and restricted solver configurations.
Quadratic Unconstrained Binary Optimization (QUBO) provides a versatile framework for representing NP-hard combinatorial problems, yet existing solvers often face trade-offs among speed, accuracy, and scalability. In this work, we introduce a quantum-inspired solver (QIS) that unites branch-and-bound pruning, continuous gradient-descent refinement, and quantum-inspired heuristics within a fully adaptive control architecture. We benchmark QIS3 against eight state-of-the-art solvers, including genetic algorithms, coherent Ising machines, simulated bifurcation, parallel tempering, simulated annealing, our prior QIS2 version, D-Wave's simulated-annealing (Neal), and Gurobi on three canonical QUBO problem classes: Max-Cut, NAE-3SAT, and Sherrington-Kirkpatrick spin glass problems. Under a uniform runtime budget, QIS3 attains the best solution on nearly all instances, achieving optimality in 94% of max-cut instances. These results establish QIS3 as a robust, high-performance solver that bridges classical exact strategies and quantum-inspired heuristics for scalable QUBO optimization.
Demonstrating quantum heuristics that outperform strong classical solvers on large-scale optimization remains an open challenge. Here we introduce Regularized Warm-Started QAOA (RWS-QAOA), which initializes qubits by minimizing expected energy with a regularizer that penalizes near-bitstring states, preventing QAOA from stalling. We further propose a protocol that yields fixed, instance-independent parameters, enabling RWS-QAOA to operate as a non-variational algorithm in which the quantum circuit parameters are fixed and only a classical warm starting step is instance-dependent. We evaluate RWS-QAOA on the Max-Cut problem for random regular graphs, where this protocol yields a constant-depth quantum circuit, across three complementary settings. First, on Quantinuum's trapped-ion processor, RWS-QAOA outperforms the classical algorithms with the best provable guarantees for Max-Cut on 3-regular graphs, namely Goemans-Williamson and Halperin-Livnat-Zwick, on 96-node instances. Second, tensor-network simulations on graphs with up to N=10,000 nodes show that depth-6 RWS-QAOA, achieving an average cut fraction of 0.9167, surpasses the best classical heuristics under matched restrictions (no local-search post-processing and no iterative refinement). Third, we remove these restrictions and benchmark against the strongest unrestricted classical heuristics, including an optimized parallel Burer-Monteiro solver that improves upon the MQLib implementation. Even against this stronger baseline, we project that surface-code RWS-QAOA reaches a quantum-classical runtime crossover below 0.2 seconds on 3,000-node graphs with fewer than 1.3 million physical qubits. Our results show that constant-depth quantum circuits combined with a classical warm start have a credible potential to surpass classical solvers on the Max-Cut problem when executed on future quantum computers.
We introduce VeloxQ, a fast solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to many real-world optimization tasks. Unlike approaches that depend on emerging quantum hardware, VeloxQ can be deployed on conventional computing infrastructure. We benchmark VeloxQ against state-of-the-art QUBO solvers from several families. These include quantum annealers, specifically D-Wave's Advantage and Advantage2 platforms; the digital-quantum BF-DCQO algorithm for Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum; physics-inspired algorithms including Simulated Bifurcation, Parallel Annealing, and tropical tensor networks; and conventional methods including CPLEX, brute force, BEIT's Chimera solver, and Branch-and-Bound variants. The benchmark suite covers native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances, planted-solution instances, certified-solver regimes, and dense Branch-and-Bound test cases. Across the benchmark suite, VeloxQ delivers competitive solution quality and runtime, and in several regimes outperforms the compared solvers. VeloxQ also demonstrates strong scalability. Among the solvers considered in this study, it was the only method we could run on the largest sparse instances within our computational budget, including problems with up to 108 sparsely connected variables. These findings position VeloxQ as a competitive and practical tool for tackling large-scale QUBO/HUBO problems, offering a practical alternative to existing quantum and classical optimization methods.
Abstract We benchmark classical, simulated-quantum, hybrid, and direct quantum-annealing workflows on a structured binary control problem formulated as a quadratic unconstrained binary optimization (QUBO) model. The benchmark is motivated by greenhouse heater scheduling, where the horizon (H) denotes the number of hourly binary control decisions, but the focus is on solver behavior for a physically decoded control-QUBO formulation. For the main one-day instance ((H=24)), all solver outputs are decoded back into heater schedules and evaluated using the same simulator-side objective and feasibility criterion. Classical simulated annealing and path-integral simulated quantum annealing produce feasible near-optimal solutions in all repetitions, with best objectives close to the exact optimum. In contrast, the tested D-Wave Leap Hybrid binary quadratic model workflow is less reliable and does not outperform the classical baselines under 15--60 s requested time limits. Direct D-Wave quantum processing unit execution on reduced instances remains feasible in all runs and recovers the exact optimum for (H=10) and (H=12), but the exact-hit rate decreases with increasing horizon. The results do not indicate quantum advantage, but provide a reproducible benchmark for evaluating annealing-based natural and quantum computing workflows on structured control QUBOs. MSC Classification: 90C27 , 90C59 , 81P68 , 93C55
Integrated HPC/QC systems aim to combine classical high-performance computing with quantum processors, but cannot be reduced to mechanisms for dispatching quantum kernels. An integrated architecture must support aspects such as observability, which cannot be implemented using QPUs alone, as well as fallback execution and cost-aware decisions on whether to replace quantum tasks with classical surrogates. Such mechanisms must be approximate or benefit from problem structure to soften the inescapable exponential classical worst-case complexity. In this work, we study tensor-network ground-state search, as such a surrogate, for optimisation problems. This combines key quantum primitives with advanced classical simulation. It provides initial empirical indicators for surrogate selection criteria, and exposes end-to-end toolchain effects that may be missed when transformation steps are studied in isolation. We compare a native polynomial unconstrained optimisation to-higher-order-Ising and a quadratised quadratic unconstrained binary optimization to-quadratic-Ising formulation for Max-3-SAT. Both are encoded as matrix product operator and optimised using density matrix renormalisation group approaches, with simulated annealing (SA) as classical performance baseline. Our results show that quadratisation is not a neutral transformation step: auxiliary variables and pairwise couplings substantially degrade solution quality relative to the native higher-order representation, while SA matches or outperforms DMRG across all tested instances. Since the optima of Boolean satisfiability (SAT)-derived problems are classical product states, DMRGs advantages dont materialise here. These findings suggest that surrogate selection in HPC/QC runtimes must be encoding- and instance-aware and provide empirical groundwork for informed decisions on fallback strategies and architecture co-design.
Due to the expected disparity in quantum vs. classical clock speeds, quantum advantage for branch and bound algorithms is more likely achievable in settings involving large search trees and low operator evaluation costs. Therefore, in this paper, we describe and experimentally validate an exact classical branch and bound solver for quadratic unconstrained binary optimization (QUBO) problems that matches these criteria. Our solver leverages cheap-to-implement bounds from the literature previously proposed for Ising models, including that of Hartwig, Daske, and Kobe from 1984. We detail a variety of techniques from high-performance computing and operations research used to boost solver performance, including a global variable reordering heuristic, a primal heuristic based on simulated annealing, and a truncated computation of the recursive bound. We also outline a number of simple and inexpensive bound extrapolation techniques. Finally, we conduct an extensive empirical analysis of our solver, comparing its performance to state-of-the-art QUBO and MaxCut solvers, and discuss the challenges of a speedup via quantum branch and bound beyond those faced by any quadratic quantum speedup.