The Discrete Fourier Transform

The Quantum Fourier Transform (QFT) is at the heart of some of the most important quantum algorithms — Shor's factoring algorithm and quantum phase estimation among them. Before building the quantum version, it is worth recalling what the classical Discrete Fourier Transform (DFT) does, because the QFT computes exactly the same mathematical function, just on quantum amplitudes rather than on a list of numbers.

Signals and frequency content

Suppose you record a sound for one second and sample it $N$ times, obtaining a list of real (or complex) numbers

x_0,\, x_1,\, \dots,\, x_{N-1}.

Each $x_j$ is the amplitude of the signal at time $t_j = j/N$ . The signal might contain several pure tones mixed together, and you want to find out which frequencies are present and how strongly. That is exactly what the DFT does.

The DFT formula

The DFT maps the time-domain vector $\mathbf{x} = (x_0, \dots, x_{N-1})$ to a frequency-domain vector $\mathbf{y} = (y_0, \dots, y_{N-1})$ by

y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \, \omega_N^{jk}, \qquad k = 0, 1, \dots, N-1,

where $\omega_N = e^{2\pi i / N}$ is the primitive $N$ -th root of unity. The coefficient $y_k$ measures how much the signal oscillates at frequency $k$ cycles per sample window.

Math you'll use here: roots of unity. The number $\omega_N = e^{2\pi i/N}$ sits on the unit circle, and its powers march around that circle in $N$ equal steps before returning to where they started, so $\omega_N^{m}$ depends only on $m \bmod N$ . For $N=4$ , $\omega_4 = e^{i\pi/2} = i$ , and the powers cycle

\omega_4^0 = 1,\quad \omega_4^1 = i,\quad \omega_4^2 = -1,\quad \omega_4^3 = -i,\quad \omega_4^4 = 1,\ \dots

which is exactly the pattern of entries you will see in $F_4$ below. The key fact behind unitarity is orthogonality: summing one full lap of any nonzero frequency cancels to zero, while a zero frequency just adds $N$ ones,

\sum_{j=0}^{N-1} \omega_N^{(k-k')\,j} = \begin{cases} N, & k \equiv k' \pmod N,\\[2pt] 0, & \text{otherwise.} \end{cases}

Two different rows of the DFT matrix are therefore orthogonal and each row has squared norm $1$ after the $1/\sqrt{N}$ factor — that is precisely why $F_N F_N^\dagger = I$ in the next section.

The DFT as a matrix

Because the DFT is a linear map, it can be written as matrix multiplication $\mathbf{y} = F_N \mathbf{x}$ , where the $(k,j)$ entry of the $N \times N$ DFT matrix $F_N$ is

(F_N)_{kj} = \frac{1}{\sqrt{N}} \omega_N^{jk}.

For $N = 4$ the matrix is

F_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix}.

The rows are sampled complex exponentials at frequencies $k = 0, 1, 2, 3$ . You can verify directly that $F_4 F_4^\dagger = I$ , confirming that $F_4$ is unitary.

The inverse DFT

Because $F_N$ is unitary, its inverse is simply its conjugate transpose: $F_N^{-1} = F_N^\dagger$ . Explicitly,

x_j = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} y_k \, \omega_N^{-jk}.

The inverse DFT converts frequency-domain data back to the time domain, and its formula differs from the forward DFT only by the sign of the exponent.

Naive complexity and the FFT

Computing all $N$ outputs of the DFT naively requires $N$ multiplications and additions for each of the $N$ outputs, giving $O(N^2)$ operations. For $N = 2^n$ , the Fast Fourier Transform (FFT) exploits the recursive structure of $\omega_N$ to reduce this to $O(N \log N) = O(n \cdot 2^n)$ operations — a dramatic improvement that made signal processing practical.

Despite the FFT's speed, factoring an $n$ -bit number still requires classical steps exponential in $n$ . The QFT will allow quantum computers to evaluate the transform in only $O(n^2)$ gate operations on $n$ qubits — an exponential improvement over even the FFT when measured per input qubit — and that efficiency is the key ingredient in Shor's algorithm.

What comes next

In the following lessons we will:

Define the QFT as a unitary transformation on the standard $n$ -qubit basis states.
Show that it equals the DFT acting on the vector of computational-basis amplitudes.
Build the QFT circuit gate by gate from Hadamards and controlled phase rotations.
Apply the QFT to quantum phase estimation, which underlies Shor's factoring algorithm.

Keeping the DFT formula $y_k = \frac{1}{\sqrt{N}} \sum_j x_j \omega_N^{jk}$ in mind will make every subsequent step feel like a natural generalization.