Quantum computation of Fourier transforms over symmetric groups

Robert Beals

Research output: Contribution to journalConference articlepeer-review

81 Scopus citations

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 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 languageEnglish (US)
Pages (from-to)48-53
Number of pages6
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1997
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Quantum computation of Fourier transforms over symmetric groups'. Together they form a unique fingerprint.

Cite this