Non-uniform mixing of quantum walks on the symmetric group
Linear Algebra and its Applications · 2026-08 · 742 · 37-65
DOI: 10.1016/j.laa.2026.04.006 ↗Kurz gefasst
Fachartikel in der Zeitschrift Linear Algebra and its Applications, 2026-08. Verfasst von Avah Banerjee. Die Arbeit nennt 39 Literaturangaben. Gefördert von: National Science Foundation, National Science Foundation Directorate for Computer and Information Science and Engineering.
Abstract (Originalsprache)
It is well-known that classical random walks on regular graphs converge to the uniform distribution. Quantum walks, in their various forms, are quantizations 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.
Förderung
- National Science Foundation
- National Science Foundation Directorate for Computer and Information Science and Engineering
Zitieren
APA
Banerjee, A. (2026). Non-uniform mixing of quantum walks on the symmetric group. Linear Algebra and its Applications, 742, 37-65. https://doi.org/10.1016/j.laa.2026.04.006
Vancouver
Banerjee A. Non-uniform mixing of quantum walks on the symmetric group. Linear Algebra and its Applications. 2026;742:37-65. doi:10.1016/j.laa.2026.04.006
BibTeX
@article{Banerjee2026,
author = {Banerjee, Avah},
title = {Non-uniform mixing of quantum walks on the symmetric group},
journal = {Linear Algebra and its Applications},
year = {2026},
volume = {742},
pages = {37--65},
doi = {10.1016/j.laa.2026.04.006}
}
EUVIMED