For every quantum walk there is a (classical) lifted Markov chain with faster mixing time

Abstract

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).