Problem of the Week
Hilton Memorial Lecture
Given a simple, undirected, regular graph G = (V, E) with adjacency matrix A, a continuous-time quantum walk on G is given by vt = exp(−iAt) v0 , where v0 is a unit |V|-dimensional vector. The probability distribution induced by such a walk at time t on vertex u is pu(t) = |vt[u]|2. A quantum walk on G is called “uniform mixing” if there is a time t* such that pu(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.