# 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](02-fourier-series-transforms.md), 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](01-complex-numbers-functions.md)). 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](../../appendix/E-math-identities.md)), 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](../../appendix/C-notation-glossary.md). This
makes the *inverse* DFT carry $+$, matching the QFT's $\omega^{+xy}$ action in
[Appendix E §6](../../appendix/E-math-identities.md).)
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](../../appendix/E-math-identities.md) and proved in
[lesson 1](01-complex-numbers-functions.md): $\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](01-complex-numbers-functions.md)). 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](../../appendix/E-math-identities.md)), 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](02-fourier-series-transforms.md), 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](02-fourier-series-transforms.md).
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](../../appendix/E-math-identities.md)):
$$
\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](../../appendix/C-notation-glossary.md) 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](01-complex-numbers-functions.md). That is the QFT gate-count $\Theta(n^2)$ recorded in
[Appendix E §8](../../appendix/E-math-identities.md).
- **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**](../../term-2-qc-core/c04-qft-qpe/01-quantum-fourier-transform.md);
> it is then used for [Phase Estimation](../../term-2-qc-core/c04-qft-qpe/03-quantum-phase-estimation.md)
> 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)
```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.
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.
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](../../appendix/E-math-identities.md)) — the single-qubit QFT *is* the Hadamard,
which is why the QFT on $n$ qubits begins with a Hadamard on each.
Solution
Bin $k$ corresponds to frequency $k f_s/N = k$ Hz for $k4$.
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.
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.
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](../../appendix/E-math-identities.md)), 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](../../term-2-qc-core/c04-qft-qpe/01-quantum-fourier-transform.md).
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](../../term-2-qc-core/c04-qft-qpe/01-quantum-fourier-transform.md).