Quantum Fourier Transform & Phase Estimation

From counting in the Fourier basis to estimating eigenvalues

0. What Is a Fourier Transform?

Before any math, the core idea: a Fourier Transform decomposes a signal into the frequencies that make it up.

Mathematically, the (continuous) Fourier Transform takes a function \(f(t)\) and produces \(\hat{f}(\nu)\):

Each frequency component \(\nu\) gets a coefficient. A spike at frequency \(\nu_0\) means the signal has a strong component oscillating at that rate. The exponential \(e^{-2\pi i \nu t}\) is a "probe" that tests how much the signal matches a particular frequency.

That's the full continuous version. In practice (and in computing), we work with finite lists of numbers, not continuous functions. That's where the DFT comes in.

1. The Discrete Fourier Transform (DFT)

The Discrete Fourier Transform does the same thing as the continuous FT, but for a finite list of \(N\) numbers instead of a continuous signal. Instead of integrating over all time, we sum over \(N\) data points.

The DFT maps a vector of \(N\) complex numbers to another vector of \(N\) complex numbers:

where \(\omega_N = e^{2\pi i/N}\) is the primitive \(N\)-th root of unity — a point on the unit circle at angle \(2\pi/N\) (i.e., \(1/N\) of a full turn). Key property: \(\omega_N^N = 1\), so the roots of unity cycle back to 1 after \(N\) steps.

The formula computes one output at a time. \(y_k\) is the \(k\)-th entry of the output vector. To get all \(N\) outputs, you run the formula \(N\) times (once per \(k\)).

Take \(N = 4\). Then \(\omega_4 = e^{2\pi i/4} = i\) (a quarter turn on the unit circle). Say our input is \((x_0, x_1, x_2, x_3)\). The DFT produces 4 outputs:

The DFT can be written as matrix multiplication \(\vec{y} = F_N \vec{x}\), where the DFT matrix \(F_N\) has entries:

The matrix entry at row \(j\), column \(k\) is \(\frac{1}{\sqrt{N}} \omega_N^{jk}\). That's it — compute \(j \times k\), use it as the exponent of \(\omega_N\). Let's build both \(F_2\) and \(F_4\) from scratch.

For \(N = 2\): \(\omega_2 = e^{2\pi i/2} = e^{i\pi} = -1\). The matrix is 2×2, so \(j \in \{0, 1\}\) and \(k \in \{0, 1\}\).

Compute every entry by plugging \(j\) and \(k\) into \(\omega_2^{jk} = (-1)^{jk}\):

Row \(j\)	Col \(k\)	\(j \times k\)	\(\omega_2^{jk} = (-1)^{jk}\)	Value
0	0	0	\((-1)^0\)	1
0	1	0	\((-1)^0\)	1
1	0	0	\((-1)^0\)	1
1	1	1	\((-1)^1\)	−1

Put them into the matrix (don't forget the \(1/\sqrt{N} = 1/\sqrt{2}\) prefactor):

That's the Hadamard gate. The single-qubit QFT is \(H\) — it was always "secretly" a Fourier transform over 2 elements.

For \(N = 4\): \(\omega_4 = e^{2\pi i/4} = e^{i\pi/2} = i\). The matrix is 4×4, so \(j, k \in \{0, 1, 2, 3\}\). We need \(\omega_4^{jk} = i^{jk}\).

First, the powers of \(i\) cycle every 4: \(i^0 = 1,\; i^1 = i,\; i^2 = -1,\; i^3 = -i,\; i^4 = 1,\; \ldots\)

\(j \times k\)	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)
\(j=0\)	\(0 \times 0 = 0\)	\(0 \times 1 = 0\)	\(0 \times 2 = 0\)	\(0 \times 3 = 0\)
\(j=1\)	\(1 \times 0 = 0\)	\(1 \times 1 = 1\)	\(1 \times 2 = 2\)	\(1 \times 3 = 3\)
\(j=2\)	\(2 \times 0 = 0\)	\(2 \times 1 = 2\)	\(2 \times 2 = 4\)	\(2 \times 3 = 6\)
\(j=3\)	\(3 \times 0 = 0\)	\(3 \times 1 = 3\)	\(3 \times 2 = 6\)	\(3 \times 3 = 9\)

Now convert each \(jk\) to \(i^{jk}\) (reduce mod 4, since \(i^4 = 1\)):

