Quantum Fourier transform over symmetric groups — improved result

This paper describes the fastest quantum algorithm at this moment for the quantum Fourier transform (QFT) over symmetric groups. We provide a new FFT (classical) algorithm over symmetric groups and then transform it to a quantum algorithm. The complexity of our QFT algorithm is O(n3log⁡n)O(n3log⁡n), faster than the existing O(n4log⁡n)O(n4log⁡n) QFT algorithm. In addition, we show that the algorithm can be performed in O(n3)O(n3) if the use of threshold gates is allowed.