This paper improves the main result in our paper "Quantum Fourier Transform over Symmetric Groups, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 227--234, Northeastern University, Boston, USA (June 26-29, 2013)." In that paper, we presented an O(n4) quantum Fourier transform (QFT) algorithm over symmetric group Sn, which was faster than the existing algorithm. This paper proposes an O(n3 log n) QFT algorithm over Sn by relieving bottlenecks of our previous algorithm.This paper improves the main result in our paper "Quantum Fourier Transform over Symmetric Groups, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 227--234, Northeastern University, Boston, USA (June 26-29, 2013)." In that paper, we presented an O(n4) quantum Fourier transform (QFT) algorithm over symmetric group Sn, which was faster than the existing algorithm. This paper proposes an O(n3 log n) QFT algorithm over Sn by relieving bottlenecks of our previous algorithm.

ACM communications in computer algebraFeb 5, 20152 citations

The Quantum Fourier Transform and Its Applications

WORLD SCIENTIFIC eBooksAug 27, 20260 citations

Quantum Fourier transform for the symmetric group

Carli Bruinsma, Dmitry Grinko, Maris Ozols

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.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.

quant-pharXiv:2608.28569Aug 31, 20260 citations

Quantum Fourier Transform and Its Applications

Weng-Long Chang, Athanasios V. Vasilakos

Studies in big dataDec 21, 20202 citations

\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.