Exploiting the deep structure of constraint satisfaction problems with quantum computers
Tad Hogg · National Conference on Artificial Intelligence · 1997
The deep structure of constraint satisfaction problems explains the association of hard search instances with a phase transition in problem solubility. This structure is also the basis of a quantum search algoritbm exhibiting the phase transition. In this paper, this algoritbm is modified to incorporate additional problem structure. This modification is an example of a general method for including heuristics in quantum search. The new algoritbm is evaluated empirically for random 3SAT, illustrating how quantum searches can benefit from using problem structure, on average.