\(i^{jk}\)	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)
\(j=0\)	\(i^0 = 1\)	\(i^0 = 1\)	\(i^0 = 1\)	\(i^0 = 1\)
\(j=1\)	\(i^0 = 1\)	\(i^1 = i\)	\(i^2 = -1\)	\(i^3 = -i\)
\(j=2\)	\(i^0 = 1\)	\(i^2 = -1\)	\(i^4 = 1\)	\(i^6 = -1\)
\(j=3\)	\(i^0 = 1\)	\(i^3 = -i\)	\(i^6 = -1\)	\(i^9 = i\)

Add the \(1/\sqrt{4} = 1/2\) prefactor:

The Quantum Fourier Transform applies the DFT matrix to the amplitudes of a quantum state. If a state is written in the computational basis as \(\ket{\psi} = \sum_x \alpha_x \ket{x}\), then:

On a single computational basis state:

To build intuition for what the QFT is "actually doing," map the classical Fourier Transform concepts onto the quantum setting:

Classical FT	QFT
Time points \(t = 0, 1, \ldots, N-1\)	Computational basis states \(\ket{0}, \ket{1}, \ldots, \ket{N-1}\)
Signal value at time \(t\)	Amplitude \(\alpha_x\) of basis state \(\ket{x}\)
Frequency components	Output amplitudes \(\beta_y\) after QFT
Spike at frequency \(\nu\)	Large amplitude on \(\ket{y}\) — means "period \(N/y\) divides \(N\)"

1b. QFT Visualized — States vs Patterns

The QFT converts between two representations. Bar height = amplitude (visible to measurement). Bar color = phase (invisible to measurement).

Left: measure → get 0 with certainty. Right: all bars same height AND same color (phase +1). Pattern is "flat." Measure → get 0, 1, 2, or 3 each with 25%.

Same bar heights as QFT\(\ket{0}\) — measurement gives the same 25% each. But the colors are different: +1 → i → −1 → −i. The phases cycle through all 4 values once. That's "frequency 1."

Phases alternate: +1, −1, +1, −1. Only two colors — this is the Hadamard pattern (N=2 repeated). Frequency 2 = the phase flips twice across 4 slots.

QFT† reads the color pattern (+1, i, −1, −i), recognizes it as "frequency 1," and concentrates all amplitude on \(\ket{1}\). The invisible phases become a visible spike. Measure → get 1 with certainty.

QPE with the T-gate (θ = 1/8), 3 counting qubits. Left: 8 bars, equal height, 8 different colors — measuring gives a random 0–7. Right: QFT† reads the pattern (phases cycle once through all 8 positions = frequency 1), concentrates everything on \(\ket{1}\). Measure → 1 → θ = 1/8.

2. The Quantum Fourier Transform

We now work with \(N = 2^n\) (since we have \(n\) qubits). The QFT on computational basis states is:

The magic of the QFT circuit comes from rewriting this sum as a tensor product. Write \(x\) in binary as \(x = x_1 x_2 \ldots x_n\) (where \(x_1\) is the most significant bit), and use the binary fraction notation:

Through algebraic manipulation (splitting the sum over \(y = y_1 y_2 \ldots y_n\) into \(n\) independent sums over each bit \(y_k\)), we arrive at the product representation:

Written out explicitly for each qubit:

Start from the definition and write \(y\) in binary \(y = y_1 y_2 \ldots y_n\), so \(y = \sum_{k=1}^n y_k 2^{n-k}\):

Substitute \(y = \sum_k y_k 2^{n-k}\):

The exponent factors: \(e^{2\pi i x \sum_k y_k / 2^k} = \prod_k e^{2\pi i x y_k / 2^k}\). And \(\ket{y_1 \ldots y_n} = \ket{y_1} \otimes \cdots \otimes \ket{y_n}\). So the whole sum factors into a tensor product:

Finally, note that \(e^{2\pi i x/2^k}\) only depends on the last \(k\) bits of \(x\) (since \(e^{2\pi i \cdot \text{integer}} = 1\)), which gives us the binary fraction form \(0.x_{n-k+1}\ldots x_n\).

Think of the Fourier basis representation as a clock analogy:

• In binary (computational basis), counting increments the least significant bit fastest: \(000, 001, 010, 011, \ldots\)
• In the Fourier basis, counting rotates qubits around the Z-axis. The first (most significant) output qubit rotates fastest (completing a full rotation for every 2 increments of \(x\)). Each subsequent qubit rotates half as fast.

