Quantum vs. classical walks with memory two

Quantum walks is an emerging field in quantum computing. It is expected to become the next most effective tool in speeding up quantum algorithms, possibly achieving the similar gain in speed as was the case with Gibbs sampling in classical computing. There already exist examples of super-exponential speed up using only quantum walks. Markov chains, or random walks on graphs, have many uses in physics; and walks with memory are standard models for a number of phenomena. We study persistent quantum walks, and compare them with equivalent classical Markov processes. The first question to ask is how the mixing time compares between persistent quantum and classical walks. Since quantum walks are generated by unitary matrices, they do not converge to a stationary state. The mixing time is then naturally introduced via a limiting distribution defined as the average of the probability distributions over time (Cesaro sum). We compare the mixing times, along with other properties, using numerical methods and spectral analysis. Our preliminary results indicate a significant speedup in some cases, and a number of other interesting aspects of quantum walks.