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 √N×√N. The previous quantum-walk based algorithms take O(√N ln N) 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(√N ln N) steps, thus giving an O(√ln N) improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.