2002/09/30 by Amir Ahmadi, Ryan Belk, Christino Tamon +1 · 1 citation
Physics and Astronomy · #quant-ph
published as Quantum Information and Computation 3 (2003), 611-618. · 8 pages, no figures
arxiv created 2003/04/16 · arxiv updated 2009/12/01
Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that a continuous quantum walk on the hypercube is instantaneously uniform mixing. We show that the continuous-time quantum walks on other well-behaved graphs do not exhibit this uniform mixing. We prove that the only graphs amongst balanced complete multipartite graphs that have the instantaneous uniform mixing property are the complete graphs on two, three and four vertices, and the cycle graph on four vertices. Our proof exploits the circulant structure of these graphs. Furthermore, we conjecture that most complete cycles and Cayley graphs lack this mixing property as well.