Relation between Random Walks and Quantum Walks

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 ρ(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 ρ(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.