Quantum walks on random lattices: Diffusion, localization, and the absence of parametric quantum speedup

Discrete-time quantum walks, quantum generalizations of classical random walks, provide a framework for quantum information processing, quantum algorithms, and quantum simulation of condensed-matter systems. The key property of quantum walks, which lies at the heart of their quantum information applications, is the possibility for a parametric quantum speedup in propagation compared to classical random walks. In this work we study propagation of quantum walks on percolation-generated two-dimensional random lattices. In large-scale simulations of topological and trivial split-step walks, we identify distinct prediffusive and diffusive behaviors at different timescales. Importantly, we show that even arbitrarily weak concentrations of randomly removed lattice sites give rise to a complete breakdown of the superdiffusive quantum speedup, reducing the motion to ordinary diffusion. By increasing the randomness, quantum walks eventually stop spreading due to Anderson localization. Near the localization threshold, we find that the quantum walks become subdiffusive. The fragility of quantum speedup implies dramatic limitations for quantum information applications of quantum walks on random geometries and graphs.