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

Danial Dervovic

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 ext…