On the Relation between Random Walks and Quantum Walks

Stefan Boettcher, Stefan Falkner, Renato Portugal

Published 2014-10-26Version 1

We propose a general relation between the walk dimensions $d_{w}$ of random walks and quantum walks, which illuminates fundamental aspects of the walk dynamics, such as its mean-square displacement. To this end, 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 the variable $x^{d_{w}}/t$. In all cases studied, we find that $d_{w}$ of the discrete-time quantum walk with the Grover coin takes on exactly half the value found for the random walk on the same geometry, irrespective of whether it is a homogeneous lattice or a heterogeneous network. We demonstrate this circumstance for several networks with distinct properties using exact RG and confirm the collapse in each case with extensive numerical simulation.