Theory of Computing
-------------------
Title     : Quantum-Walk Speedup of Backtracking Algorithms
Authors   : Ashley Montanaro
Volume    : 14
Number    : 15
Pages     : 1-24
URL       : https://theoryofcomputing.org/articles/v014a015

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 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.