Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems

Abstract

Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. However, the solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. In order to deal with this issue, we propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits. We analyze the performance of this method on two problems, the knapsack problem and the traveling salesman problem. Our results show the advantages of this method, that balances the number of steps that the algorithm has to make with the amount of error in the solution found by the quantum hardware that the user is willing to risk. All the results are actual runs on the quantum annealer D-Wave Advantage.

arXiv comment11 pages, 11 figures

References in corpus (7)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Adiabatic Quantum Computing
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• Quantum versus Classical Annealing of Ising Spin Glasses
• Searching for quantum speedup in quasistatic quantum annealers
• Building an iterative heuristic solver for a quantum annealer