(251f) Hybrid Quantum Branch-and-Bound Method for Quadratic Unconstrained Binary Optimization

With the advancement of quantum hardware and theory, quantum algorithms have demonstrated their effectiveness in finding high-quality solutions for Quadratic Unconstrained Binary Optimization (QUBO) problems [1]. Moreover, there exists a myriad of novel methods aimed at finding reasonable solutions to QUBO problems efficiently, named Ising solvers, given the equivalence of QUBO to the transverse field Ising problem in statistical physics. However, optimization problems of interest to process system engineering are more general than QUBOs, usually involving discrete non-binary and continuous variables and constraints. Although it is possible to map such problems onto QUBOs [2], the size of solvable QUBOs is inherently limited by the number of qubits in available quantum computers. Moreover, the global optimality of the solution cannot be guaranteed due to the thermal noise and the nature of the algorithms implementable for this problem class in quantum devices. Guaranteeing global optimality has been recently addressed using hybrid quantum-classical algorithms [3], [4].

This work presents a hybrid quantum branch-and-bound method to address these challenges. This method utilizes the computational strengths of quantum hardware alongside the global search capabilities of the branch-and-bound method. The strategy of breaking the problem into smaller subproblems aligns well with the capabilities of quantum hardware[1]. Contrary to previous work on characterizing the hardness of a branch-and-bound enhanced with quantum algorithms for exploring the nodes [5], this work provides a practical implementation of the method relying on a classical branch-and-bound enhanced with Ising solvers, potentially leveraging quantum mechanics, in an open-access repository (https://github.com/SECQUOIA/QuantumBranchAndBound). The Ising solver serves as a heuristic method, and we further explore the strategy of when and where to apply it within the branch and bound framework. Particularly, limitations in quantum annealers related to the embedding problem [6] set such limitations.

Additionally, a customized branching rule and an optimized embedding of QUBO problems are applied to accelerate the convergence of the algorithm, where even without enhancing the commercial solver Gurobi 11 with the solutions coming from Ising solvers, we can achieve a speedup of 20% with respect to the default branching rule in Gurobi. The performance of the proposed method is evaluated on hundreds of QUBO instances from QUBOLib.jl (https://github.com/SECQUOIA/QUBOLib.jl), using Gurobi as the branch-and-bound solver, several physics-inspired classical heuristics [7] and the D-Wave quantum annealer as the quantum solver. Detailed computational results are presented, and the proposed method, Gurobi, and the hybrid B&B method are compared with classical heuristic approaches. Improvements in the solution time go up to 14%, and the reduction of the number of nodes explored to prove optimality reaches 16% using Ising solvers with respect to default Gurobi when solving QUBO problems to 0.01% of optimality, highlighting the value of this hybrid approach.

Reference

[1] Bernal, D. E., Ajagekar, A., Harwood, S. M., Stober, S. T., Trenev, D., & You, F. (2022). Perspectives of quantum computing for chemical engineering. AIChE Journal, 68(6), e17651.

[2] Xavier, P. M., Ripper, P., Andrade, T., Garcia, J. D., Maculan, N., & Neira, D. E. B. (2023). QUBO.jl: A Julia ecosystem for quadratic unconstrained binary optimization. arXiv preprint arXiv:2307.02577.

[3] Brown, R., Neira, D. E. B., Venturelli, D., & Pavone, M. (2022). Copositive programming for mixed-binary quadratic optimization via Ising solvers. arXiv preprint arXiv:2207.13630.

[4] Gambella, C., & Simonetto, A. (2020). Multiblock ADMM heuristics for mixed-binary optimization on classical and quantum computers. IEEE Transactions on Quantum Engineering, 1, 1-22.

[5] Chakrabarti, S., Minssen, P., Yalovetzky, R., & Pistoia, M. (2022). Universal quantum speedup for branch-and-bound, branch-and-cut, and tree-search algorithms. arXiv preprint arXiv:2210.03210.

[6] Bernal, D. E., Booth, K. E., Dridi, R., Alghassi, H., Tayur, S., & Venturelli, D. (2020). Integer programming techniques for minor-embedding in quantum annealers. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 17th International Conference, CPAIOR 2020, Vienna, Austria, September 21–24, 2020, Proceedings 17 (pp. 112-129). Springer International Publishing.

[7] Dunning, I., Gupta, S., & Silberholz, J. (2018). What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS Journal on Computing, 30(3), 608-624.