Spatial search by quantum walk

TLDR

Grover's quantum search algorithm accelerates combinatorial search but does not directly apply to searching a physical database laid out in space. The authors propose a continuous‑time quantum‑walk algorithm on a graph as an alternative search method. They demonstrate that this quantum‑walk search achieves the optimal √N speedup on d‑dimensional periodic lattices for d>4, requires √N polylog N time in d=4, and offers no substantial speedup for d<4, thereby extending earlier results for complete graphs, hypercubes, and the Aaronson–Ambainis spatial‑database bounds.

Abstract

Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of $N$ items laid out in $d$ spatial dimensions can be searched in time of order $\sqrt{N}$ for $d&gt;2$, and in time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$ for $d=2$. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that $\sqrt{N}$ speedup can also be achieved on the hypercube. We show that full $\sqrt{N}$ speedup can be achieved on a $d$-dimensional periodic lattice for $d&gt;4$. In $d=4$, the quantum walk search algorithm takes time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$, and in $d&lt;4$, the algorithm does not provide substantial speedup.