Uniform mixing on abelian Cayley graphs

Xiwang Cao, Keqin Feng

Published 2019-11-18Version 1

In the past few decades, quantum algorithms have become a popular research area of both mathematicians and engineers. In 2003, Childs et al. found a graph in which the continuous-time quantum walk spreads exponentially faster than any classical algorithm for a certain black-box problem. Since then, there are extensive explorations on quantum walks on graphs. Among them, uniform mixing provides a uniform probability distribution of information over time which attracts a special attention. However, there are only a few known examples of graphs which admit uniform mixing. In this paper, we give a characterization of abelian Cayley graphs having uniform mixing. Some concrete constructions of such graphs are provided. Particularly, for cubelike graphs, it is shown that the Cayley graph ${\rm Cay}(\mathbb{F}_2^{2k};S)$ having uniform mixing if and only if $f$ is a bent function, where $f$ is the characteristic function of $S$.