Faster quantum-walk algorithm for the two-dimensional spatial search

We consider the problem of finding a desired item out of $N$ items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\times \sqrt{N}$. The previous quantum-walk based algorithms take $O\left(\sqrt{N}\text{ln}N\right)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in $O\left(\sqrt{N\text{ln}N}\right)$ steps, thus giving an $O\left(\sqrt{\text{ln}N}\right)$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.

Figure 1

Circuit diagram for the controlled quantum-walk search algorithm. The reflect and walk boxes denote the reflection operator ${\overline{R}}_{uc,m}$ and the walk operator $W$, respectively, as defined in the text.