Metraipolis › archive › dc_f971220d5bbc

Quantum Fourier transform for the symmetric group — arXiv:2608.28569

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.28569
License (as archived)
CC0-1.0
Archived
2026-10-17T11:58:32.292Z
SHA-256 of the archived text
4852a7fdae67f62c9e31ac7ce8b05a6ba088c5f3f5eb5a8d5ec76fc66a886b47
Stable URL of this page
https://metraipolis.com/documento/dc_f971220d5bbc

How to cite

Quantum Fourier transform for the symmetric group — arXiv:2608.28569 — arXiv (en), https://arxiv.org/abs/2608.28569 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f971220d5bbc (Metraipolis archive dc_f971220d5bbc, sha256 4852a7fdae67f62c9e31ac7ce8b05a6ba088c5f3f5eb5a8d5ec76fc66a886b47)
BibTeX
@misc{dcf971220d5bbc,
  title = {Quantum Fourier transform for the symmetric group — arXiv:2608.28569},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.28569},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f971220d5bbc; sha256 4852a7fdae67f62c9e31ac7ce8b05a6ba088c5f3f5eb5a8d5ec76fc66a886b47},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28569. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Quantum Fourier transforms (QFT) for general groups were recognized to be fundamental already early in the field. A canonical example of non-abelian QFT for the symmetric group was outlined by Beals (1997). Later, a more detailed analysis of this algorithm was carried out by Kawano and Sekigawa (2016). In this paper, we revisit that construction. After a careful analysis, we revise their gate complexity to $\widetilde{\mathcal{O}}(n^{3.5})$ and circuit depth to $\widetilde{\mathcal{O}}(n^3)$. Moreover, we observe that their construction is not optimal in the choice of transversal elements, so we propose simpler realization of the symmetric group QFT.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-08-31 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph) ; Representation Theory (math.RT).
Pagina del lavoro: https://arxiv.org/abs/2608.28569 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T11:28:37.536Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).