Abstract
A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order where d is the dimension of the search space, whereas any classical algorithm necessarily scales as 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 with the constant 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, is estimated to be around 0.62.
- Received 31 July 1998
DOI:https://doi.org/10.1103/PhysRevA.61.032303
©2000 American Physical Society