Quantum Algorithms Database
Quantum Fourier Transform (QFT)
The quantum analog of the discrete Fourier transform, performed exponentially faster than the classical Fast Fourier Transform.
Year
1994
Inventor(s)
Don Coppersmith (building on classical FFT)
Speedup Type
Exponential Speedup
Difficulty
★★★★☆
The Problem
Transforming a quantum state to reveal its underlying periodicity or frequency structure.
How It Works
Uses a sequence of Hadamard and controlled-phase gates to transform amplitudes, extracting frequency information encoded across a register of qubits.
Real-World Impact
A core subroutine used inside Shor's Algorithm and quantum phase estimation; rarely used as a standalone algorithm but essential as a building block.