Abstract
It is well-known that classical random walks on regular graphs converge to the uniform distribution. Quantum walks, in their various forms, are quantization's of their corresponding classical random walk processes. Gerhardt and Watrous (2003) demonstrated that continuous-time quantum walks do not converge to the uniform distribution on certain Cayley graphs of the Symmetric group, which by definition are all regular. In this paper, we demonstrate that discrete-time quantum walks, in the sense of quantized Markov chains as introduced by Szegedy (2004), also do not converge to the uniform distribution. We analyze the spectra of the Szegedy walk operators using the representation theory of the symmetric group. In the discrete setting, the analysis is complicated by the fact that we work within a Hilbert space of a higher dimension than the continuous case, spanned by pairs of vertices. Our techniques are general, and we believe they can be applied to derive similar analytical results for other non-commutative groups using the characters of their irreducible representation.
Recommended Citation
A. Banerjee, "Non-uniform Mixing of Quantum Walks on the Symmetric Group," Linear Algebra and Its Applications, vol. 742, pp. 37 - 65, Elsevier, Aug 2026.
The definitive version is available at https://doi.org/10.1016/j.laa.2026.04.006
Department(s)
Computer Science
Publication Status
Full Text Access
Keywords and Phrases
Non-commutative Fourier analysis; Quantum walks; Symmetric group
International Standard Serial Number (ISSN)
0024-3795
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2026 Elsevier, All rights reserved.
Publication Date
01 Aug 2026
