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 ( n 3 log ? n ) , faster than the existing O(n4log?n) O ( n 4 log ? n ) QFT algorithm. In addition, we show that the algorithm can be performed in O(n3) O ( n 3 ) if the use of threshold gates is allowed.
quantum fourier transform symmetric group fast fourier transform representation theory non-abelian group