Relation between Random Walks and Quantum Walks

Abstract

Based on studies on four specific networks, we conjecture a general relation between the walk dimensions $d_w$ of discrete-time random walks and quantum walks with the (self-inverse) Grover coin. In each case, we find that $d_w$ of the quantum walk takes on exactly half the value found for the classical random walk on the same geometry. Since walks on homogeneous lattices satisfy this relation trivially, our results for heterogeneous networks suggests that such a relation holds irrespective of whether translational invariance is maintained or not. To develop our results, we extend the renormalization group analysis (RG) of the stochastic master equation to one with a unitary propagator. As in the classical case, the solution $\rho (x,t)$ in space and time of this quantum walk equation exhibits a scaling collapse for a variable $x^{d_w}/t$ in the weak limit, which defines $d_w$ and illuminates fundamental aspects of the walk dynamics, e.g., its mean-square displacement. We confirm the collapse for $\rho (x,t)$ in each case with extensive numerical simulation. The exact values for $d_w$ in themselves demonstrate that RG is a powerful complementary approach to study the asymptotics of quantum walks that weak-limit theorems have not been able to access, such as for systems lacking translational symmetries beyond simple trees.

8 pages, RevTex4-1; several corrections and upgrades; for related information, see http://www.physics.emory.edu/faculty/boettcher/

References in corpus (18)

• Quantum Mechanics helps in searching for a needle in a haystack
• Universal computation by quantum walk
• Quantum walks: a comprehensive review
• Spatial search by quantum walk
• Single-Spin Addressing in an Atomic Mott Insulator
• Two-particle bosonic-fermionic quantum walk via 3D integrated photonics
• From quantum cellular automata to quantum lattice gases
• Realization of quantum walks with negligible decoherence in waveguide lattices
• Anderson localization of entangled photons in an integrated quantum walk
• Universal computation by multi-particle quantum walk
• An example of the difference between quantum and classical random walks
• Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
• Weak limits for quantum random walks
• Quantum Google in a Complex Network
• Anomalous Diffusion on the Hanoi Networks
• One-Dimensional Coinless Quantum Walks
• Scaling of Clusters near Discontinuous Percolation Transitions in Hyperbolic Networks
• Renormalization and Scaling in Quantum Walks

Cited by in corpus (16)

• Dark states of quantum search cause imperfect detection
• The Chiral Potts Spin Glass in d=2 and 3 Dimensions
• The spectral dimension controls the decay of the quantum first detection probability
• Uncertainty and symmetry bounds for the quantum total detection probability
• Analysis of Coined Quantum Walks with Renormalization
• Phase Transitions between Different Spin-Glass Phases and between Different Chaoses in Quenched Random Chiral Systems
• Devil's Staircase Continuum in the Chiral Clock Spin Glass with Competing Ferromagnetic-Antiferromagnetic and Left-Right Chiral Interactions
• Stepwise Positional-Orientational Order and the Multicritical-Multistructural Global Phase Diagram of the s=3/2 Ising Model from Renormalization-Group Theory
• Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
• Transient temperature and mixing times of quantum walks on cycles
• Renormalization of the Unitary Evolution Equation for Coined Quantum Walks
• Driven Topological Systems in the Classical Limit
• On the equivalence between quantum and random walks on finite graphs
• Transport and Localization in Quantum Walks on a Random Hierarchy of Barriers
• Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity
• Renormalization of Discrete-Time Quantum Walks with non-Grover Coins