The Discrete Fourier Transform

The continuous Fourier transform is beautiful; the discrete one is what runs. Sample a signal at $N$ points and Fourier analysis becomes a single matrix–vector product by a special $N\times N$ matrix — one whose normalized form is unitary. That unitarity is not a footnote: it is the exact reason the Quantum Fourier Transform exists as a legal quantum operation, and the FFT's $O(N\log N)$ trick is the classical shadow of the QFT's $O(n^2)$ circuit. This lesson is the hinge between Term 0 and the quantum algorithms to come.

Learning Objectives

By the end of this lesson you will be able to:

1. Define the discrete Fourier transform $X_k = \sum_{n} x_n\,e^{-2\pi i kn/N}$ and its inverse, and express both as matrix–vector products.
2. Prove that the normalized DFT matrix $U = \tfrac{1}{\sqrt N}[\omega^{-kn}]$ is unitary, using the roots-of-unity orthogonality relation.
3. Explain the periodicity of the DFT and connect it to sampling and aliasing.
4. Contrast the $O(N^2)$ naive DFT with the $O(N\log N)$ FFT and explain the divide-and-conquer idea.
5. Articulate precisely how the Quantum Fourier Transform performs this same unitary on amplitudes in $O(n^2)$ gates with $n=\log_2 N$, and locate where that is developed.
6. Build the DFT matrix in NumPy, verify unitarity with np.allclose, and check it against np.fft.

---

Intuition

You cannot store a continuous signal in a computer — you store $N$ samples $x_0,\dots,x_{N-1}$. The discrete Fourier transform asks the same question as before ("what frequencies is this made of?") but now there are only $N$ frequencies to ask about, indexed $k = 0,\dots,N-1$. So the DFT is finite: $N$ inputs in, $N$ complex amplitudes out. Each output $X_k$ is the overlap of the sampled signal with a sampled pure tone $\omega^{-kn}$ — exactly the inner-product "project onto a frequency" move from lesson 2, now a finite sum.

Because it is finite and linear, the DFT is a matrix. And the magic from the roots of unity comes back: the rows of that matrix are sampled tones, and distinct tones are orthogonal (the vanishing-sum theorem from lesson 1). Orthogonal rows, after normalizing, make a unitary matrix — a rotation in $\mathbb C^N$ that preserves length. Hold onto that word unitary: in quantum computing, unitary = "a thing a closed quantum system is allowed to do." The DFT being unitary is what lets a quantum computer perform it, and do so astonishingly fast.

There are two efficiency stories here, and they rhyme. Classically, the naive DFT costs $N^2$ multiply-adds, but the FFT exploits the recursive structure of the roots of unity to do it in $N\log N$. Quantumly, the QFT exploits the same structure to do it in $O((\log N)^2)$ gates — because the $N$ amplitudes live on only $n=\log_2 N$ qubits. Same matrix, three speeds. By the end you should see the DFT not as a numerical recipe but as the unitary that the rest of the program keeps reaching for.

---

Theory

Definition

Given a vector $x = (x_0, x_1, \dots, x_{N-1})\in\mathbb C^N$, the discrete Fourier transform is the vector $X = (X_0,\dots,X_{N-1})$ with

$$\boxed{\;X_k = \sum_{n=0}^{N-1} x_n\, e^{-2\pi i kn/N},\qquad k = 0,1,\dots,N-1.\;}$$

