Hybrid Quantum Branch-and-Bound Solves Quadratic Unconstrained Binary Optimization with Enhanced Heuristics

Quadratic Unconstrained Binary Optimisation (QUBO) problems represent a significant challenge in fields ranging from machine learning to materials science, yet finding truly optimal solutions remains difficult. Zedong Peng from Purdue University, Daniel de Roux from Carnegie Mellon University and Google, and David E Bernal Neira from Purdue University, now demonstrate a new approach that combines the strengths of both quantum and classical computing. Their team developed a hybrid algorithm integrating quantum Ising solvers as guiding heuristics within a classical branch-and-bound framework, offering a practical pathway towards guaranteed optimal solutions. By carefully determining when and where to employ quantum computation, and optimising the problem’s structure for quantum processing, they achieve substantial improvements in solution time and computational effort, surpassing the performance of leading commercial optimisation software on a wide range of benchmark problems. This work establishes the potential of hybrid quantum-classical strategies to deliver significant advances in exact optimisation for complex real-world challenges.

It details various approaches, including classical algorithms, quantum algorithms like quantum annealing and variational quantum algorithms, and hybrid methods. The core focus lies in solving problems expressible as QUBOs or Ising models, versatile formulations for many computationally challenging problems such as MaxCut and graph coloring. A significant theme is the need for robust benchmarks and evaluation methods to compare the performance of different solvers, both classical and quantum.

Classical approaches frequently employ methods like simulated annealing, tabu search, genetic algorithms, and multistart strategies. Branch and bound algorithms, often combined with cutting planes, are also highlighted as effective for finding optimal solutions, especially for sparse problems, with recent work focusing on improving efficiency through techniques like digitized counterdiabatic quantum optimization. Quantum approaches prominently feature quantum annealing, utilizing devices like those from D-Wave. Challenges include embedding problems onto the hardware and verifying solution quality.

Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA), are explored as potential solutions, though concerns exist regarding barren plateaus and cost function locality. A key trend involves combining quantum and classical techniques, for example, using quantum algorithms to generate candidate solutions for a classical branch and bound algorithm. Problem structure significantly influences solver performance, and scalability remains a major hurdle for both classical and quantum methods. Current research emphasizes addressing challenges like barren plateaus in VQAs and effective embedding for quantum annealers. This framework integrates Ising solvers as heuristics within a classical B and B algorithm, preserving global optimality guarantees. This work presents a practical implementation and explores strategic application of Ising solvers within the B and B search tree, optimizing the process for QUBO embedding. Scientists meticulously evaluated the method on hundreds of QUBO instances sourced from QUBOLib. jl, employing both the commercial solver Gurobi and the D-Wave quantum annealer as comparative benchmarks and heuristic tools within the B and B framework.

The core innovation lies in a custom branching rule designed to improve QUBO embedding, effectively guiding the B and B search and reducing computational effort. Experiments involved systematically comparing the performance of this hybrid approach against default Gurobi settings, measuring both solution time and the number of nodes explored during the search. Results demonstrate a significant improvement in efficiency, with the hybrid method achieving up to 11% less solution time and 17% fewer nodes explored compared to standard Gurobi optimization. This improvement stems from the strategic integration of the Ising solvers, which effectively prune the search space and guide the B and B algorithm towards optimal solutions. This work presents a practical implementation, publicly available as open-source software, and benchmarks it against a suite of over 5,000 QUBO instances. The team explored strategies for strategically applying Ising solvers during the B and B search process and introduced a custom branching rule optimized for QUBO embedding. Experiments demonstrate a median reduction of 17% in the number of nodes explored by the B and B algorithm and an 11% decrease in overall solution time compared to the standard Gurobi solver.

Specifically, the shifted geometric mean with a 10-second shift (SGM10) reduced the baseline solve time from 154 seconds to 137 seconds. The method incorporates a preprocessing step to reduce the size of subproblems and utilizes a branching rule informed by the degree of variables within the QUBO interaction graph. This hybrid approach leverages the strengths of both classical and Ising-based solvers, enabling more efficient exploration of the solution space while maintaining guarantees of global optimality. The team successfully interfaced their algorithm with both simulated and hardware Ising solvers, demonstrating its versatility and potential for tackling complex optimization challenges. Researchers developed a practical implementation, openly available, to systematically explore when and how to best utilize these solvers during the optimization process, alongside a branching rule specifically designed for QUBO embedding. Extensive testing on over 5,800 instances from the QUBOLib collection demonstrates the effectiveness of this method. Results indicate that incorporating solutions from Ising solvers improves performance by approximately 5%, while the optimized branching rule alone reduces both solution time and the number of nodes explored by over 10%.

However, the team acknowledges that the observed improvements currently fall short of the theoretical maximum achievable through perfect integration of solvers. Future research will focus on developing more effective methods for integrating quantum solvers as node-wise heuristics to further enhance the capabilities of this hybrid strategy. This work validates the potential of combining classical and quantum techniques to accelerate exact solvers for structured QUBO problems.