Projects per year
Abstract
We describe 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. Then we show that there is a boundederror quantum algorithm which completes the same task using (Formula presented) 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.
Original language  English 

Article number  15 
Number of pages  24 
Journal  Theory of Computing 
Volume  14 
DOIs  
Publication status  Published  3 Dec 2018 
Structured keywords
 QITG
Keywords
 Quantum computing
 Quantum query complexity
 Quantum walk
Fingerprint
Dive into the research topics of 'QuantumWalk Speedup of Backtracking Algorithms'. Together they form a unique fingerprint.Projects
 1 Finished
Activities
 1 Fellowship awarded competitively

EPSRC Fellowship  New insights in quantum algorithms and complexity.
Ashley Montanaro (Recipient)
31 Jul 2014 → 31 Jul 2019Activity: Other activity types › Fellowship awarded competitively
Profiles

Professor Ashley M R Montanaro
 School of Mathematics  Professor of Quantum Computation
 The Bristol Centre for Nanoscience and Quantum Information
 Theory and Algorithms
 Mathematical Physics
 Quantum Information Theory
Person: Academic , Member, Group lead