This is like clock hands: the "seconds hand" (least significant Fourier qubit) moves slowly, while the "milliseconds hand" (most significant Fourier qubit) spins rapidly. The state \(\ket{0} + e^{2\pi i \cdot 0.x_n}\ket{1}\) only cares about the last bit of \(x\) — it flips between \(\ket{+}\) and \(\ket{-}\) with each increment. The deeper qubits encode finer and finer phase information.

3. The QFT Circuit

The product representation tells us exactly how to build the circuit. We need two types of gates:

The circuit processes qubits from top to bottom. For an \(n\)-qubit input \(\ket{x_1 x_2 \ldots x_n}\):

1. Qubit 1: Apply \(H\) to get \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \, 0.x_1}\ket{1})\). Then apply \(CR_2\) (controlled by qubit 2) to add the \(x_2\) contribution, \(CR_3\) (controlled by qubit 3), \(\ldots\), \(CR_n\) (controlled by qubit \(n\)). After all rotations, qubit 1 is in state \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \, 0.x_1 x_2 \ldots x_n}\ket{1})\).
2. Qubit 2: Apply \(H\), then \(CR_2\) (controlled by qubit 3), \(\ldots\), \(CR_{n-1}\) (controlled by qubit \(n\)). Result: \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \, 0.x_2 x_3 \ldots x_n}\ket{1})\).
3. \(\vdots\)
4. Qubit \(n\): Just apply \(H\). Result: \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \, 0.x_n}\ket{1})\).
5. SWAP qubits to reverse their order (qubit 1 ↔ qubit \(n\), qubit 2 ↔ qubit \(n-1\), etc.), because the product representation produces the qubits in reverse order compared to the standard convention.

For \(n = 3\), the circuit (before SWAPs) looks like:

|x₁⟩ ─── H ── R₂ ── R₃ ──────────────────── ×
                │      │                        │
|x₂⟩ ──────── •──── │──── H ── R₂ ────────── │
                       │         │              │
|x₃⟩ ───────────── •──────── •──── H ──── ×

Let's walk through what each gate does:

1. \(H\) on qubit 1: \(\ket{x_1} \to \frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \cdot 0.x_1}\ket{1})\). Note that \(e^{2\pi i \cdot 0.x_1} = e^{2\pi i \cdot x_1/2} = (-1)^{x_1}\), so this is just \(H\ket{x_1}\).
2. \(CR_2\) (control: qubit 2, target: qubit 1): Adds phase \(e^{2\pi i/4} = i\) to qubit 1's \(\ket{1}\) component when \(x_2 = 1\). Qubit 1 becomes \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \cdot 0.x_1 x_2}\ket{1})\).
3. \(CR_3\) (control: qubit 3, target: qubit 1): Adds phase \(e^{2\pi i/8}\) when \(x_3 = 1\). Qubit 1 is now \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \cdot 0.x_1 x_2 x_3}\ket{1})\). Done with qubit 1.
4. \(H\) on qubit 2: \(\ket{x_2} \to \frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \cdot 0.x_2}\ket{1})\).
5. \(CR_2\) (control: qubit 3, target: qubit 2): Qubit 2 becomes \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \cdot 0.x_2 x_3}\ket{1})\). Done with qubit 2.
6. \(H\) on qubit 3: Qubit 3 becomes \(\frac{1}{\sqrt{2}}(\ket{0} + e^{2\pi i \cdot 0.x_3}\ket{1})\). Done.
7. SWAP qubits 1 and 3 to reverse the order.

The total state (after SWAP) is:

which matches the product representation of the QFT.

4. QFT on Key States

The simplest case: \(\text{QFT}\ket{0} = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{0} \ket{y} = \frac{1}{\sqrt{N}} \sum_y \ket{y} = \ket{+}^{\otimes n}\).

The QFT of \(\ket{0}\) is the uniform superposition. This makes sense: in the Fourier basis, the "zero frequency" component is the uniform (DC) signal.

Suppose we have a state that is an equal superposition over evenly spaced computational basis states with spacing \(r\) (assuming \(r\) divides \(N\)):

The QFT maps this to another periodic state with spacing \(N/r\):

Apply the QFT definition:

Swap the sums and examine the inner sum over \(j\):

This is a geometric series. It equals \(N/r\) when \(e^{2\pi i ry/N} = 1\) (i.e., when \(y\) is a multiple of \(N/r\)), and equals 0 otherwise (the terms cancel). So only the values \(y = k \cdot N/r\) for \(k = 0, 1, \ldots, r-1\) survive, each contributing \(N/r\). The overall coefficient becomes \(\sqrt{r/N} \cdot (1/\sqrt{N}) \cdot (N/r) = 1/\sqrt{r}\).

