Universal mixing of quantum walk on graphs

摘要: We study the set of probability distributions visited by a continuous-time quantum walk on graphs. An edge-weighted graph G is universal mixing if instantaneous or average distribution ranges over all vertices as weights are varied non-negative reals. The uniform it visits distribution. Our results include following: • All weighted complete multipartite graphs mixing. This in contrast to fact that no unweighted (except for four-cycle K2,2). For n ≥ 1, claw K1,n minimally connected graph. In fact, corollary, adds new family list so far contains only hypercubes. Any almost-uniform unless its spectral type sublinear size provides nearly tight characterization circulant No shows do not help achieve mixing, unlike case. proofs exploit spectra underlying and path collapsing arguments.