Writing $\omega = e^{2\pi i/N}$ for the primitive $N$-th root of unity (Appendix E §6), the kernel is $e^{-2\pi i kn/N} = \omega^{-kn}$, so $X_k = \sum_n x_n\,\omega^{-kn}$. (We follow the program convention $\omega = e^{+2\pi i/N}$ with a minus sign in the forward DFT kernel; Appendix C §4. This makes the inverse DFT carry $+$, matching the QFT's $\omega^{+xy}$ action in Appendix E §6.)

The inverse discrete Fourier transform (IDFT) recovers $x$ from $X$:

$$\boxed{\;x_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k\, e^{+2\pi i kn/N} = \frac1N\sum_{k=0}^{N-1} X_k\,\omega^{kn}.\;}$$

Proof that this inverts the DFT. Substitute the definition of $X_k$ and swap the finite sums:

$$\frac1N\sum_{k} X_k\,\omega^{kn} = \frac1N\sum_{k}\Big(\sum_{m} x_m\,\omega^{-km}\Big)\omega^{kn} = \sum_{m} x_m\cdot\underbrace{\frac1N\sum_{k} \omega^{k(n-m)}}_{=\,\delta_{nm}} = x_n,$$

where the braced sum is the roots-of-unity orthogonality relation from Appendix E §6 and proved in lesson 1: $\tfrac1N\sum_{k=0}^{N-1}\omega^{k(n-m)} = \delta_{nm}$. Only $m=n$ survives, leaving $x_n$. $\blacksquare$

The DFT as a matrix

Both transforms are linear, so each is multiplication by an $N\times N$ matrix. Define the DFT matrix $W$ with entries

$$W_{kn} = \omega^{-kn} = e^{-2\pi i kn/N},\qquad 0\le k,n\le N-1,$$

so that $X = Wx$. It is a symmetric Vandermonde-type matrix in the powers of $\omega$. For $N=4$, with $\omega = e^{2\pi i/4} = i$ so $\omega^{-1} = -i$:

$$W = \begin{pmatrix} \omega^{0} & \omega^{0} & \omega^{0} & \omega^{0}\\ \omega^{0} & \omega^{-1} & \omega^{-2} & \omega^{-3}\\ \omega^{0} & \omega^{-2} & \omega^{-4} & \omega^{-6}\\ \omega^{0} & \omega^{-3} & \omega^{-6} & \omega^{-9} \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i\\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i \end{pmatrix},$$

reducing each exponent mod $4$ (e.g. $\omega^{-4}=\omega^0=1$, $\omega^{-6}=\omega^{-2}=-1$). Row $k$ samples the pure tone of frequency $k$; the inverse matrix is $W^{-1} = \tfrac1N\,\overline{W}$ (the conjugate, up to the $1/N$), as the IDFT formula shows.

The normalized DFT matrix is unitary

The factor-of-$N$ asymmetry between forward and inverse transforms is just bookkeeping. Split the $1/N$ symmetrically by defining the normalized DFT matrix

$$U := \frac{1}{\sqrt N}\,W,\qquad U_{kn} = \frac{1}{\sqrt N}\,\omega^{-kn}.$$

Theorem. $U$ is unitary: $U^{\dagger}U = U U^{\dagger} = I$.

Proof. Compute the $(j,k)$ entry of $U^{\dagger}U$. The adjoint conjugates and transposes, so $(U^{\dagger}){jn} = \overline{U{nj}} = \tfrac{1}{\sqrt N},\overline{\omega^{-nj}} = \tfrac{1}{\sqrt N},\omega^{nj}$(recall$\overline{\omega^{m}} = \omega^{-m}$, from lesson 1). Then

$$\big(U^{\dagger}U\big)_{jk} = \sum_{n=0}^{N-1} (U^{\dagger})_{jn}\,U_{nk} = \sum_{n=0}^{N-1} \frac{1}{\sqrt N}\,\omega^{nj}\cdot \frac{1}{\sqrt N}\,\omega^{-nk} = \frac{1}{N}\sum_{n=0}^{N-1}\omega^{\,n(j-k)}.$$

By the orthogonality relation $\tfrac1N\sum_{n}\omega^{n(j-k)} = \delta_{jk}$ (Appendix E §6), this equals $\delta_{jk}$, i.e. $U^{\dagger}U = I$. Since$U$is square,$U^{\dagger}U = I$already forces$UU^{\dagger}=I$as well. Hence$U$ is unitary. $\blacksquare$

This is the single most important fact in the lesson. Equivalent restatements:

• The rows (and columns) of $U$ are an orthonormal basis of $\mathbb C^N$ — the normalized sampled tones $\tfrac1{\sqrt N}(\omega^{-kn})_n$.
• $U$ preserves the inner product and the norm: $\langle Ux, Uy\rangle = \langle x,y\rangle$ and $\|Ux\| = \|x\|$. This is the finite-dimensional Parseval/Plancherel identity — the same energy-conservation proved in lesson 2, now exact and algebraic: $\sum_k |X_k|^2 = N\sum_n |x_n|^2$ for the unnormalized $W$, i.e. $\|Ux\|^2 = \|x\|^2$.
• $U^{-1} = U^{\dagger}$, so the inverse transform is "the same machine run backward" — and in particular the IDFT is the adjoint, which is exactly what makes the inverse QFT just the QFT circuit reversed.

Computational cost and the FFT idea

Computing $X = Wx$ directly is $N$ inner products of length $N$: $N^2$ complex multiply-adds, i.e. $O(N^2)$. The Fast Fourier Transform (Cooley–Tukey) brings this to $O(N\log N)$ by divide-and-conquer on the structure of the roots of unity. For even $N$, split $x$ into even- and odd-indexed subsequences:

$$X_k = \sum_{n=0}^{N-1} x_n\,\omega^{-kn} = \underbrace{\sum_{m=0}^{N/2-1} x_{2m}\,\omega^{-k(2m)}}_{\text{even}} + \underbrace{\sum_{m=0}^{N/2-1} x_{2m+1}\,\omega^{-k(2m+1)}}_{\text{odd}}.$$

Now use $\omega^{2} = e^{2\pi i\cdot 2/N} = e^{2\pi i/(N/2)} = \omega_{N/2}$, the primitive $(N/2)$-th root. The even sum is a length-$N/2$ DFT $E_k$ of the even samples; the odd sum is $\omega^{-k}$ times a length-$N/2$ DFT $O_k$ of the odd samples:

$$X_k = E_k + \omega^{-k}\,O_k,\qquad X_{k+N/2} = E_k - \omega^{-k}\,O_k,$$

where the second line uses $\omega^{-(k+N/2)} = \omega^{-k}\omega^{-N/2} = -\omega^{-k}$ (since $\omega^{N/2} = e^{i\pi} = -1$) and the period-$N/2$ of $E,O$. So two half-size DFTs plus $N$ "butterfly" combines give the full DFT. The recurrence $T(N) = 2T(N/2) + O(N)$ solves to $T(N) = O(N\log N)$ — the asymmetry $-1$ in the cancellation (the same $\omega^{N/2}=-1$ that made roots sum to zero) is what halves the work at every level.

Periodicity and sampling

Two periodicities are built in. First, both $x$ and $X$ are treated as periodic with period $N$: $X_{k+N} = \sum_n x_n,\omega^{-(k+N)n} = \sum_n x_n,\omega^{-kn},\underbrace{\omega^{-Nn}}{=1} = X_k$, and likewise$x{n+N} = x_n$. This is why np.fft-based convolution is circular (it wraps around), as flagged in lesson 2.

Second, the DFT lives on sampled data. If a continuous signal $f$ is sampled at rate $f_s$ ($N$ samples spaced $\Delta t = 1/f_s$), the DFT bin $k$ corresponds to frequency $k\,f_s/N$ for $k < N/2$, and to the negative frequency $(k-N)f_s/N$ for $k > N/2$ (the upper half of the spectrum is the negative frequencies, by the period-$N$ symmetry). The Nyquist–Shannon sampling theorem says a signal band-limited to $|\xi| < f_s/2$ is perfectly determined by its samples; frequencies above the Nyquist frequency $f_s/2$ are indistinguishable from lower ones — they alias. Aliasing is just the period-$N$ identity $\omega^{-kn} = \omega^{-(k+N)n}$ wearing a physical hat: two tones whose frequencies differ by a multiple of $f_s$ produce identical samples.

The strong link: this is (classically) what the QFT does

Everything above sets up one of the program's pivotal connections. The Quantum Fourier Transform applies the same unitary $U$ — the normalized DFT matrix — but to the amplitudes of a quantum state rather than to a stored array. With $N = 2^n$ basis states on $n$ qubits, its action on a basis state is precisely the DFT kernel (Appendix E §6):

$$\text{QFT}\,|x\rangle = \frac{1}{\sqrt N}\sum_{y=0}^{N-1} e^{+2\pi i xy/N}\,|y\rangle,\qquad N = 2^n,$$

and on a general superposition $|\psi\rangle = \sum_x x_n|x\rangle$ it maps the amplitude vector $x\mapsto Ux$. (The QFT conventionally uses the $+$ sign — it implements the inverse-DFT kernel, or equivalently the DFT up to the index reversal $y\mapsto -y$; the unitary content is identical and the choice is just our Appendix C §4 convention.) Three things make this revolutionary, and each traces back to a fact in this lesson:

• It is allowed at all because $U$ is unitary (the theorem above). A non-unitary "transform" could not be a quantum gate.
• It is exponentially compact. The classical FFT writes down all $N$ outputs in $O(N\log N) = O(n,2^n)$time. The QFT acts on$n=\log_2 N$qubits using only **$O(n^2)$ gates** — Hadamards and controlled-phase rotations whose phases are exactly the roots of unity $\omega^{2^j}$ from lesson 1. That is the QFT gate-count $\Theta(n^2)$ recorded in Appendix E §8.
• The inverse is free. Because $U^{-1} = U^{\dagger}$, running the QFT circuit in reverse (daggering each gate) gives the inverse — no new construction needed. This is what powers Quantum Phase Estimation.

The catch, which the quantum lessons make precise, is that you cannot read out all $N$ amplitudes: the QFT does not hand you the spectrum, it rearranges amplitudes so that a subsequent measurement samples from a Fourier-transformed distribution. That is exactly enough to find hidden periods, which is why the QFT is the engine of Shor's factoring algorithm.

Forward link (do this when you reach Term 2). The QFT is built, decomposed into $O(n^2)$ gates, and run on Braket in Term 2.4 · The Quantum Fourier Transform; it is then used for Phase Estimation and ultimately Shor's algorithm in Term 3.3. When you get there, the matrix you build below is the exact unitary that circuit implements. [KLM, Ch. 7] and [NC, §5.1] develop the gate decomposition.

---

Worked Examples

Example 1 — DFT of a length-4 signal by hand

Let $x = (1, 0, 1, 0)$. Using the $N=4$ matrix $W$ above ($\omega = i$):

$$X = Wx = \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i\\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i \end{pmatrix} \begin{pmatrix}1\\0\\1\\0\end{pmatrix} = \begin{pmatrix} 1+1\\ 1-1\\ 1+1\\ 1-1\end{pmatrix} = \begin{pmatrix} 2\\ 0\\ 2\\ 0\end{pmatrix}.$$

Interpretation: $x = (1,0,1,0)$ is a tone that repeats every $2$ samples — i.e. it sits at the Nyquist frequency (bin $k=2$) plus a DC component (bin $k=0$). The transform $X = (2,0,2,0)$ confirms energy only at $k=0$ (the average) and $k=2$ (the fastest representable oscillation), with nothing in between. Inverting: $\tfrac14 W^{\dagger}X$ returns $(1,0,1,0)$ — try it.

Example 2 — Verifying unitarity for $N=4$

Take the normalized matrix $U = \tfrac12 W$. Its first two rows are $u_0 = \tfrac12(1,1,1,1)$ and $u_1 = \tfrac12(1,-i,-1,i)$. Check orthonormality via the Hermitian inner product (conjugate the left):

$$\langle u_0, u_0\rangle = \tfrac14(1+1+1+1) = 1,\qquad \langle u_1, u_1\rangle = \tfrac14(|1|^2+|{-i}|^2+|{-1}|^2+|i|^2) = \tfrac14\cdot 4 = 1,$$$$\langle u_0, u_1\rangle = \tfrac14\big(1^{*}\!\cdot 1 + 1^{*}\!\cdot(-i) + 1^{*}\!\cdot(-1) + 1^{*}\!\cdot i\big) = \tfrac14(1 - i - 1 + i) = 0.$$

The diagonal inner products are $1$ and the off-diagonal is $0$ — the rows are orthonormal, the hallmark of a unitary matrix. The general proof (orthogonality relation) gives this for all row pairs and all $N$.

Example 3 — A period reveals itself as a frequency spike

Let $N = 8$ and $x_n = \cos(2\pi\cdot 2 n/8)$ for $n=0,\dots,7$ — a pure cosine completing exactly $2$ cycles over the window. Since $\cos\theta = \tfrac12(e^{i\theta} + e^{-i\theta})$, this signal is $\tfrac12\omega^{2n} + \tfrac12\omega^{-2n}$ with $\omega = e^{2\pi i/8}$. Its DFT is therefore nonzero only where the kernel matches: a spike of height $N/2 = 4$ at bin $k=2$ and another at bin $k = N-2 = 6$ (the alias / negative-frequency partner), with all other bins zero. The DFT has localized the periodicity of $x$ into two sharp peaks — the discrete analog of "a tone in time is a spike in frequency." This peak-at-the-period behavior is precisely what Shor's algorithm reads off the QFT (via measurement) to recover an unknown period.

---

Hands-on (Python)

import numpy as np

# =====================================================================
# 1. Build the (un)normalized DFT matrix and the normalized unitary one.
# =====================================================================
def dft_matrix(N, normalized=False):
    """Return the N×N DFT matrix W with W[k,n] = ω^{-kn}, ω = e^{2πi/N}.
       If normalized, return U = W/√N (the unitary normalized DFT)."""
    k = np.arange(N).reshape(-1, 1)      # column index k
    n = np.arange(N).reshape(1, -1)      # row index n
    W = np.exp(-2j * np.pi * k * n / N)  # ω^{-kn} = e^{-2πi kn/N}
    return W / np.sqrt(N) if normalized else W

N = 8
W = dft_matrix(N)
U = dft_matrix(N, normalized=True)

# Sanity: the N=4 matrix matches the hand computation in the lesson.
print("N=4 DFT matrix (rounded):")
print(np.round(dft_matrix(4), 6).real + 1j * np.round(dft_matrix(4), 6).imag)

# =====================================================================
# 2. PROVE numerically that the normalized DFT matrix is UNITARY.
#    U is unitary  ⇔  U† U = I  ⇔  rows form an orthonormal basis.
# =====================================================================
def dag(A):
    return A.conj().T                    # adjoint (conjugate transpose)

I = np.eye(N)
print("U† U  = I :", np.allclose(dag(U) @ U, I, atol=1e-12))   # True
print("U U†  = I :", np.allclose(U @ dag(U), I, atol=1e-12))   # True
print("U⁻¹ = U†  :", np.allclose(np.linalg.inv(U), dag(U), atol=1e-12))  # True
# Norm preservation (finite-dimensional Parseval / Plancherel):
x = np.random.default_rng(0).standard_normal(N) + 1j * np.random.default_rng(1).standard_normal(N)
print("‖Ux‖ = ‖x‖ :", np.isclose(np.linalg.norm(U @ x), np.linalg.norm(x)))  # True

# =====================================================================
# 3. Our DFT vs. np.fft. NumPy uses the UNNORMALIZED convention X = W x,
#    with the SAME e^{-2πi kn/N} kernel — so it must match W @ x exactly.
# =====================================================================
x = np.array([1, 0, 1, 0], dtype=complex)
print("\nExample 1 check, x = (1,0,1,0):")
print("  W @ x      =", np.round(dft_matrix(4) @ x, 10))   # [2,0,2,0]
print("  np.fft.fft =", np.round(np.fft.fft(x), 10))        # [2,0,2,0]
print("  match      :", np.allclose(dft_matrix(4) @ x, np.fft.fft(x)))  # True

# Inverse: IDFT recovers x.  (np.fft.ifft includes the 1/N.)
X = np.fft.fft(x)
print("  IDFT recovers x:", np.allclose(np.fft.ifft(X), x))             # True

# =====================================================================
# 4. A period shows up as a frequency spike (Worked Example 3).
# =====================================================================
N = 8
n = np.arange(N)
x = np.cos(2 * np.pi * 2 * n / N)        # exactly 2 cycles over the window
X = np.fft.fft(x)
print("\nSpectrum magnitudes of a 2-cycle cosine (N=8):")
print(np.round(np.abs(X), 6))            # spikes of height 4 at bins k=2 and k=6

# =====================================================================
# 5. Cost scaling: naive DFT (matrix multiply, O(N²)) vs FFT (O(N log N)).
#    Both agree; the FFT is dramatically faster as N grows.
# =====================================================================
import time
for N in (256, 1024, 4096):
    x = np.random.default_rng(0).standard_normal(N).astype(complex)
    W = dft_matrix(N)
    t0 = time.perf_counter(); Xslow = W @ x;          t1 = time.perf_counter()
    t2 = time.perf_counter(); Xfast = np.fft.fft(x);  t3 = time.perf_counter()
    assert np.allclose(Xslow, Xfast, atol=1e-8)
    print(f"N={N:5d}:  naive O(N²) = {1e3*(t1-t0):7.2f} ms   "
          f"FFT O(N log N) = {1e3*(t3-t2):7.3f} ms")

What you should observe: U† U = I, U U† = I, U⁻¹ = U†, and ‖Ux‖ = ‖x‖ all print True — a numerical proof that the normalized DFT matrix is unitary and norm-preserving. Our hand-built W @ x matches np.fft.fft exactly (same kernel, same unnormalized convention), and the IDFT round-trips. The 2-cycle cosine produces clean spikes at bins $k=2$ and $k=6$. Finally the timing loop shows the naive $O(N^2)$ matrix product ballooning while the FFT stays nearly flat — the classical preview of why the QFT's $O(n^2)$ gate count is such a leap.

---

Exercises

1. (Easy) DFT by hand. Compute the DFT of $x = (1,1,1,1)$ for $N=4$ using the matrix $W$, and interpret the result.

Solution

Each output is a row of $W$ dotted with $(1,1,1,1)$, i.e. the sum of that row's entries. Row 0 sums to $4$; rows $1,2,3$ are $\{1,-i,-1,i\}$, $\{1,-1,1,-1\}$, $\{1,i,-1,-i\}$, each summing to $0$ (the vanishing-sum theorem!). So $X = (4,0,0,0)$. A constant signal is pure DC: all energy in bin $k=0$, nothing elsewhere.

2. (Easy) Linearity and the inverse. Given $\text{DFT}(x) = X$ and $\text{DFT}(y) = Y$, what is $\text{DFT}(3x - 2y)$? And how do you recover $x$ from $X$ using the matrix $U$?

Solution

By linearity of matrix multiplication, $\text{DFT}(3x-2y) = W(3x-2y) = 3X - 2Y$. Recovery: since $X = Wx = \sqrt N\,Ux$, we have $x = U^{\dagger}X/\sqrt N$ — or directly $x = \tfrac1N W^{\dagger}X$ (the IDFT). The key point is $U^{-1} = U^{\dagger}$, so inverting is just applying the adjoint.

3. (Medium) Unitarity of the $N=2$ DFT. Write $W$ for $N=2$, normalize it, and show by hand that $U^{\dagger}U = I$. What familiar gate is $U$?

Solution

For $N=2$, $\omega = e^{2\pi i/2} = -1$, so W = \begin{psmallmatrix}1&1\\1&-1\end{psmallmatrix} and U = \tfrac1{\sqrt2}\begin{psmallmatrix}1&1\\1&-1\end{psmallmatrix}. $U$ is real and symmetric, so $U^{\dagger} = U$, and U^2 = \tfrac12\begin{psmallmatrix}2&0\\0&2\end{psmallmatrix} = I. Hence $U^{\dagger}U = U^2 = I$: unitary. This $U$ is exactly the Hadamard gate $H$ (Appendix E §2) — the single-qubit QFT is the Hadamard, which is why the QFT on $n$ qubits begins with a Hadamard on each.

4. (Medium) Periodicity and aliasing. A continuous tone at $5$ Hz is sampled at $f_s = 8$ samples/s. Which DFT bin does it land in for $N=8$, and why is that not bin "$5$"? Identify the aliased frequency.

Solution

Bin $k$ corresponds to frequency $k f_s/N = k$ Hz for $k<N/2=4$, and to $(k-N)f_s/N$ Hz for $k>4$. A $5$ Hz tone exceeds the Nyquist frequency $f_s/2 = 4$ Hz, so it aliases: $5,\text{Hz} \equiv 5 - f_s = 5 - 8 = -3,\text{Hz}$. The negative frequency$-3$Hz appears at bin$k$ with $(k-8)\cdot 1 = -3$, i.e. $k = 5$ — but it is physically a $-3$ Hz (equivalently $3$ Hz) component, indistinguishable from a true $3$ Hz tone given these samples. Algebraically this is $\omega^{-5n} = \omega^{(8-5)\cdot(-1)\cdot n}\!\dots$ — the period-$N$ identity $\omega^{-kn} = \omega^{-(k\pm N)n}$. Moral: sample faster than twice the highest frequency, or alias.

5. (Hard) FFT butterfly by hand. Using the radix-2 split $X_k = E_k + \omega^{-k}O_k$, $X_{k+N/2} = E_k - \omega^{-k}O_k$, compute the DFT of $x = (1,2,3,4)$ ($N=4$) via two length-2 DFTs and one butterfly stage. Check against the direct matrix product.

Solution

Even samples $x_{\text{even}} = (x_0,x_2) = (1,3)$; odd $x_{\text{odd}} = (x_1,x_3) = (2,4)$. Length-2 DFTs (the $N=2$ matrix \begin{psmallmatrix}1&1\\1&-1\end{psmallmatrix}): $E = (1+3,\,1-3) = (4,-2)$ and $O = (2+4,\,2-4) = (6,-2)$. Twiddle factors $\omega^{-k}$ with $\omega = e^{2\pi i/4} = i$: $\omega^{0}=1$, $\omega^{-1} = -i$. Combine for $k=0,1$:

$$X_0 = E_0 + \omega^{0}O_0 = 4 + 6 = 10,\qquad X_1 = E_1 + \omega^{-1}O_1 = -2 + (-i)(-2) = -2 + 2i,$$$$X_2 = E_0 - \omega^{0}O_0 = 4 - 6 = -2,\qquad X_3 = E_1 - \omega^{-1}O_1 = -2 - (-i)(-2) = -2 - 2i.$$

So $X = (10,\, -2+2i,\, -2,\, -2-2i)$. Direct $W x$ gives the same (and np.fft.fft([1,2,3,4]) confirms it). The conjugate-symmetry $X_3 = X_1^{*}$ reflects that $x$ is real.

6. (Hard) Counting operations: DFT vs FFT vs QFT. For $N = 2^{20}$ ($\approx 10^6$), estimate the number of complex multiplications for (a) the naive DFT, (b) the FFT, and (c) the number of gates for the QFT. State the qubit count $n$ for the QFT and the moral.

Solution

(a) Naive DFT: $N^2 = 2^{40} \approx 1.1\times 10^{12}$ complex multiplies. (b) FFT: $\sim \tfrac{N}{2}\log_2 N = \tfrac{2^{20}}{2}\cdot 20 = 10\cdot 2^{20}\approx 1.05\times 10^7$ — about $10^5\times$ fewer than naive. (c) QFT: with $n = \log_2 N = 20$ qubits, the standard decomposition uses $\tfrac{n(n+1)}{2} = \tfrac{20\cdot 21}{2} = 210$ Hadamard + controlled-phase gates ($\Theta(n^2)$, Appendix E §8), plus $\lfloor n/2\rfloor$ swaps. Moral: the FFT is an enormous classical win, but it still writes down all $N\approx 10^6$ outputs; the QFT manipulates the same $N$ amplitudes living on just $20$ qubits with a few hundred gates — though you cannot read all amplitudes out, only sample. That exponential compactness, harnessed by phase estimation, is the source of Shor's speedup. See Term 2.4.

---

Checkpoint

1. Write the DFT and its inverse, and identify the kernel.

$X_k = \sum_{n=0}^{N-1} x_n\,e^{-2\pi i kn/N} = \sum_n x_n\,\omega^{-kn}$ (forward), and $x_n = \tfrac1N\sum_{k=0}^{N-1} X_k\,e^{+2\pi i kn/N}$ (inverse), with kernel $\omega^{\mp kn}$ and $\omega = e^{2\pi i/N}$.

2. Why is the normalized DFT matrix $U = W/\sqrt N$ unitary?

$(U^{\dagger}U)_{jk} = \tfrac1N\sum_n \omega^{n(j-k)} = \delta_{jk}$ by the roots-of-unity orthogonality relation. So $U^{\dagger}U = I$ (and, $U$ being square, $UU^{\dagger}=I$): its rows are orthonormal sampled tones.

3. What is the inverse of a unitary, and why does that matter for the QFT?

$U^{-1} = U^{\dagger}$. For the QFT this means the inverse transform is just the circuit run in reverse with each gate daggered — no separate construction — which is what makes Quantum Phase Estimation practical.

4. State the cost of the naive DFT vs. the FFT, and the idea behind the speedup.

Naive DFT is $O(N^2)$; the FFT is $O(N\log N)$. The speedup comes from radix-2 divide-and-conquer: $X_k = E_k + \omega^{-k}O_k$, $X_{k+N/2} = E_k - \omega^{-k}O_k$, recursively splitting into half-size DFTs ($T(N) = 2T(N/2)+O(N)$), using $\omega^{N/2} = -1$.

5. What does periodicity of the DFT imply about convolution and sampling?

The DFT treats data as period-$N$, so FFT-based convolution is circular (wrap-around; zero-pad for linear convolution). For sampled signals, frequencies above Nyquist $f_s/2$ alias onto lower bins — the period-$N$ identity $\omega^{-kn} = \omega^{-(k+N)n}$ in physical disguise.

6. In one sentence: how does the QFT relate to the DFT, and where is it built?

The QFT applies the same unitary (the normalized DFT matrix) to the amplitudes of an $n$-qubit state ($N=2^n$) using only $O(n^2)$ gates; it is constructed in Term 2.4 · The Quantum Fourier Transform.

---

Further Reading

• [NC, §5.1] — the Quantum Fourier Transform and its $O(n^2)$ gate decomposition; the DFT background it rests on.
• [KLM, Ch. 6–7] — DFT → FFT → QFT, developed in the order this course follows.
• [Aar] — intuition for why the QFT's compactness does not let you read out the spectrum, only sample it.
• Appendix E §6, §8 — orthogonality relation, QFT kernel, and the $\Theta(n^2)$ gate count.

---

← Prev: Fourier Series & Transforms · Up: Term 0 · Next: Models of Computation →