The Classical DFT Recapped

Open your phone's photo app and tap a picture. Somewhere in the chain between the sensor that captured the light and the pixels now glowing on your screen, a Discrete Fourier Transform was computed. The same transform decoded the YouTube video you watched earlier. The same transform found the faint radio echo of a pulsar inside the noise at the Giant Metrewave Radio Telescope near Pune. The same transform is inside every MRI scan, every 5G tower, every Diwali song compressed to fit on an SD card.

It is the most important linear operation in signal processing — almost certainly the most frequently executed numerical algorithm on Earth. And in the next chapter you will meet its quantum cousin, the Quantum Fourier Transform, which is the engine at the heart of Shor's factoring algorithm and phase estimation. Before you can see what the quantum version adds, you need the classical version crisp in your head: the formula, the geometry, the matrix, and the fast algorithm that makes it practical.

This chapter is a careful recap. If you have met the DFT before in a signals course, some of what follows will be familiar — stay for the matrix form and the orthogonality argument, which are what the quantum version builds on. If you have not met it before, do not worry: everything you need is in here, derived from scratch, no handwaving.

The idea — a signal, and its frequency recipe

Start with the picture.

You have a string of N numbers — think of them as samples of a sound wave, measured once every millisecond; or pixel intensities along one row of an image; or the closing price of a stock on each of N consecutive days. Call them x_0, x_1, \ldots, x_{N-1}. These N numbers live in "sample space" or "time domain" — the axis you are indexing along is whatever the input is indexed along (time, position, day number).

The DFT takes this signal and gives you back a second list of N numbers: y_0, y_1, \ldots, y_{N-1}. These new numbers live in "frequency space" — y_k tells you how much of frequency k is present in the original signal.

What does "frequency k" mean here? It means a specific pure oscillation — a sinusoid whose value at sample j is e^{2\pi i\, jk/N}. That complex exponential is a pure rotation in the complex plane: as j runs from 0 to N-1, the exponent 2\pi i\, jk/N sweeps around the unit circle k full times. So frequency k=1 is the slowest non-trivial wave (one full turn in N samples); frequency k=2 goes round twice; frequency k = N/2 is the fastest meaningful wave (flips sign every sample).

The DFT says: any signal — any list of N complex numbers — can be written as a sum of these N pure waves, and y_k is exactly the amount of wave-k you need to use.

Why this is interesting: some signals look messy in time but tidy in frequency. A cricket commentator's voice in a raw microphone recording looks like a jagged line with no pattern. The same signal in the frequency domain looks like a few narrow bumps — one at the vocal-cord fundamental, a few at harmonics. You can now delete the bumps you do not care about (say, a 50 Hz hum from the electrical mains in the stadium), inverse-transform, and get back a cleaner voice. That is digital signal processing in one paragraph — and the DFT is the step that makes it possible.

The formula — and decoding every symbol

Here is the DFT, written precisely.

Reading the formula. Walk through it piece by piece.

• x_j is the j-th input sample — one of the N numbers you started with.
• e^{2\pi i\, jk/N} is a complex number on the unit circle. Its modulus is 1; its angle is 2\pi\, jk/N radians. You can think of it as a stamp of "how aligned is sample j with frequency-k wave at this instant."
• The sum \sum_{j=0}^{N-1} runs over every input sample. For each output index k, you multiply every sample by its corresponding unit-circle phase and add them all up.
• The 1/\sqrt N is a normalisation so the transform preserves total energy — see the orthogonality section below.
• The output y_k is a complex number whose modulus |y_k| tells you the amplitude of frequency k in the signal, and whose argument \arg(y_k) tells you the phase shift of that frequency.

Why the formula has this exact shape: any complex number e^{2\pi i\, jk/N} is a point on the unit circle, and the N values \omega^0, \omega^1, \ldots, \omega^{N-1} for \omega = e^{2\pi i/N} are the N "roots of unity" — evenly spaced points on the circle. The DFT is the change of basis from the standard basis (N spikes, one per sample) into the basis made of these N complex waves. The formula is just "compute coefficients of the signal in the new basis" — the same way you project a 3D vector onto the x-axis by dotting it with \hat x.

Roots of unity — the circle you need to know

Define \omega = e^{2\pi i/N}. This single complex number is the N-th primitive root of unity: it is the unit-modulus complex number whose N-th power is 1. Specifically, \omega^N = e^{2\pi i} = 1.

