Quantum Walks on Trees with Disorder

Quantum walks on trees have the potential for exponential speedup compared to classical algorithms. It has been argued that disorder may limit this potential, due to Anderson localization. We report on an extensive numerical analysis of quantum walks with disorder and find evidence of a localization transition for large disorder, but a quantum-to-classical transition for intermediate disorder. These results suggest that quantum walks may yet retain their speedup for high-dimensional graphs with weak disorder.