Quantum computers [2, 4, 16, 17, 19, 20, 40] offer a new approach to combinatorial search problems [23] with quantum parallelism, i.e., the ability to operate simultaneously on many classical search states, and interference among different paths through the search space. A quantum algorithm to rapidly factor integers [49], a problem thought to be intractable for classical machines, offers a dramatic example of how these features of quantum mechanics can be exploited.
While several additional algorithms have been developed [7, 11, 27, 26, 29, 30, 51], the extent to which quantum searches can improve on heuristically guided classical search methods remains an open question. Quantum algorithms can be based directly on classical heuristics, achieving a search cost that is the square root of the corresponding classical method [8, 10]. Obtaining further improvement requires uniquely quantum mechanical methods. Heuristics exploit the structure of the search problems to greatly reduce the search cost in many cases. The success of these heuristics raises the question of whether the structure of search problems can form the basis of even better quantum algorithms. A suggestion that this is possible has been observed empirically for highly constrained problems [30], but the complexity of the algorithm precluded a definitive theoretical analysis of its behavior.
This paper presents a new quantum search algorithm that is extremely effective for some highly constrained search problems. These constraints also allow for effective classical heuristics, i.e., these problems are relatively easy. However, the new quantum algorithm requires even fewer steps than the best classical methods, providing another example of search problems for which quantum computers can outperform classical ones. More significantly, this algorithm illustrates how knowledge of the structure inherent in search problems can be used to develop new algorithms. Finally, because of its simplicity, the algorithm's behavior can be readily characterized analytically in some cases, conclusively demonstrating its asymptotic performance behavior in those cases.
Specifically the following two sections briefly review the ingredients of quantum programs and the satisfiability problem. The quantum algorithm for a particularly simple case is described in §4 and generalized in §5. The new algorithm is then evaluated for a variety of highly constrained problems. Finally some open issues are discussed, including a variety of ways this approach can be extended.