Mixing of Quantum Walk on Circulant Bunkbeds

P. Lo, S. Rajaram, D. Schepens, D. Sullivan, C. Tamon, J. Ward

Published 2005-09-08Version 1

We give new observations on the mixing dynamics of a continuous-time quantum walk on circulants and their bunkbed extensions. These bunkbeds are defined through two standard graph operators: the join G + H and the Cartesian product of graphs G and H.Our results include the following: 1. The quantum walk is average uniform mixing on circulants with bounded eigenvalue multiplicity. This extends a known fact about the cycles. 2. Explicit analysis of the probability distribution of the quantum walk on the join of circulants. This explains why complete partite graphs are not average uniform mixing, using the fact the complete n-vertex graph is the join of a 1-vertex graph and the (n-1)-vertex complete graph, and that the complete m-partite graph, where each partition has size n, is the m-fold join of the empty n-vertex graph. 3. The quantum walk on the Cartesian product of a m-vertex path P and a circulant G, is average uniform mixing if G is. This highlights a difference between circulants and the hypercubes. Our proofs employ purely elementary arguments based on the spectra of the graphs.