2019/06/25 by Ashley Montanaro · 1 citation
Computer Science · Physics and Astronomy · #cs.DS #quant-ph
paper · pdf · doi:10.1103/physrevresearch.2.013056
published as Phys. Rev. Research 2, 013056 (2020) · 11 pages, 5 figures
arxiv created 2019/06/25 · arxiv updated 2020/01/22
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.