Mixing of quantum walk on circulant bunkbeds
This paper gives new observations on the mixing dynamics of a continuous-time quantum walk on circulants and their bunkbeds. These bunkbeds are defined through two standard graph operators: the join G + H and the Cartesian product G x H of graphs G and H. Our results include the following: (i) The quantum walk is average uniform mixing on circulants with bounded eigenvalue multiplicity; this extends a known fact about the cycles C-n. (ii) Explicit analysis of the probability distribution of the quantum walk on the join of circulants; this explains why complete multipartite graphs are not average uniform mixing, using the fact K-n = K-1 + Kn-1 and K-n,K-...n = (K) over bar (n) +... + (K) over bar (n). (iii) The quantum walk on the Cartesian product of a m-vertex path P-m and a circulant G, namely, P-m x G, is average uniform mixing if G is; this highlights a difference between circulants and the hypercubes Q(n) = P-2 x Q(n-1). Our proofs employ purely elementary arguments based on the spectra of the graphs.
mixing quantum walks circulants continuous-time