Its powers — \omega^0, \omega^1, \omega^2, \ldots, \omega^{N-1} — are N different points evenly spaced around the unit circle. Together, they are called the N-th roots of unity, because each one satisfies z^N = 1.

With this shorthand, the DFT formula collapses to

Much tidier. The whole transform is built from a single complex number \omega and its powers. Everything that follows — the matrix form, the orthogonality proof, the inverse formula — is just arithmetic on \omega^{jk} for various j and k.

The matrix form — a unitary F

The DFT is linear: scaling the input by c scales the output by c; adding two inputs gives the sum of their outputs. Every linear map from \mathbb{C}^N to \mathbb{C}^N is a matrix, so the DFT is a matrix. Define

Then y = Fx as column vectors. The row index is k (the output frequency); the column index is j (the input sample).

Here is the N=4 case written out. With \omega = e^{2\pi i/4} = i, the powers \omega^{jk} cycle through 1, i, -1, -i:

Why the rows look like that: row k has entries \omega^{0\cdot k}, \omega^{1\cdot k}, \omega^{2\cdot k}, \omega^{3\cdot k} — that is, the powers of \omega^k. Row 0 is all 1's. Row 1 is 1, i, -1, -i (one full turn). Row 2 is 1, -1, 1, -1 (two full turns — Nyquist). Row 3 is 1, -i, -1, i (three full turns, same as -1 full turn going the other way).

