Quantum circuit for the fast Fourier transform
arXiv:1911.03055 · doi:10.1007/s11128-020-02776-5
Abstract
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.
arXiv comment20 pages, typos corrected, published version
References in corpus (10)
- Elementary gates for quantum computation
- Quantum random access memory
- Quantum Networks for Elementary Arithmetic Operations
- A new quantum ripple-carry addition circuit
- Architectures for a quantum random access memory
- Addition on a Quantum Computer
- Circuit-Based Quantum Random Access Memory for Classical Data
- Quantum Algorithms and the Fourier Transform
- Quantum Fourier Transform in Computational Basis
- Reversible addition circuit using one ancillary bit with application to quantum computing
Cited by in corpus (9)
- Quantum random access memory via quantum walk
- Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory
- Quantum Multiplication Algorithm Based on the Convolution Theorem
- Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
- Two-level Quantum Walkers on Directed Graphs I: Universal Quantum Computing
- Quantum Radio Astronomy: Data Encodings and Quantum Image Processing
- High-dimensional quantum Fourier transform of twisted light
- QFT based quantum arithmetic logic unit on IBM quantum computer
- Quanta in sound, the sound of quanta: a voice-informed quantum theoretical perspective on sound