Quantum speedup of branch-and-bound algorithms
Ashley Montanaro
Abstract
Quantum computers could significantly outperform their classical counterparts for solving hard optimization problems. One prominent classical technique for such problems is known as branch-and-bound. This work describes a quantum algorithm for accelerating general branch-and-bound methods, and gives an application to spin glasses.
Topics & Concepts
Quantum algorithmSpeedupAlgorithmComputer scienceQuantumQuantum computerQuantum phase estimation algorithmQuantum sortQuantum algorithm for linear systems of equationsWork (physics)Theoretical computer scienceMathematicsQuantum annealingQuantum informationQuantum Fourier transformSpin (aerodynamics)Efficient algorithmQuantum information scienceProcess (computing)Quantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsMathematical Approximation and Integration