EUVIMEDEUVIMED entdecken
Crossref

Non-uniform mixing of quantum walks on the symmetric group

Avah Banerjee

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →