Quantum computation of Fourier transforms over symmetric groups

Abstract

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 macline 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 IGI), 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.