Hi Everybody,

Ashley Montanaro from the University of Bristol is visiting us this week. On Friday, Ashley is giving the qip seminar. Please find details below, and please let me know if you want to schedule a meeting

Best,
cyril

Speaker: Ashley Montanaro (University of Bristol) 
Title: Quantum walk speedup of backtracking algorithms
Place: 6C-442
Time: 1:30 (October 30)
Abstract: In this talk I will discuss a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, 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. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. I will present a bounded-error quantum algorithm which completes the same task using O(sqrt(T) n^(3/2) log n) tests. 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. I will also discuss how, for certain distributions on the inputs, the algorithm can lead to an average-case exponential speedup.

--
Cyril Stark
Center for Theoretical Physics
Massachusetts Institute of Technology
77 Massachusetts Ave, 6-304
Cambridge, MA 02139, USA