摘要：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(
√
T n3/2
logn) 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.
关键词：quantum computing; quantum query complexity; quantum walk