5. The Inverse QFT

Since \(F_N\) is unitary, its inverse is its conjugate transpose \(F_N^\dagger = F_N^{-1}\):

The only difference from the forward QFT is the sign of the exponent (minus instead of plus).

To get the inverse QFT circuit:

1. Take the QFT circuit
2. Reverse the order of all gates
3. Replace every \(R_k\) with \(R_k^\dagger\) (negate the rotation angle: \(e^{2\pi i/2^k} \to e^{-2\pi i/2^k}\))

Equivalently: SWAPs first, then process qubits in reverse order (\(n\) to 1), with each rotation using \(-2\pi/2^k\) instead of \(+2\pi/2^k\).

5b. QFT as Generalized Hadamard

5c. QFT in the QPE Pipeline — The Big Picture

Before diving into the QPE circuit details, here's the high-level story of what happens and why the QFT is needed:

In more detail, the pipeline has four stages:

1. Prepare: Hadamards create a uniform superposition over all counting register states
2. Encode: Controlled-\(U^{2^j}\) operations use phase kickback to stamp the eigenvalue phase \(\theta\) onto each counting qubit. The result is a "messy wave" — all basis states have equal probability, but each has a different phase. The amplitudes form a periodic pattern with frequency related to \(\theta\).
3. Decode: \(\text{QFT}^{-1}\) converts that periodic phase pattern into a single spike — one basis state with high amplitude. This is the Fourier transform doing its core job: messy signal in, clean frequency spike out.
4. Read: Measure the counting register. The spike location gives you \(\theta\) (or the closest \(t\)-bit approximation).

Note that the forward QFT is never explicitly applied in QPE. The controlled-\(U\) gates implicitly create the QFT-encoded state through phase kickback. Only QFT\(^{-1}\) is applied as an actual circuit operation.

6. Quantum Phase Estimation (QPE)

QPE is arguably the most important subroutine in quantum computing. It underlies Shor's factoring algorithm, quantum simulation, and many other applications.

The circuit has two registers:

• Counting register: \(t\) qubits, initialized to \(\ket{0}^{\otimes t}\) — determines the precision of the estimate
• Eigenstate register: holds \(\ket{\psi}\) (the eigenstate of \(U\))

|0⟩ ─── H ────────────────── ● ────────────── QFT† ─── Measure
|0⟩ ─── H ──────────── ● ──── │ ────────────── QFT† ─── Measure
|0⟩ ─── H ────── ● ──── │ ──── │ ────────────── QFT† ─── Measure
                    │      │      │
|ψ⟩ ──────────── U¹ ── U² ── U⁴ ──────────────────────────────

The steps are:

1. Apply \(H\) to all counting qubits
2. Apply controlled-\(U^{2^j}\) from counting qubit \(j\) to the eigenstate register (for \(j = 0, 1, \ldots, t-1\))
3. Apply \(\text{QFT}^\dagger\) to the counting register
4. Measure the counting register

We'll trace both the general formula and a concrete example (\(U = T\)-gate, \(\ket{\psi} = \ket{1}\), \(t = 3\) counting qubits, \(\theta = 1/8\)) side by side.

Step 1: Hadamard on counting register

T-gate example: \(\ket{000}\ket{1} \xrightarrow{H^{\otimes 3}} \frac{1}{\sqrt{8}}(\ket{0} + \ket{1} + \cdots + \ket{7})\ket{1}\). All 8 counting states in equal superposition, eigenstate \(\ket{1}\) sits untouched.

Step 2: Controlled-\(U\) operations

The controlled-\(U^{2^j}\) gate, controlled by counting qubit \(j\), acts as:

Because \(\ket{\psi}\) is an eigenstate, \(U^{2^j}\ket{\psi} = (e^{2\pi i\theta})^{2^j}\ket{\psi} = e^{2\pi i \theta \cdot 2^j}\ket{\psi}\). The eigenstate is unchanged — all the information goes into the phase of the counting qubit. This is phase kickback again.

After all \(t\) controlled operations, counting qubit \(j\) has picked up phase \(e^{2\pi i \theta \cdot 2^j}\) on its \(\ket{1}\) component. The combined state is:

