Nested quantum search and structured problems - art. no. 032303

A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order root d, where d is the dimension of the sea rch space, whereas any classical algorithm necessarily scales as O(d). It i s shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum sear ch within another. The average number of iterations required to find the so lution of a typical hard instance of a constraint satisfaction problem is f ound to scale as root d(alpha), with the constant alpha<1 depending on the nesting depth and the type of problem considered. This corresponds to a squ are-root speedup over a classical nested search algorithm, of which our alg orithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, al pha is estimated to be around 0.62.