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

National Conference on Artificial IntelligenceJul 27, 19971 citation

Nested quantum search and structured problems

Nicolas J. Cerf, Lov K. Grover, Colin P. Williams

A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $\sqrt{d},$ where d is the dimension of the search space, whereas any classical algorithm necessarily scales as $O(d).$ It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $\sqrt{d},$ where d is the dimension of the search space, whereas any classical algorithm necessarily scales as $O(d).$ It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.

arXiv:quant-ph/9806078Physical Review AFeb 9, 2000104 citations

A framework for structured quantum search

Tad Hogg

arXiv:quant-ph/9701013Physica D Nonlinear PhenomenaSep 1, 199823 citations

A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order

\sqrt{d},

where d is the dimension of the search space, whereas any classical algorithm necessarily scales as

O(d).

It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.