Continuous Time Quantum Walks in finite Dimensions

Continuous time quantum walk (CTQW) provides optimal quadratic speedup for spatial search on complete graphs, hypercubes, and connected random graphs compared to classical algorithms. Instead of these high dimensional graphs, we consider the performance of CTQW on the finite dimensional Migdal-Kadanoff lattices. We relate the critical point for the walk Hamiltonian to the lattice Laplacian. Using renormalization group analysis\footnote{Boettcher, Stefan, and Shanshan Li, Journal of Physics A 48, 415001 (2015)}, we calculate the critical point and derive the search performance on instances of different spectral dimension. For those with integer dimension, we reproduce the known algorithmic efficiency on regular lattices. In particular, we show that on these finite dimensional graphs, the algorithmic efficiency of quantum walk is entirely determined by the spectral dimension of the Laplacian. Quadratic speedup can only be achieved when the spectral dimension is larger than four.