PreprintarXiv licencearXiv
Quantum Fourier transform for the symmetric group
Abstract
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 𝒪̃(n3.5) and circuit depth to 𝒪̃(n3). 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.
Related
- Mathematical foundation of symmetric fast Fourier transform
- Characterization of the group Fourier transform of Hilbert space Valued functions
- Differentiation and Shift Property Characterisations of the Group Fourier Transform on the Heisenberg Group
- Some Characterisations of the Strichartz Fourier Transform on the Heisenberg Group
- Contour-integral and Fourier transform based multivariable quantum eigenvalue transformation for commuting matrices
BibTeX
@misc{bruinsma2026quantum,
title = {{Quantum Fourier transform for the symmetric group}},
author = {Carli Bruinsma and Dmitry Grinko and Maris Ozols},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.28569},
eprint = {2608.28569},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28569},
}
RIS
TY - UNPB
TI - Quantum Fourier transform for the symmetric group
AU - Carli Bruinsma
AU - Dmitry Grinko
AU - Maris Ozols
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2608.28569
UR - https://arxiv.org/abs/2608.28569
AB - 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 𝒪̃(n^3.5) and circuit depth to 𝒪̃(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.
ER -