For every quantum walk there is a (classical) lifted Markov chain with the same mixing time. (arXiv:1712.02318v1 [quant-ph])

Quantum walks on graphs have been shown in certain cases to mix quadratically
faster than their classical counterparts. Lifted Markov chains, consisting of a
Markov chain on an extended state space which is projected back down to the
original state space, also show considerable speedups in mixing time. Here, we
construct a lifted Markov chain on a graph with $n^2 T^3$ vertices that mixes
to the average mixing distribution of a quantum walk on any graph with $n$
vertices over $T$ timesteps. Moreover, we prove that the mixing time of this
chain is $T$, the number of timesteps in the quantum walk. As an immediate
consequence, for every quantum walk there is a lifted Markov chain with the
same mixing time. The result is based on a lifting presented by Apers, Ticozzi
and Sarlette (arXiv:1705.08253).

Article web page: