Simulation of quantum walks and fast mixing with classical processes

We compare discrete-time quantum walks on graphs to their natural classical equivalents, which we argue are lifted Markov chains (LMCs), that is, classical Markov chains with added memory. We show that LMCs can simulate the mixing behavior of any quantum walk, under a commonly satisfied invariance condition. This allows us to answer an open question on how the graph topology ultimately bounds a quantum walk's mixing performance, and that of any stochastic local evolution. The results highlight that speedups in mixing and transport phenomena are not necessarily diagnostic of quantum effects, although superdiffusive spreading is more prominent with quantum walks. The general simulating LMC construction may lead to large memory, yet we show that for the main graphs under study (i.e., lattices) this memory can be brought down to the same size employed in the quantum walks proposed in the literature.

Figure 1

Left: Random walk ${\mathbf{P}}_0$ on the cycle. Right: Unitary quantum walk with coin toss $\mathbf{C}$, or lifted Markov chain with a stochastic coin toss $\overline{\mathbf{C}}$, suggesting their comparison.

Figure 2

Depiction of the LMC construction for $T=2$. (a) For each node $v$ we construct a stochastic bridge $\left\{{\mathbf{P}}_t^{\left(v\right)}\right\}$ that tracks the $p_t$ induced by the QW starting on node $v$. (b) Each of these bridges is implemented as a time-invariant LMC on $T+1$ copies of $\mathcal{G}$. These LMCs are combined into a final LMC, such that the QW starting from a general initial distribution on $\mathcal{V}$ is simulated with the initialization $\mathbf{F}$, over $T$ steps. The dashed lines represent the “amplification” edges added in the last step of the construction to pursue the LMC evolution for $t>T$.

Figure 3

Capacitated network construction used in Lemma 1.