Discrete Fourier Transform

The Discrete Fourier Transform (DFT) is a linear transformation that maps a finite sequence of N complex numbers to another sequence of N complex numbers, decomposing a discrete signal into its constituent frequency components. Where the continuous Fourier transform operates on functions over ℝ, the DFT operates on vectors in ℂᴺ, making it computable by finite machines.

The DFT of a sequence x₀, x₁, ..., x_{N-1} is defined as X_k = Σ_{n=0}^{N-1} x_n · e^{-2πink/N} for k = 0, ..., N−1. This is a matrix multiplication: the DFT matrix has entries ω^{jk} where ω = e^{-2πi/N} is a primitive Nth root of unity. Direct computation requires O(N²) operations; the Fast Fourier Transform (FFT) reduces this to O(N log N) by exploiting the factorization of ω into smaller roots.

The Quantum Fourier Transform used in Shor's Algorithm is the quantum analog of the DFT — applied to superpositions of basis states rather than classical vectors — and achieves the same decomposition with only O(N²) quantum gates, exponentially fewer than the N operations the classical DFT matrix would formally require if applied sample-by-sample. The information-theoretic elegance of the DFT is that it makes periodicity visible: periodic sequences have sparse Fourier representations, concentrated at multiples of the fundamental frequency. Shor's period-finding exploits this fact directly.