VeloxQ: A Fast and Efficient QUBO Solver
J. Pawłowski, J. Tuziemski, P. Tarasiuk, H. Louzada, R. Adamski, K. Hendzel, Ł. Pawela, B. Gardas · 2025
Read VeloxQ: A Fast and Efficient QUBO Solver by J. Pawłowski, J. Tuziemski, P. Tarasiuk, H. Louzada, R. Adamski, K. Hendzel, Ł. Pawela, B. Gardas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19221.txt.
Introduction
Pawłowski, Tuziemski, Tarasiuk and colleagues introduce VeloxQ, a solver for quadratic unconstrained binary optimisation problems, in 2025. Such problems sit at the heart of many scheduling, routing and design tasks, and new quantum machines are often pitched as the way to crack them.
VeloxQ instead runs on ordinary computers. Benchmarked against quantum annealers, physics-inspired methods and classical solvers such as CPLEX, it matched or beat rivals in several regimes. It was also the only solver the team could run on the largest sparse problems, with up to a hundred million variables. The results make it a practical option for very large optimisation work today.
Catalog record
| CREATOR | J. Pawłowski, J. Tuziemski, P. Tarasiuk, H. Louzada, R. Adamski, K. Hendzel, Ł. Pawela, B. Gardas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-19221
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
VeloxQ: A Fast and Efficient QUBO Solver J. Pawłowski, J. Tuziemski, P. Tarasiuk, H. Louzada, R. Adamski, K. Hendzel, Ł. Pawela, B. Gardas Abstract 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 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. I Introduction The increasing complexity of real-world optimization problems poses a serious challenge to state-of-the-art methods. The growing size and complexity of industry-relevant instances may soon limit the performance of well-established exact and heuristic approaches. Recent progress in emerging computational paradigms, including quantum computing and physics-inspired algorithms, has opened new opportunities for the development of optimization methods that may outperform conventional techniques on selected classes of QUBO problems. For example, simulating the dynamics of certain classical systems has recently proven to be a promising heuristic approach to QUBO optimization [ 36 , 35 , 48 ] . In contrast to other physics-inspired optimization algorithms such as Simulated Annealing [ 50 ] , these approaches can take advantage of conventional parallel hardware. Here we present VeloxQ [ 64 ] , a QUBO solver based on a novel physics-inspired methodology. Unlike approaches that rely on further advances in quantum hardware, VeloxQ can fully exploit conventional computing hardware today. In this sense, VeloxQ bridges established and emerging approaches to optimization and may also serve as a practical component of hybrid quantum-classical workflows, although such integrations are outside the scope of the present paper. This document is intended as a technical white paper aimed at practitioners considering QUBO solvers for production use, rather than as a peer-reviewed journal submission. Its aim is to provide an extensive set of benchmarks that characterizes key features of VeloxQ, including solution quality and runtime. To place VeloxQ in the broader QUBO landscape, we compare it with a wide range of competing approaches, including the commercial optimization suite CPLEX, quantum-analog solvers offered by D-Wave, the digital-quantum optimization algorithm developed by Kipu Quantum [ 65 ] , and an optimized implementation of the brute-force QUBO solver [ 47 , 46 , 45 ] . The comparison also covers solvers with ground-state certification, including the BEIT QUBO solver [ 5 , 4 ] and a physics-inspired algorithm based on tropical tensor networks [ 54 ] , as well as heuristic and classical methods such as parallel annealing [ 48 ] , simulated bifurcation [ 36 ] , and modern Branch-and-Bound variants [ 14 , 63 ] . The benchmark set includes instances that are favorable to the solvers compared with VeloxQ. This choice allows us to identify their strengths and reduces the risk that VeloxQ performance appears favorable only because of biased instance selection. The three central claims tested below are solution quality, runtime, and scalability. Across these benchmarks, VeloxQ is competitive with the compared solvers in solution quality and runtime, while its main distinction is scalability: among the methods included in this study, it is the only one that we were able to run successfully on the largest sparse instances considered here. As in several of the compared methods, however, VeloxQ results are not certified, i.e. , the returned solution is not guaranteed to be optimal. For example, VeloxQ can solve an optimization problem on the Zephyr graph Z_{1750} , which involves more than 9.8\times 10^{7} variables. As an illustrative scale comparison, Fig. 1 shows a simple extrapolation from past D-Wave device sizes to a native graph of that magnitude; this estimate should be interpreted only as a rough indication of scale. A similar scale separation appears in the comparison with the digital quantum algorithm developed by Kipu Quantum, for which VeloxQ can handle an instance with 10^{8} variables. There are notable emerging QUBO solution technologies that we do not include in this comparison. Memcomputing is a promising approach to QUBO optimization [ 66 ] ; however, we were not able to access a solver based on this methodology. Considerable effort has also been devoted to coherent Ising machines, both from the hardware perspective [ 67 ] and in the theoretical study of the relation between binary solutions and their continuous relaxations [ 75 , 72 ] . We decided not to include coherent Ising machines because their behavior is similar to that of the simulated bifurcation algorithm. We also implemented an annealer based on Hamiltonian Monte Carlo [ 71 ] , but the initial results were not satisfactory and we therefore did not pursue an extensive benchmark. Finally, approaches based on classical thermodynamics, such as quadratic programming enhanced by thermodynamic linear algebra subroutines [ 3 , 2 ] , were not considered because they require specialized hardware that is currently unavailable and do not solve binary problems natively. To make the paper self-contained, Sec. II introduces the definition of QUBO problems, their relation to the Ising model, and higher-order unconstrained binary optimization. Sec. III reviews state-of-the-art approaches to solving QUBO problems. The benchmark sections are organized as follows. Sec. V presents benchmarks against D-Wave quantum annealers. Sec. VI compares VeloxQ with the digital quantum algorithm developed by Kipu Quantum. Sec. VII discusses benchmarks against solvers with certified solutions, including the BEIT solver [ 5 , 4 ] and a tropical tensor network approach. Sec. VIII presents results against physics-inspired algorithms, namely parallel annealing and simulated bifurcation. Sec. IX compares VeloxQ with a refined Branch-and-Bound (B&B) algorithm proposed by Quantagonia [ 63 ] . We summarize our findings in Sec. X . Each benchmark addresses a different problem: instances native to quantum hardware, impact of embedding overhead, reduction of higher-order problems to QUBO, cost of certified solution and performance on planted-solution instances. All benchmark instances, generation scripts, plotting scripts, and relevant data are provided in the separate online repository [ 21 ] . While VeloxQ is a proprietary solver, access is provided via the open Python API veloxq_sdk [ 68 ] . Sec. V.3 discusses the API in more detail, including a comparison against the D-Wave API. FIG. 1. : Comparison of past and current D-Wave quantum-annealer qubit counts with an illustrative extrapolation to the Z_{1750} instance solved by VeloxQ, containing \sim 9.8\times 10^{7} variables (purple hexagon). Under a simple doubling-every-two-years extrapolation estimated from historical