Mixing in Continuous Quantum Walks on Graphs
arXiv:quant-ph/0209106
Abstract
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.
8 pages, no figures
References in corpus (7)
- Quantum Computation and Decision Trees
- Exponential algorithmic speedup by quantum walk
- An example of the difference between quantum and classical random walks
- Quantum random walks in optical lattices
- Experimental Implementation of the Quantum Random-Walk Algorithm
- Decoherence can be useful in quantum walks
- Quantum Random Walks Hit Exponentially Faster