F is unitary. Compute F^\dagger F. The (k, k') entry is

Why that sum is easy: if k = k', each term is \omega^0 = 1 and the sum is N, giving (F^\dagger F)_{kk} = 1. If k \neq k', the exponent k'-k is a non-zero integer between -(N-1) and N-1, and the sum \sum_{j=0}^{N-1} \omega^{jm} is a geometric series with ratio \omega^m \neq 1, which sums to (1 - \omega^{Nm})/(1 - \omega^m) = (1 - 1)/(1-\omega^m) = 0. So the off-diagonal entries vanish.

Put those together: (F^\dagger F)_{kk'} = \delta_{k,k'} — the identity matrix. So F^\dagger F = I, meaning F is unitary, and F^{-1} = F^\dagger. The inverse of the DFT is the complex conjugate of its transpose — which, looking at entries, is exactly the formula you would get by flipping the sign of the exponent in the DFT itself. That is why the inverse DFT formula has e^{-2\pi i\, jk/N}: it is the complex conjugate of e^{2\pi i\, jk/N}.

The geometric orthogonality-of-roots-of-unity calculation you just saw — \sum_{j=0}^{N-1} \omega^{jm} = N \delta_{m,0} — is the single algebraic fact that makes Fourier analysis work. It is worth memorising: the N roots of unity sum to zero unless they are all 1.

Worked examples

Complexity — naive vs Fast

Computing the DFT from the formula directly means, for each of the N output values y_k, summing N terms. That is N \times N = N^2 multiplications and additions — quadratic in the signal length. For N = 1024 (a small chunk of audio), that is a million operations. For N = 2^{20} \approx 10^6 (a modest image row), it is 10^{12} — a trillion. Naive DFT does not scale.

The Fast Fourier Transform (Cooley and Tukey, 1965 — though Gauss seems to have known it as early as 1805) is an O(N \log N) algorithm that computes exactly the same DFT using a divide-and-conquer trick: split the sum into even-j and odd-j pieces, each of which is itself a DFT of half the length. The idea recurses: each length-N DFT is two length-N/2 DFTs plus N combining operations, so T(N) = 2T(N/2) + O(N), which solves to T(N) = O(N \log N).

Why this speedup was transformative: before Cooley–Tukey, spectrum analysis on a 10^6-sample signal was simply impossible at interactive speeds. After, it was interactive. Digital audio, JPEG compression, real-time radar, MRI reconstruction, OFDM in 4G and 5G, GNR radio data pipelines — all of these are practical because O(N \log N) is fast and O(N^2) is not.

Why this chapter sets up the quantum version

Here is where the classical DFT points toward the Quantum Fourier Transform, the topic of the next chapter.

An n-qubit quantum state has N = 2^n complex amplitudes — one for each basis string |00\ldots 0\rangle, |00\ldots 1\rangle, \ldots, |11\ldots 1\rangle. Those amplitudes form a length-N complex vector, exactly like a signal.

The Quantum Fourier Transform is the unitary operation on an n-qubit state whose action on the amplitude vector is the DFT. Mathematically it is the same linear map F you just met. Algorithmically it is wildly different, because:

• The amplitude vector of an n-qubit state has N = 2^n entries, exponentially many in the qubit count. A classical FFT on such a vector would need O(N \log N) = O(n \cdot 2^n) operations — exponential in n.
• The Quantum Fourier Transform, implemented as a quantum circuit on n qubits, needs only O(n^2) = O((\log N)^2) gates. Polynomial in n — exponentially fewer operations than the classical FFT on the same-length vector.

That is the speedup. It does not mean the QFT solves the DFT problem faster in the sense of "read out all N frequency coefficients." Quantum measurement only reveals one basis outcome per run. But it does mean that certain algorithmic patterns — where you only need a sample from the Fourier-transformed distribution, or where you are running Fourier as an intermediate step and then using interference — become exponentially cheaper.

Shor's factoring algorithm and quantum phase estimation both exploit this. Their engines run a QFT on a state whose amplitude vector has N = 2^n entries — and the full transform would take a classical FFT O(n \cdot 2^n) \approx 2^n operations, exponential in n. The quantum version does it in O(n^2). The quantum advantage in Shor's algorithm is, at its heart, the exponential gap between O(n \cdot 2^n) and O(n^2) on this very specific linear transformation.

The next chapter — QFT defined — makes this precise.

Common confusions

• "DFT and FFT are the same thing." No — the DFT is the mathematical object (a specific linear transformation on \mathbb{C}^N). The FFT is an algorithm for computing it fast. A different fast algorithm, or even the naive O(N^2) direct computation, still produces the same DFT. The DFT is the recipe; the FFT is an efficient kitchen.

• "DFT only works on real signals." No — the DFT is defined for any complex-valued input. Real signals are a special case, and their DFTs have a symmetry (the Hermitian conjugate: y_{N-k} = \overline{y_k} for real x), but the transform is not restricted to real inputs. Quantum states — the kind of input the QFT will see — have complex amplitudes, and the DFT handles them natively.

• "The DFT gives you the frequencies of the signal." Partly true, but watch the language. The DFT gives you the coefficients y_k of the frequencies-k basis waves e^{2\pi i jk/N} — it does not "find" frequencies; it expresses the signal as a linear combination in a fixed basis. Which basis waves are indexed by k is built into the formula, not discovered by it.

• "The normalisation 1/\sqrt N is a convention that does not matter." It is a convention, but it does matter. Different sources use 1/N out front of the forward transform only (then nothing on the inverse), or 1 out front of forward and 1/N on the inverse. The symmetric 1/\sqrt N choice makes F unitary (F^\dagger F = I), which is the convention quantum mechanics demands because quantum states have norm 1. Always check what convention a source is using before plugging into a formula.

• "The DFT is a spectral decomposition in the eigenvalue sense." This is a loose use of "spectral" common in engineering that conflates two different mathematical ideas. In linear algebra, a spectral decomposition writes a matrix in terms of its eigenvectors. The DFT is a change of basis — a way of expressing a signal in a new basis — not a diagonalisation of an operator. The two are related (the DFT diagonalises translation operators) but not identical. Engineering calls the DFT's output the "spectrum" by analogy with optical spectra; the word does not imply "eigenvalues of the signal."

Going deeper

Cooley–Tukey in one derivation

Split the DFT sum by even and odd j (assume N is even, write N = 2M):

Relabel: write even j as 2m and odd j as 2m+1, with m running from 0 to M-1:

Notice that \omega_N^{2} = e^{2\pi i \cdot 2/N} = e^{2\pi i/M} = \omega_M — the primitive M-th root of unity. So both inner sums are themselves length-M DFTs of the even-indexed and odd-indexed sub-signals. Let E_k and O_k denote those half-length DFTs; then

for k = 0, 1, \ldots, M-1. (The second line uses \omega_N^{k+M} = -\omega_N^k, which follows from \omega_N^M = e^{i\pi} = -1.)

That is the Cooley–Tukey step: one length-N DFT becomes two length-M = N/2 DFTs plus N "butterfly" combinations. Recursing gives T(N) = 2T(N/2) + O(N) = O(N \log N).

The construction assumes N is a power of 2 for clean recursion. More general splittings (mixed-radix, prime-factor, Rader, Bluestein) handle other sizes; all land at O(N \log N) with different constants.

DFT as a change of basis and as a group Fourier transform

Two views of the DFT that will pay off in the QFT chapter:

Change of basis. Think of \mathbb{C}^N as having two natural bases. The standard basis is \{\delta_0, \delta_1, \ldots, \delta_{N-1}\}, where \delta_j is the vector with a 1 in slot j and zeros elsewhere — the "signal is a spike at j" basis. The Fourier basis is \{f_0, f_1, \ldots, f_{N-1}\}, where f_k is the vector whose j-th entry is \omega^{jk}/\sqrt N — the "signal is a pure wave of frequency k" basis. The DFT is exactly the unitary that takes standard-basis coordinates to Fourier-basis coordinates. In quantum language: the DFT rotates you from the "position" basis to the "momentum" basis.

Fourier on \mathbb{Z}_N. The set \{0, 1, 2, \ldots, N-1\} with addition mod N forms an abelian group called \mathbb{Z}_N. Harmonic analysis on a finite abelian group G gives a canonical "group Fourier transform" — for \mathbb{Z}_N, that transform is exactly the DFT. The Fourier basis vectors are the characters of the group: the homomorphisms \chi_k : \mathbb{Z}_N \to U(1), \chi_k(j) = \omega^{jk}. Every DFT formula and identity you know has a group-theoretic interpretation.

This second view generalises. The quantum Fourier transform over an arbitrary abelian group G is the analog of the DFT for G, and underlies the hidden subgroup problem — a unifying abstraction that contains Shor's factoring, discrete log, and Simon's algorithm as special cases.

The convolution theorem and fast polynomial multiplication

Convolution of two length-N signals x and h is the signal x * h defined by (x*h)_k = \sum_j x_j\, h_{k-j} (indices mod N). Convolution is expensive to compute directly — O(N^2) operations.

The convolution theorem. If \mathcal{F} denotes the DFT, then

where the product on the right is entry-wise (not matrix multiplication). Because entry-wise multiplication is O(N) and the FFT is O(N\log N), the whole pipeline — FFT both inputs, multiply entry-wise, inverse-FFT — computes convolution in O(N\log N) time. A factor-N/\log N speedup for any problem that boils down to convolution.

And a lot of problems do. Polynomial multiplication is the clearest example: multiplying two degree-N polynomials p and q amounts to convolving their coefficient lists. The Schönhage–Strassen algorithm uses exactly this to multiply N-bit integers in time O(N \log N \log\log N), dramatically faster than long multiplication's O(N^2). The Harvey–van der Hoeven 2019 algorithm pushes this down to O(N \log N), at last matching the theoretical lower bound.

Every high-performance integer-multiplication library (including those used internally by the Python arbitrary-precision integer implementation for very large integers) uses an FFT-based multiplication under the hood.

The DFT in India's applied work

At the Giant Metrewave Radio Telescope (GMRT, Narayangaon, 80 km from Pune), radio data from the array's thirty dishes is cross-correlated and Fourier-transformed in real time to produce sky images. At IIT Madras and IIT Bombay, signal-processing research groups work on FFT-based algorithms for millimetre-wave 5G receivers and for medical imaging. Every Aadhaar biometric comparison at UIDAI runs FFT-accelerated image-processing filters on fingerprint and iris data. The FFT is not abstract; it is the workhorse numerical algorithm behind India's largest scientific and infrastructure projects.

Where this leads next

• QFT defined — the same transformation, applied to the amplitude vector of an n-qubit state. The next chapter.
• QFT circuit construction — how to build the QFT from Hadamards and controlled phase gates, in O(n^2) operations.
• Why QFT is efficient — the careful comparison of classical FFT (O(N\log N)) versus QFT (O((\log N)^2)) and what the speedup actually means.
• Quantum phase estimation — the algorithm that extracts an eigenphase of a unitary, built directly on top of the QFT.
• Shor's algorithm — factoring via period-finding, the QFT's flagship application.

References

1. Wikipedia, Discrete Fourier transform — definitions, conventions, and the full table of symmetries.
2. Wikipedia, Fast Fourier transform — the algorithmic side, Cooley–Tukey and beyond.
3. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §5.1 — the classical–quantum bridge, setting up QFT — Cambridge University Press.
4. John Preskill, Lecture Notes on Quantum Computation, Chapter 6 — the DFT-to-QFT correspondence with full derivations — theory.caltech.edu/~preskill/ph229.
5. J.W. Cooley and J.W. Tukey, An Algorithm for the Machine Calculation of Complex Fourier Series (1965) — DOI:10.1090/S0025-5718-1965-0178586-1. The original O(N\log N) paper.
6. Qiskit Textbook, Quantum Fourier Transform — hands-on QFT with Qiskit code, including a classical DFT recap.