Abstract
Two methods for fast Fourier transforms are used in a quantum context. The first method is for systems with dimension of the Hilbert space D=dⁿ with d an odd integer, and is inspired by the Cooley-Tukey formalism. The `large Fourier transform' is expressed as a sequence of n `small Fourier transforms' (together with some other transforms) in quantum systems with d-dimensional Hilbert space. Limitations of the method are discussed. In some special cases, the n Fourier transforms can be performed in parallel. The second method is for systems with dimension of the Hilbert space D=d₀...d_n-1 with d₀,...,d_n-1 odd integers coprime to each other. It is inspired by the Good formalism, which in turn is based on the Chinese reminder theorem. In this case also the `large Fourier transform' is expressed as a sequence of n `small Fourier transforms' (that involve some constants related to the number theory that describes the formalism). The `small Fourier transforms' can be performed in a classical computer or in a quantum computer (in which case we have the additional well known advantages of quantum Fourier transform circuits). In the case that the small Fourier transforms are performed with a classical computer, complexity arguments for both methods show the reduction in computational time from O(D²) to O(Dlog D). The second method is also used for the fast calculation of Wigner and Weyl functions, in quantum systems with large finite dimension of the Hilbert space.