Speaker
Description
Spatial searches by continuous-time quantum walks have been rigorously studied on lattices with nearest-neighbor hopping, in which search capabilities worsen with decreasing lattice dimension when $d\leq4$. With the addition of long-range hopping, where the hopping rate $\tau$ decays as a power-law with the inter-site distance $\tau\sim\ell^{-\alpha}$, we can avert this deterioration in performance. More precisely, we recover $\mathcal{O}(\sqrt{N})$ runtimes for quantum spatial search conducted on low-dimensional cubic lattices of $N$ sites. This is established via an asymptotic analysis of the spectral gap of the lattice's associated discrete Laplacian. The asymptotics also shed light on the interplay between the lattice's Euclidean dimension $d$ and the long-range hopping exponent $\alpha$, requiring $\alpha<3d/2$, $d\in[1,4]$, for high-fidelity searches in $\mathcal{O}(\sqrt{N})$ runtime. Extending the study to also include Euclidean dimensions $d>4$, we establish that the spectral dimension $d_s$ must satisfy the constraint $d_s>4$ to achieve optimal search. Moreover, the spectral dimension $d_s$ relies on the Laplacian's spectral density and does not uniquely define the underlying lattice structure, thereby providing a promising metric to understand the complexity class of quantum search algorithms on different graph architectures.
