Von N^2 nach log^2 N – Zur algebraischen Berechnungskomplexität allgemeiner Fouriertransformationen (in German)
- Bjorn Grohmann ,
- Martin Roetteler
Proceedings GI Jahrestagung 1999 (Paderborn) |
Published by Springer Berlin Heidelberg
We present an overview of methods to compute general Fourier transforms on various computational models. A realization of the transformation ADFT(N) using O(N) arithmetic operations is derived. Furthermore an example for a non-abelian Fourier transform on a quantum computer is discussed.