  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 D(G)$ vertices that mixes
exactly to the average mixing distribution of a quantum walk on the graph $G$
with $n$ vertices, where $D(G)$ is the diameter of $G$. Moreover, the mixing
time of this chain is $D(G)$ timesteps, and we prove that computing the
transition probabilities for the lifted chain takes time polynomial in $n$. As
an immediate consequence, for every quantum walk there is a lifted Markov chain
with a faster mixing time that is polynomial-time computable, as the quantum
mixing time is trivially lower bounded by the graph diameter. The result is
based on a lifting presented by Apers, Ticozzi and Sarlette (arXiv:1705.08253).
