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.
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.
Quantum algorithms have shown promise in solving Quadratic Unconstrained Binary Optimization (QUBO) problems, benefiting from their connection to the transverse field Ising model.Various Ising solvers, both classical and quantum, have emerged to tackle such problems efficiently but lack global optimality guarantees and oftentimes sufer from hardware limitations such as limited qubit availability.In this work, we propose a hybrid branch-andbound (B&B) framework that integrates Ising solvers as heuristics within a classical B&B algorithm.Unlike prior theoretical studies, our work presents a practical implementation, available as open-source at GitHub.We explore when and where to apply Ising solvers in the search tree, and introduce a custom branching rule optimized QUBO embedding.Our method is evaluated on hundreds of QUBO instances from QUBOLib.jl using Gurobi and the D-Wave quantum annealer.Our Results show up to 11% less solution time and 17% fewer nodes compared to default Gurobi, an off-the-shelf commercial optimization solver.These findings demonstrate the value of hybrid quantum-classical strategies for enhancing exact optimization.
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.
Mixed Integer Programs (MIPs) model many optimization problems of interest in Computer Science, Operations Research, and Financial Engineering. Solving MIPs is NP-Hard in general, but several solvers have found success in obtaining near-optimal solutions for problems of intermediate size. Branch-and-Cut algorithms, which combine Branch-and-Bound logic with cutting-plane routines, are at the core of modern MIP solvers. Montanaro proposed a quantum algorithm with a near-quadratic speedup compared to classical Branch-and-Bound algorithms in the worst case, when every optimal solution is desired. In practice, however, a near-optimal solution is satisfactory, and by leveraging tree-search heuristics to search only a portion of the solution tree, classical algorithms can perform much better than the worst-case guarantee. In this paper, we propose a quantum algorithm, Incremental-Quantum-Branch-and-Bound, with universal near-quadratic speedup over classical Branch-and-Bound algorithms for every input, i.e., if classical Branch-and-Bound has complexity Q on an instance that leads to solution depth d, Incremental-Quantum-Branch-and-Bound offers the same guarantees with a complexity of O~(Qd). Our results are valid for a wide variety of search heuristics, including depth-based, cost-based, and A∗ heuristics. Universal speedups are also obtained for Branch-and-Cut as well as heuristic tree search. Our algorithms are directly comparable to commercial MIP solvers, and guarantee near quadratic speedup whenever Q≫d. We use numerical simulation to verify that Q≫d for typical instances of the Sherrington-Kirkpatrick model, Maximum Independent Set, and Portfolio Optimization; as well as to extrapolate the dependence of Q on input size parameters. This allows us to project the typical performance of our quantum algorithms for these important problems.
Abstract The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
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.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.