A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.
An algorithm is presented allowing the construction of fast Fourier transforms for any solvable group on a classical computer. The special structure of the recursion formula being the core of this algorithm makes it a good starting point to obtain systematically fast Fourier transforms for solvable groups on a quantum computer. The inherent structure of the Hilbert space imposed by the qubit architecture suggests to consider groups of order 2^n first (where n is the number of qubits). As an example, fast quantum Fourier transforms for all 4 classes of non-abelian 2-groups with cyclic normal subgroup of index 2 are explicitly constructed in terms of quantum circuits. The (quantum) complexity of the Fourier transform for these groups of size 2^n is O(n^2) in all cases.
In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs
O(q2) gates (and
O(q) qubits) to perform the exact Fourier transform over
F2q. Cleve and Watrous (FOCS 2000) improved this gate count to
O(q(logq)2(loglogq)) using the integer multiplication algorithm in
O(n(logn)(loglogn)) time for two
n-bit integers (best known at that time). Our first main result shows that this gate count can be improved to
O(q(logq)). In fact, if there is a multiplication circuit, to multiply two
n-bit integers, with
O(n(logn)α) gates; we get a QFT circuit with
O(q(logq)α) gates (improving upon
O(q(logq)α+1)) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with
o(q(logq)) gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with
O(q(loglog(q/ε))α+1) gates, where
ε is the approximating parameter. Our second main result again improves this to
O(q(loglog(q/ε))α) gates.
This survey presents a comprehensive analysis of the quantum Fourier transform (QFT), a fundamental tool in quantum computing, in comparison to its classical counterpart, the fast Fourier transform (FFT). The study begins with an introduction to the classical Fourier transform, which is widely used in different disciplines such as signal and image processing. The article introduces the QFT as a quantum version of the Fourier transform, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the operation, and highlighting its crucial role in quantum algorithms like Shor’s algorithm for integer factorization. The analysis also addresses the mathematical foundations of the QFT, its implementation in quantum circuits, and the key advantages and challenges associated with its use, such as measurement precision and quantum decoherence. Finally, it concludes with an exploration of the current and potential applications of QFT in quantum computing.
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.