# Quantum speedup of branch-and-bound algorithms

arXiv: https://arxiv.org/abs/1906.10375 · HTML: https://mlsanity.com/paper/1906.10375/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2019.

## Built on by (most cited first, 1 of 1)

- [Explainable AI using expressive Boolean formulas](https://mlsanity.com/paper/2306.03976/) (2023)

## Abstract (arXiv)

Branch-and-bound is a widely used technique for solving combinatorial optimisation problems where one has access to two procedures: a branching procedure that splits a set of potential solutions into subsets, and a cost procedure that determines a lower bound on the cost of any solution in a given subset. Here we describe a quantum algorithm that can accelerate classical branch-and-bound algorithms near-quadratically in a very general setting. We show that the quantum algorithm can find exact ground states for most instances of the Sherrington-Kirkpatrick model in time O(20.226n), which is substantially more efficient than Grover's algorithm.