Deterministic spatial search using alternating quantum walks

This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\lceil \frac{\pi }{2\sqrt{2}}\sqrt{N}\rceil$ marked vertex phase shifts for an $N$-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.

Figure 1

The $n=5$ CIIN has a total of $N=2n=10$ vertices. The solid lines are the edges of the complete graph ${\mathbb{K}}_5$, while the dashed lines are the identity interconnections.

Figure 2

The weighted graph representing connectivity between the four vertex groups with respect to the marked vertex $|b_1\rangle =|\omega \rangle$.

Figure 3

Dynamics of the spatial search algorithm on a CIIN with $N=2048$ vertices, showing the rotation between $|b_3\rangle$ and the marked element $|b_1\rangle =|\omega \rangle$. Approximately 50% success probability is reached after evolution time $T=\frac{\pi }{2\sqrt{2}}\sqrt{N}\approx 50.3$.

Figure 4

Dynamics of a quantum walk on an 18-vertex CIIN, starting from the marked element. There is $2\pi$ periodicity, and for multiple values of $t$ the amplitude is suppressed in one or more vertex groups.

Figure 5

The state of a 2048-vertex CIIN after $p$ applications of $U$ to $|s\rangle$, shown in the dual basis.

Figure 6

Comparing the dynamics of the (a) approximate and (b) deterministic algorithms on a 24-vertex instance. The horizontal lines represent the evolution target of $|\langle \psi |b_1^{*}\rangle {|}^2=\frac{1}{n}$ (and $|\langle \psi |b_4^{*}\rangle {|}^2=\frac{n-1}{n}$). In the exact algorithm, the speed of evolution can be manipulated such that the target is reached exactly at $2p=4$, i.e., after two iterations of $U(-\theta )U\left(\theta \right)$.

Figure 7

The state of a 2050-vertex CIIN after $p$ applications of the alternate iterate $U_o$.

Figure 8

Quantum circuit for fast-forwarded gate-model simulation of quantum walk on a $2^{m+1}$-vertex CIIN.