# 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/en/paper/1906.10375v1/

## Key points

- Branch-and-bound is a widely used technique for solving combinatorial optimization problems
- Ashley Montanaro introduced a quantum algorithm to accelerate classical branch-and-bound algorithms
- The quantum algorithm demonstrates near-quadratic speedup compared to traditional methods
- The research showcases the efficiency of the quantum algorithm in finding exact ground states for the majority of instances of the Sherrington-Kirkpatrick model
- The algorithm achieves this feat in an impressive time complexity of $O(2^{0.226n}), surpassing Grover's algorithm performance significantly
- Published study in Phys. Rev. Research 2, 013056 (2020) offers promising prospects for enhancing computational capabilities through quantum acceleration techniques

## Summary

Branch-and-bound is a widely used technique for solving combinatorial optimization problems. It involves dividing potential solutions into subsets and determining lower bounds on their costs. In a recent study by Ashley Montanaro, a quantum algorithm was introduced to significantly accelerate classical branch-and-bound algorithms in various scenarios. This quantum algorithm demonstrates near-quadratic speedup compared to traditional methods. Specifically, the research showcases the remarkable efficiency of the quantum algorithm in finding exact ground states for the majority of instances of the Sherrington-Kirkpatrick model. The algorithm achieves this feat in an impressive time complexity of $O(2^{0.226n}), surpassing the performance of Grover's algorithm by a substantial margin. The findings presented in this study, published in Phys. Rev. Research 2, 013056 (2020), offer promising prospects for enhancing computational capabilities in solving complex optimization problems through quantum acceleration techniques. Ashley Montanaro's work sheds light on the potential of quantum computing to revolutionize traditional algorithms and pave the way for more efficient problem-solving strategies in various fields.