← Quantum Store · Guides · Lessons · Glossary · About · Türkçe
What is the quantum Fourier transform?
The quantum Fourier transform (QFT) computes the discrete Fourier transform of the amplitudes with H and controlled-phase gates; it underlies period finding and phase estimation.
The classical Fourier transform splits a signal into its frequencies. The QFT applies the same transform to the amplitudes of a quantum state: it turns a periodic amplitude pattern into a few distinct results that reveal the period. On n qubits it needs about n²/2 gates; the classical fast Fourier transform of a vector of the same size takes on the order of n·2ⁿ operations.
The result of the QFT cannot be read out directly, only sampled by measurement. It is therefore used in problems where the result concentrates in a few peaks, such as period finding in Shor’s algorithm and phase estimation.
Try it yourself
The lesson The quantum Fourier transform: catching the period lets you try this concept in the browser, with no installation.
Related packages
Related concepts
- Quantum phase estimation (QPE) · Quantum phase estimation (QPE) reads the phase a gate adds to one of its eigenstates as a binary number in counting qubits, using phase kickback and the inverse Fourier transform.
- Shor’s algorithm · Shor’s algorithm factors large numbers exponentially faster than known classical methods, which is why it threatens RSA encryption.
- Quantum interference · Quantum interference is the way amplitudes add up like waves, raising the probability of some results and cancelling others to zero.