  We propose an implementation of the algorithm for the fast Fourier transform
(FFT) as a quantum circuit consisting of a combination of some quantum gates.
In our implementation, a data sequence is expressed by a tensor product of
vector spaces. Namely, our FFT is defined as a transformation of the tensor
product of quantum states. It is essentially different from the so-called
quantum Fourier transform (QFT) defined to be a linear transformation of the
amplitudes for the superposition of quantum states. The quantum circuit for the
FFT consists of several circuits for elementary arithmetic operations such as a
quantum adder, subtractor and shift operations, which are implemented as
effectively as possible. Namely, our circuit does not generate any garbage
bits. The advantages of our method compared to the QFT are its high
versatility, and data storage efficiency in terms, for instance, of the quantum
image processing.