T-gate example: The counting register is \(\frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2\pi i k/8} \ket{k}\). Write out: \(\frac{1}{\sqrt{8}}(\ket{0} + e^{i\pi/4}\ket{1} + e^{i\pi/2}\ket{2} + e^{i3\pi/4}\ket{3} + e^{i\pi}\ket{4} + e^{i5\pi/4}\ket{5} + e^{i3\pi/2}\ket{6} + e^{i7\pi/4}\ket{7})\). Every state equally likely to be measured — the answer is hidden in the phases.

Step 3: Apply QFT\(^\dagger\) to the counting register

The inverse QFT undoes the QFT, leaving us with the state \(\ket{2^t\theta}\) in the counting register.

T-gate: QFT\(^\dagger\)(QFT\(\ket{001}\)) = \(\ket{001}\). All 8 phases interfere — 7 cancel (destructive), 1 survives (constructive). The state collapses from "8 states with different phases" to "1 state with certainty."

Step 4: Measure the counting register

We measure and obtain the integer \(m = 2^t\theta\). Therefore:

T-gate: Measure \(\ket{001}\) → \(m = 1\). So \(\theta = 1/8\), and the eigenvalue is \(e^{2\pi i/8} = e^{i\pi/4}\). Done — we recovered the T-gate's eigenvalue phase with certainty.

In general, \(2^t\theta\) may not be an integer. Then the state after QFT\(^\dagger\) is a superposition peaked around the nearest integer(s) to \(2^t\theta\):

• The probability of measuring the closest integer to \(2^t\theta\) is at least \(\frac{4}{\pi^2} \approx 0.405\) (about 40%)
• Adding more counting qubits increases precision: \(t\) qubits give an estimate accurate to within \(\pm 1/2^t\)
• To estimate \(\theta\) to \(n\) bits of accuracy with probability \(> 1 - \epsilon\), use \(t = n + \lceil \log_2(2 + 1/(2\epsilon)) \rceil\) counting qubits

7. QPE Example: T-Gate Phase Estimation

Let's work through a concrete example. Take \(U = T\) (the \(\pi/8\) gate) and \(\ket{\psi} = \ket{1}\).

The eigenvalues of \(T\): \(\ket{0}\) has eigenvalue 1 (i.e., \(\theta_0 = 0\)) and \(\ket{1}\) has eigenvalue \(e^{i\pi/4} = e^{2\pi i/8}\) (i.e., \(\theta_1 = 1/8\)).

Using \(t = 3\) counting qubits and \(\ket{\psi} = \ket{1}\):

1. \(2^t \cdot \theta = 2^3 \cdot \frac{1}{8} = 1\) — this is an integer, so we get an exact result!
2. The measurement outcome is \(m = 1\), i.e., we measure \(\ket{001}\)
3. Therefore \(\theta = m/2^t = 1/8\), and the eigenvalue is \(e^{2\pi i/8} = e^{i\pi/4}\)

8. Why QPE Matters

At first glance, QPE seems circular: "we need to know the eigenstate \(\ket{\psi}\) and be able to implement controlled-\(U\), so don't we already know everything?" Not quite.

Shor's algorithm for factoring \(N\):

1. Pick random \(a < N\)
2. Use QPE to find the period \(r\) of \(f(x) = a^x \bmod N\)
3. Use \(r\) to find factors of \(N\) (classical post-processing)

QPE finds \(r\) by estimating the eigenvalues of the unitary \(U: \ket{y} \mapsto \ket{ay \bmod N}\). The eigenvalues are \(e^{2\pi i s/r}\) for \(s = 0, 1, \ldots, r-1\), so measuring gives an estimate of \(s/r\), from which \(r\) can be extracted using continued fractions.

9. Connection to Previous Algorithms

The progression of algorithms in this course follows a clear arc:

Algorithm	Encoder	Phase Source	Decoder
Deutsch-Jozsa	\(H^{\otimes n}\)	Phase oracle \((-1)^{f(x)}\)	\(H^{\otimes n}\)
Bernstein-Vazirani	\(H^{\otimes n}\)	Phase oracle \((-1)^{s \cdot x}\)	\(H^{\otimes n}\)
Simon's	\(H^{\otimes n}\)	Boolean oracle + measurement	\(H^{\otimes n}\)
QPE / Shor's	\(H^{\otimes t}\)	Controlled-\(U^{2^j}\) (eigenvalue phases)	\(\text{QFT}^\dagger\)

The key evolution: the first three algorithms use \(H^{\otimes n}\) as both encoder and decoder (because \(H = H^\dagger\), the Hadamard is its own inverse). QPE upgrades the decoder to the full inverse QFT, which can handle the richer phase structure of eigenvalue problems.

10. Exam Checklist