Given a simple, undirected, regular graph G = (V, E) with adjacency matrix A, a continuous-time quantum walk on G is given by v_t = exp(−iAt) v₀ , where v₀ is a unit |V|-dimensional vector. The probability distribution induced by such a walk at time t on vertex u is p_u(t) = |v_t[u]|². A quantum walk on G is called “uniform mixing” if there is a time t* such that p_u(t*) = 1/|V| for all u in V.

Classical random walks on well-behaved graphs are known to mix to the uniform distribution. But this is a property not shared by most quantum walks. This talk describes counter-intuitive differences in mixing phenomena between classical and quantum walks on graphs.