Discrete quantum walks on the symmetric group

Both the transient and limiting dynamical behavior of classical random walks on non-abelian groups have a well-developed theory utilizing non-commutative Fourier analysis. The success of the non-commutative Fourier transform in the analysis of such random walks lies in the fact that in the Fourier domain, the distribution for the next step can be determined by a multiplication instead of a convolution operation, and character theory can be used to find analytical formulas for the distribution. In this paper, we initiate a study of using non-commutative Fourier transform for expressing the dynamics of discrete quantum walks in non-abelian groups. More specifically, we investigate the discrete-time quantum walk model on Cayley graphs of the symmetric group. We present the following results: (1) An expression for the probability amplitude of the walker’s state using a recurrence relation in the Fourier domain; (2) A relationship between certain symmetries of the initial state, the generating set for the Cayley graph, and the state of the walker; (3) An expression for the probability amplitudes, derived for the Cayley graph with only two generators, based on a sequence that behaves like a 1D Walsh matrix.