Spatial search on a two-dimensional lattice with long-range interactions

Quantum-walk-based algorithms that search a marked location among $N$ locations on a $d$-dimensional lattice succeeds in time $O\left(\sqrt{N}\right)$ for $d>2$, while this is not found to be possible when $d=2$. In this paper, we consider a spatial search algorithm using continuous-time quantum walk on a two-dimensional square lattice with the existence of additional long-range edges. We examined such a search on a probabilistic graph model where an edge connecting non-nearest-neighbor lattice points $i$ and $j$ apart by a distance $|i-j|$ is added by probability $p_{ij}={|i-j|}^{-\alpha }(\alpha \ge 0)$. Through numerical analysis, we found that the search succeeds in time $O\left(\sqrt{N}\right)$ when $\alpha \le {\alpha }_c=2.4\pm 0.1$. For $\alpha >2$, the expectation value of the additional long-range edges on each node scales as a constant when $N\to \infty$, which means that search time of $O\left(\sqrt{N}\right)$ is achieved on a graph with average degree scaling as a constant.

Figure 1

Schematic representation of adding long-range edges on the two-dimensional square lattice. An edge is added between nodes $i$ and $j$ by probability $p_{ij}={|i-j|}^{-\alpha }$, which is a power-law decaying function depending on the Euclidean distance between the nodes.

Figure 2

Energy gap, success probability, and squared overlaps for a long-range percolation graph with $N=1024$ and $\alpha =2$. The squared overlaps of $|s\rangle$ with the eigenstates of $H$ satisfy $|\langle s|{\psi }_0\rangle {|}^2+{\left|\langle s|{\psi }_1\rangle \right|}^2\simeq 1$ for the entire range of $\gamma$. In the vicinity where the energy gap $E_1-E_0$ takes the minimum, the success probability $|\langle w|exp[-iH\pi /(E_1-E_0)]{|s\rangle |}^2$ takes a peak value. We evaluate the algorithm by using this peak value as the success probability, and use the energy gap at this point to calculate the evolution time.

Figure 3

The $\alpha$ dependence of (a) the success probability $P$ and (b) the normalized energy gap $\mathrm{\Delta }E\sqrt{N}/2$ on the $d=2$ LRP graph with various sizes from $N=64$ to $N=1024$. The data points represent the averaged values of 200 samples, while error bars are not shown for the visibility of the plots. The curves intersect at $\alpha \approx 2.4$ for both figures.

Figure 4

The $\alpha$ dependence of (a) the success probability $P$ (b) energy gap $\mathrm{\Delta }E$, and (c) total search time $T=\pi /\mathrm{\Delta }EP$ on the $d=2$ LRP graph with size $N=1024$. The data points were obtained by averaging 200 samples. The error bars represent the standard deviation of each quantity. This fluctuation comes from the randomness and inhomogeneity of the graph. For each figure, the red solid horizontal line represents the value for the complete graph, and the blue dashed horizontal line represents the value for the $d=2$ square lattice. Note that only the nearest-neighbor edges are generated in the limit of $\alpha \to \infty$, resulting in a square lattice. Therefore, each quantity asymptotically reaches the blue dashed line as $\alpha \to \infty$.

Figure 5

The $\alpha$ dependence of (a) the success probability $P$ and (b) the normalized energy gap $\mathrm{\Delta }E\sqrt{N}/2$ on the $d=1$ LRP graph with various sizes from $N=144$ to $N=1600$. The steeper curves correspond to larger $N$. The data points represent the averaged values of 200 samples, while error bars represent the standard errors. The curves intersect at around $\alpha \approx 1.3$ for both figures.

Figure 6

Verification of the finite size scaling method applied to the behavior of the search time on the $d=2$ LRP graph. Success probability $P$ (a) and normalized energy gap $\mathrm{\Delta }E\sqrt{N}/2$ (b) are plotted as a function of $(\alpha -{\alpha }_c)N^{1/\nu }$, with ${\alpha }_c=2.4$ and $\nu =3.2$. Standard errors of the data are smaller than the symbols. Focusing on the vicinity of ${\alpha }_c$ [i.e., vicinity of $(\alpha -{\alpha }_c)N^{1/\nu }=0]$, the plots with different $N$ collapse into a single curve.