Nested quantum search and structured problems

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\left(d\right).$ 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^{\alpha }},$ with the constant $\alpha <1\mathrm{}$ 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, $\alpha$ is estimated to be around 0.62.