The QFT is the quantum version of the DFT: |x⟩ → (1/√N) Σ e^{2πixy/N} |y⟩. It uses O(n²) gates vs O(n·2ⁿ) classical FFT gates — exponentially fewer operations on quantum states.
—
Classical FFT ops
—
QFT gate count
—
Gate ratio
QFT Circuit — n=4 qubits
Input State Amplitudes
QFT Output — Frequency Domain
Mathematical Structure
QFT|x⟩ = (1/√N) Σ_{y=0}^{N-1} e^{2πixy/N} |y⟩
Circuit: H on each qubit + controlled-R_k gates where R_k = [[1,0],[0,e^{2πi/2^k}]]
Phase kickback: controlled phase e^{iφ} "kicks back" to control qubit
QFT†·QFT = I (unitary → invertible with same circuit reversed)
The QFT is a key subroutine in Shor's, quantum phase estimation, and HHL linear systems. Unlike classical FFT, the QFT doesn't give direct access to amplitudes — measurement collapses the superposition.