Using quantum walks to unitarily represent random walks on finite graphs

Quantum and random walks have been shown to be equivalent in the following sense: a time-dependent random walk can be constructed such that its vertex distribution at all time instants is identical to the vertex distribution of any discrete-time coined quantum walk on a finite graph. This equivalence establishes a deep connection between the two processes, far stronger than simply considering quantum walks as quantum analogs of classical random walks. The present paper strengthens this connection by providing a construction that establishes this equivalence in the reverse direction: a unitary time-dependent quantum walk can be constructed such that its vertex distribution is identical to the vertex distribution of any random walk on a finite graph at all time instants. The construction shown here describes a quantum walk that matches a random walk without measurements at all time steps (an otherwise trivial statement): measurement is performed in a quantum walk that evolved unitarily until a given time $t$ such that its vertex distribution is identical to the random walk at time $t$. The construction procedure is general, covering both homogeneous and nonhomogeneous random walks. For homogeneous random walks, unitary evolution implies time dependency for the quantum walk, since homogeneous quantum walks do not converge under arbitrary initial conditions, while a broad class of random walks does. Thus, the absence of convergence demonstrated for a quantum walk in its debut comes from both time homogeneity and unitarity, rather than unitarity alone, and our results shed light on the power of quantum walks to generate samples for arbitrary probability distributions. Finally, the construction here proposed is used to simulate quantum walks that match uniform random walks on the cycle and the torus.

Figure 1

Visual depiction of auxiliary functions $\eta$ and $\sigma$. $\eta$ gives an ordering for the neighbors of $v$ such that, in this case, $\eta (v,c)=u$. $\sigma$ maps the state $|v,c\rangle \left[\mathrm{edge}\right(v,u\left)\right]$ to the state $|u,\sigma (v,u)\rangle \left[\mathrm{edge}(u,u^{\prime })\right]$. The inverse association ${\sigma }^{-1}$ connects the state $|u,\sigma (v,u)\rangle \left[\mathrm{edge}(u,u^{\prime })\right]$ with state $|v,c\rangle \left[\mathrm{edge}\right(v,u\left)\right]$.

Figure 2

TVD with stationary distribution at step multiples of 15 for the cycle and torus graphs ($n=121$ in both cases). Ground-truth curves show the TVD between the random-walk vertex probability distribution $\pi \left(t\right)$ and the stationary distribution ${\pi }^{*}$, which is the uniform distribution for both graphs. Other curves show the TVD between ${\mathcal{V}}_t^k$ and ${\pi }^{*}$ for $k\in \{{10}^2,{10}^3,{10}^5\}$.

Figure 3

Probability distribution of the time-dependent quantum walk, $\mu (·,t)$, for the cycle with $\left|V\right|=121$ vertices at times $t\in \left\{2\right|V|,4|V|,8|V|,16|V\left|\right\}$ and its stationary distribution (uniform). The initial condition $\pi \left(0\right)$ used is the delta function at the vertex labeled 60. For clarity, we omit $\mu (·,t)$ for vertices $v$ with $\mu (v,t)\le {10}^{-4}$.