Quantum walks on random lattices: Diffusion, localization and the absence of parametric quantum speed-up

Abstract

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 speed-up 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 pre-diffusive and diffusive behaviors at different time scales. Importantly, we show that even arbitrarily weak concentrations of randomly removed lattice sites give rise to a complete breakdown of the superdiffusive quantum speed-up, 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 speed-up implies dramatic limitations for quantum information applications of quantum walks on random geometries and graphs.

6+4 pages, 5+3 figures

References in corpus (21)

• Anderson Transitions
• Universal computation by quantum walk
• Spatial search by quantum walk
• Quantum Walk in Position Space with Single Optically Trapped Atoms
• Exploring Topological Phases With Quantum Walks
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• Destruction of Anderson localization by a weak nonlinearity
• Discrete single-photon quantum walks with tunable decoherence
• Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
• Decoherence in quantum walks - a review
• Symmetries, Topological Phases and Bound States in the One-Dimensional Quantum Walk
• Spatial search and the Dirac equation
• Non-Hermitian Edge Burst
• A random walk approach to quantum algorithms
• Quantum walks with random phase shifts
• Anderson localization in generalized discrete time quantum walks
• Asymptotic dynamics of coined quantum walks on percolation graphs
• Coined quantum walks on percolation graphs
• Discrete time quantum walks on percolation graphs
• Topological spin texture of chiral edge states in photonic two-dimensional quantum walks
• Localization and Fractality in Inhomogeneous Quantum Walks with Self-Duality

Cited by in corpus (6)

• Coined quantum walks on the line: Disorder, entanglement, and localization
• Localization of quantum walk with classical randomness: Comparison between manual methods and supervised machine learning
• Clustering-induced localization of quantum walks on networks
• Repeated measurements and random scattering in quantum walks
• Dissipation in fermionic two-body continuous-time quantum walk under the steepest entropy ascent formalism
• Two-particle Hadamard walk on dynamically percolated line and circle