Many algorithmic developments in quantum complexity theory, including Shor's celebrated algorithms for factoring and discrete logs, have made use of Fourier transforms over abelian groups. That is, at some point in the computation, the machine is in a superposition of states corresponding to elements of a finite abelian group G, and in quantum polynomial time (i.e., polynomial in log |G|), the machine is transformed according to the Fourier transform to a superposition of states corresponding to the irreducible representations of G. We give a quantum polynomial time algorithm for the Fourier transform for the symmetric groups Sn, adapting results obtained by Clausen and Diaconis-Rockmore to the quantum setting.
|Original language||English (US)|
|Number of pages||6|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - Jan 1 1997|
|Event||Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA|
Duration: May 4 1997 → May 6 1997
All Science Journal Classification (ASJC) codes