Southwest Quantum Information and Technology

Quantum speedup of backtracking and Monte Carlo algorithms

Presenting Author: Ashley Montanaro, (University of Bristol)

In this talk I will describe how quantum computing can accelerate two standard types of classical algorithms: backtracking algorithms and Monte Carlo methods. Backtracking is a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. I will present a bounded-error quantum algorithm which finds a solution in time which is (almost) bounded by the square root of the size of the tree. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree. Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. I will present a quantum algorithm which uses amplitude amplification to estimate the expected output value of an arbitrary randomised or quantum subroutine with bounded variance, and achieves a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques.

Read this article online: http://arxiv.org/abs/1509.02374

(Session 7 : Friday from 10:15 am - 11:00 am)