Quantum Fourier Transforms (qiskit.aqua.components.qfts)¶
In quantum computing, a Quantum Fourier Transform (QFT) is a linear transformation
on quantum bits, and is the quantum analogue of the discrete Fourier transform.
A QFT is a part of many quantum algorithms, such as
Shor’s algorithm for factoring and computing the discrete
logarithm, and the QPE algorithm for estimating the
eigenvalues of a unitary operator.
A QFT can be performed efficiently on a quantum computer, with a particular decomposition into a product of simpler unitary matrices. It has been shown how, using a simple decomposition, the discrete Fourier transform on \(2^n\) amplitudes can be implemented as a quantum circuit consisting of only \(O(n^2)\) Hadamard gates and controlled phase shift gates, where \(n\) is the number of qubits. This is in contrast to the classical discrete Fourier transform, which takes \(O(n2^n)\) gates, where in the classical case \(n\) is the number of bits. The best quantum Fourier transform algorithms currently known require only \(O(n\log n)\) gates to achieve an efficient approximation.
Most of the properties of the QFT follow from the fact that it is a unitary transformation. This implies that, if \(F\) is the matrix representing the QFT, then \(FF^\dagger = F^{\dagger}F=I\), where \(F^\dagger\) is the Hermitian adjoint of \(F\) where \(I\) is the identity matrix. It follows that \(F^{-1} = F^\dagger\).
Since there is an efficient quantum circuit implementing the QFT, the circuit can be run in reverse to perform the Inverse Quantum Fourier Transform (IQFT). Thus, both transforms can be efficiently performed on a quantum computer.
Quantum Fourier Transforms¶
The Standard QFT. |
|
The Approximate QFT. |