Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Branch-Collapse Search for Dense QUBO Optimization: Equal-Time Comparison with Greedy, Simulated Annealing, and Tabu Baselines

King Quantum

Published May 15, 2026• 0 citations
Publisher

Abstract

This technical report presents an empirical validation study of Branch-Collapse search for dense Quadratic Unconstrained Binary Optimization (QUBO). The method is evaluated against greedy local search, simulated annealing, and an implemented Tabu search baseline under fixed benchmark conditions. The study reports results on locked dense random QUBO instances, including primary benchmarks at n = 50, 60, and 70, larger scaling probes, and equal wall-clock Tabu comparisons at n = 300, n = 500, and n = 750. The strongest completed validation compares an RQCE-derived Branch-Collapse solver against the implemented Tabu baseline on n = 500 dense QUBO instances across five Python hash seeds, achieving 100 wins, 0 losses, and 0 ties at 0.5s, 1.0s, and 2.0s, and 98 wins, 2 losses, and 0 ties at 5.0s. A further n = 750 scaling pilot achieved 10 wins, 0 losses, and 0 ties at each tested budget. The report includes baseline descriptions, benchmark methodology, robustness checks, selected seed-level energy tables, checkpoint audit outputs, file-hash evidence for a locked validation artifact, and a clear statement of limitations. The results should be interpreted as author-reported empirical validation under the stated benchmark conditions, not as a claim of global optimality or superiority over all possible Tabu implementations or all QUBO instance families. A separate controlled technical appendix containing additional seed-level outputs, validation commands, audit records, and locked-file metadata is retained by the author and may be made available for controlled technical review.

DOI
10.5281/zenodo.20190382

Related papers

Quantum Portfolio Optimization Under Realistic Frictions: A Rigorous Comparison with Classical Baselines

Ekow Tawiah Andoh

We test whether quantum-inspired optimization, specifically Quadratic Unconstrained Binary Optimization (QUBO) solved via simulated annealing, can improve implementable portfolio performance compared to classical baselines when realistic frictions are included. Our experimental design uses daily returns from the Center for Research in Security Prices (CRSP) for S&P500 constituents spanning 2014–2025, with monthly rebalancing, explicit transaction costs, and turnover accounting. We compare QUBO portfolios against equal-weight and convex mean–variance portfolios across multiple universe sizes (20, 50, 67 assets), lookback windows, and transaction-cost levels. Statistical significance is assessed via paired moving-block bootstrap on out-of-sample net returns. A hyperparameter sweep over encoding depth, penalty coefficients, and turnover reveals 19 of 81 QUBO configurations beat the equal-weight baseline, with the best achieving a Sharpe of 1.59 versus 1.42. However, under a fair walk forward model-selection protocol that eliminates look-ahead bias, the QUBO strategy does not achieve statistically significant superiority over either classical benchmark (∆Sharpe vs. equal weight: −0.13, 95% CI [−0.46,0.16]; vs. mean–variance: −0.29, 95% CI [−0.63,0.06]). Excessive turnover (averaging ∼1.0 per rebalance) is identified as the primary bottleneck. We conclude that current QUBO formulations with simulated annealing do not yet deliver a robust, implementable edge over well-tuned convex optimizers, though the framework remains a promising research direction as quantum hardware and hybrid solvers mature.

•Mar 24, 2026•0 citations

VeloxQ: A Fast and Efficient QUBO Solver

Jakub Pawłowski, Jan Tuziemski, Paweł Tarasiuk +5 more

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 $10^{8}$ 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.

arXiv:2501.19221•Jan 31, 2025•2 citations

Solving QUBOs with a quantum-amenable branch and bound method

Thomas Häner, Kyle E. C. Booth, Sima Esfandiarpour Borujeni +1 more

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.

arXiv:2407.20185•Jul 29, 2024•0 citations

An Efficient Closed-Form Formula for Evaluating r-Flip Moves in Quadratic Unconstrained Binary Optimization

Bahram Alidaee, Haibo Wang, Lutfu Sagbansua

Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy “flips” r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.

Algorithms•Dec 5, 2023•4 citations

Comparing classical and quantum QUBO solvers: optimality, trajectory diagnostics, and limits of solver selection

Gerhard Hellstern, Cedric Schacht, Martin Zaefferer

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.

quant-pharXiv:2610.35126•Oct 27, 2026•0 citations

A Novel Solver for QUBO Problems: Performance Analysis and Comparative Study with State-of-the-Art Algorithms

Jiecheng Yang, Ding Wang, Xiang Zhao +3 more

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.

arXiv:2506.04596•Jun 5, 2025•0 citations
This technical report presents an empirical validation study of Branch-Collapse search for dense Quadratic Unconstrained Binary Optimization (QUBO). The method is evaluated against greedy local search, simulated annealing, and an implemented Tabu search baseline under fixed benchmark conditions. The study reports results on locked dense random QUBO instances, including primary benchmarks at n = 50, 60, and 70, larger scaling probes, and equal wall-clock Tabu comparisons at n = 300, n = 500, and n = 750. The strongest completed validation compares an RQCE-derived Branch-Collapse solver against the implemented Tabu baseline on n = 500 dense QUBO instances across five Python hash seeds, achieving 100 wins, 0 losses, and 0 ties at 0.5s, 1.0s, and 2.0s, and 98 wins, 2 losses, and 0 ties at 5.0s. A further n = 750 scaling pilot achieved 10 wins, 0 losses, and 0 ties at each tested budget. The report includes baseline descriptions, benchmark methodology, robustness checks, selected seed-level energy tables, checkpoint audit outputs, file-hash evidence for a locked validation artifact, and a clear statement of limitations. The results should be interpreted as author-reported empirical validation under the stated benchmark conditions, not as a claim of global optimality or superiority over all possible Tabu implementations or all QUBO instance families. A separate controlled technical appendix containing additional seed-level outputs, validation commands, audit records, and locked-file metadata is retained by the author and may be made available for controlled technical review.
We test whether quantum-inspired optimization, specifically Quadratic Unconstrained Binary Optimization (QUBO) solved via simulated annealing, can improve implementable portfolio performance compared to classical baselines when realistic frictions are included. Our experimental design uses daily returns from the Center for Research in Security Prices (CRSP) for S&P500 constituents spanning 2014–2025, with monthly rebalancing, explicit transaction costs, and turnover accounting. We compare QUBO portfolios against equal-weight and convex mean–variance portfolios across multiple universe sizes (20, 50, 67 assets), lookback windows, and transaction-cost levels. Statistical significance is assessed via paired moving-block bootstrap on out-of-sample net returns. A hyperparameter sweep over encoding depth, penalty coefficients, and turnover reveals 19 of 81 QUBO configurations beat the equal-weight baseline, with the best achieving a Sharpe of 1.59 versus 1.42. However, under a fair walk forward model-selection protocol that eliminates look-ahead bias, the QUBO strategy does not achieve statistically significant superiority over either classical benchmark (∆Sharpe vs. equal weight: −0.13, 95% CI [−0.46,0.16]; vs. mean–variance: −0.29, 95% CI [−0.63,0.06]). Excessive turnover (averaging ∼1.0 per rebalance) is identified as the primary bottleneck. We conclude that current QUBO formulations with simulated annealing do not yet deliver a robust, implementable edge over well-tuned convex optimizers, though the framework remains a promising research direction as quantum hardware and hybrid solvers mature.
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 10810^{8}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.
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.
Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy “flips” r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.
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ρ= 0.78ρ=0.78 in sample and 0.730.730.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.
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.