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(opens in a new tab) 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 (opens in a new tab)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 Transform Base Class

Quantum Fourier Transforms