Spatial search via an interpolated memoryless walk

The defining feature of memoryless quantum walks is that they operate on the vertex space of a graph and therefore can be used to produce search algorithms with minimal memory. We present a memoryless walk that can find a unique marked vertex on a two-dimensional lattice. Our walk is based on the construction proposed by Falk, which tessellates the lattice with squares of size $2\times 2$. Our walk uses minimal memory, $O\left(\sqrt{NlogN}\right)$ applications of the walk operator, and outputs the marked vertex with vanishing error probability. To accomplish this, we apply a self-loop to the marked vertex—a technique we adapt from interpolated walks. We prove that with our explicit choice of self-loop weight, this forces the action of the walk asymptotically into a single rotational space. We characterize this space and as a result show that our memoryless walk produces the marked vertex with a success probability asymptotically approaching one.

Figure 1

Staggered tessellations of the two-dimensional lattice into squares of size $2\times 2$. The dashed red lines represent the states $|a_{ij}\rangle$ and solid blue lines represent the states $|b_{ij}\rangle$, as defined in (1) and (2). The construction based on alternating reflections about this tessellation structure was originally proposed in Ref. [20]