$\epsilon$-Uniform Mixing in Discrete Quantum Walks

Abstract

We study whether the probability distribution of a discrete quantum walk can get arbitrarily close to uniform, given that the walk starts with a uniform superposition of the outgoing arcs of some vertex. We establish a characterization of this phenomenon on regular non-bipartite graphs in terms of their adjacency eigenvalues and eigenprojections. Using theory from association schemes, we show this phenomenon happens on a strongly regular graph $X$ if and only if $X$ or $\overline{X}$ has parameters $(4m^2,2m^2\pm m,m^2\pm m,m^2\pm m)$ where $m\ge 2$.