Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms

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 commercial solvers often find near-optimal solutions for problems of intermediate size. Modern MIP solvers use Branch-and-Cut algorithms, which combine Branch-and-Bound logic with cutting-plane routines. 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. We propose a quantum algorithm 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 a given instance, our algorithm offers the same guarantees with a complexity of about √Q. 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 such as Gurobi and CPLEX, and guarantee near quadratic speedup for a wide range of optimization problems.