# Quantum speedup of branch-and-bound algorithms

**Authors:** Ashley Montanaro  
**arXiv:** [1906.10375](https://arxiv.org/abs/1906.10375)  
**Date:** 2019-06-25  
**Summary page:** https://www.summarizepaper.com/fr/paper/1906.10375v1/

## Abstract

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(2^{0.226n})$, which is substantially more efficient than Grover's algorithm.