Non-uniform mixing of quantum walk on cycles

A classical lazy random walk on cycles is known to mix with the uniform distribution. In contrast, we show that a continuous-time quantum walk on cycles exhibits strong non-uniform mixing properties. First, we prove that the instantaneous distribution of a quantum walk on most even-length cycles is never uniform. More specifically, we prove that a quantum walk on a cycle C-n is not instantaneous uniform mixing, whenever n satisfies either: (a) n = 2(u), for u >= 3; or (b) n = 2(u)q, for u >= 1 and q equivalent to 3 (mod4). Second, we prove that the average distribution of a quantum walk on any Abelian circulant graph is never uniform. As a corollary, the average distribution of a quantum walk on any standard circulant graph, such as the cycles, complete graphs, and even hypercubes, is never uniform. Nevertheless, we show that the average distribution of a quantum walk on the cycle C-n is O(1/ n)-uniform.