Chapter 14: The Quantum Fourier Transform — The Mathematical Engine Inside the Most Important Quantum Algorithms

"The QFT is not a faster way to compute the classical Fourier transform. It is something far more profound: a way to place the Fourier transform of a vector into the amplitudes of a quantum state — exponentially compact, and ready for quantum interference."

Learning Objectives

After completing this chapter, you will be able to:

• Derive the Quantum Fourier Transform (QFT) from the classical Discrete Fourier Transform
• Express the QFT as a unitary matrix and verify its unitarity
• Construct the QFT circuit from Hadamard gates and controlled phase rotations
• Analyze the gate complexity: $O(n^2)$ for QFT vs. $O(n 2^n)$ for classical FFT
• Implement the QFT and inverse QFT in Qiskit
• Derive the product representation of the QFT from the definition
• Explain why the QFT alone does not provide a speedup (the measurement problem)
• Understand the QFT's role as a subroutine in phase estimation, Shor's algorithm, and quantum simulation
• Compute the QFT of specific states by hand and verify the results
• Analyze the approximate QFT and its trade-offs
• Connect the QFT to the broader framework of quantum algorithms

14.1 The Classical Discrete Fourier Transform: A Brief Review

The Discrete Fourier Transform (DFT) maps a vector of $N$ complex numbers $x_0, x_1, \ldots, x_{N-1}$ to another vector $y_0, y_1, \ldots, y_{N-1}$:

$$y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \, e^{-2\pi i j k / N}$$

Equivalently, using the $N$-th root of unity $\omega_N = e^{2\pi i / N}$:

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

The DFT is a linear transformation, represented by the $N \times N$ matrix $F_N$ with entries:

$$(F_N)_{jk} = \frac{1}{\sqrt{N}} \omega_N^{-jk}$$

The inverse DFT is:

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

14.1.1 Key Properties of the DFT

1. Linearity: The DFT is a linear transformation.
2. Unitarity: $F_N F_N^\dagger = I$, so the DFT preserves the $\ell^2$ norm (Parseval's theorem).
3. Periodicity detection: If $x_j$ is periodic with period $r$, then $|y_k|^2$ is concentrated at $k$ values that are multiples of $N/r$.
4. Convolution theorem: $\text{DFT}(x * y) = \text{DFT}(x) \cdot \text{DFT}(y)$, where $*$ denotes circular convolution.

Computational cost: The classical Fast Fourier Transform (FFT) computes the DFT in $O(N \log N)$ operations. For $N = 2^n$, this is $O(n 2^n)$.

Why This Matters: The QFT is the quantum analog of the DFT. It performs the same mathematical operation — but on quantum amplitudes rather than classical data. The exponential advantage comes from the fact that a quantum state of $n$ qubits encodes $2^n$ amplitudes, and the QFT transforms all of them in $O(n^2)$ gates. The catch is that we cannot read out all $2^n$ amplitudes — we can only measure the state and get one outcome.

14.2 The Quantum Fourier Transform: Definition

The Quantum Fourier Transform (QFT) on $n$ qubits ($N = 2^n$ basis states) is the unitary operator:

$$\text{QFT}_n |j\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i j k / 2^n} |k\rangle$$

where $j$ and $k$ are integers $0, 1, \ldots, 2^n-1$, and $|j\rangle$ is the computational basis state corresponding to the binary representation of $j$.

Key difference from classical DFT: The QFT acts on the amplitudes of a quantum state, not on an array of numbers. If the input state is $|\psi\rangle = \sum_{j=0}^{N-1} x_j |j\rangle$, then:

$$\text{QFT}_n |\psi\rangle = \sum_{j=0}^{N-1} x_j \, \text{QFT}_n |j\rangle = \sum_{k=0}^{N-1} \left( \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \, e^{2\pi i j k / N} \right) |k\rangle = \sum_{k=0}^{N-1} y_k |k\rangle$$

The output amplitudes $y_k$ are exactly the DFT of the input amplitudes $x_j$. The QFT transforms the amplitude vector of a quantum state.

Common Misconception: "The QFT computes the Fourier transform exponentially faster than the FFT"

The QFT uses $O(n^2)$ gates to transform $2^n$ amplitudes, compared to $O(n 2^n)$ operations for the FFT. But the QFT's output is a quantum state whose amplitudes are the Fourier transform — we cannot read out all $2^n$ amplitudes. Measurement gives only one outcome $k$ with probability $|y_k|^2$. The QFT is not a fast classical FFT; it is a quantum subroutine that must be embedded in a larger algorithm.

14.2.1 The QFT Matrix for Small n

The QFT matrix (n=1, N=2):

$$\text{QFT}_1 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = H$$

For a single qubit, the QFT is exactly the Hadamard gate. This connects the QFT directly to the Hadamard transform we studied in Chapters 11 and 12.

The QFT matrix (n=2, N=4):

$$\text{QFT}_2 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix}$$

Let us verify this is unitary: $\text{QFT}_2 \cdot \text{QFT}_2^\dagger = I$.

$(\text{QFT}_2 \cdot \text{QFT}_2^\dagger)_{00} = \frac{1}{4}(1 + 1 + 1 + 1) = 1$ ✓

$(\text{QFT}_2 \cdot \text{QFT}_2^\dagger)_{01} = \frac{1}{4}(1 + i \cdot (-i) + (-1) \cdot (-1) + (-i) \cdot i) = \frac{1}{4}(1 + 1 - 1 + 1)$... wait, let me recompute.

Actually, let me verify unitarity by checking that the rows are orthonormal. Row 0: $(1, 1, 1, 1)/2$. Row 1: $(1, i, -1, -i)/2$. Inner product: $\frac{1}{4}(1 \cdot 1 + 1 \cdot (-i) + 1 \cdot (-1) + 1 \cdot i) = \frac{1}{4}(1 - i - 1 + i) = 0$ ✓.

The QFT matrix (n=3, N=8):

$$\text{QFT}_3 = \frac{1}{\sqrt{8}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^2 & \omega^3 & \omega^4 & \omega^5 & \omega^6 & \omega^7 \\ 1 & \omega^2 & \omega^4 & \omega^6 & 1 & \omega^2 & \omega^4 & \omega^6 \\ 1 & \omega^3 & \omega^6 & \omega & \omega^4 & \omega^7 & \omega^2 & \omega^5 \\ 1 & \omega^4 & 1 & \omega^4 & 1 & \omega^4 & 1 & \omega^4 \\ 1 & \omega^5 & \omega^2 & \omega^7 & \omega^4 & \omega & \omega^6 & \omega^3 \\ 1 & \omega^6 & \omega^4 & \omega^2 & 1 & \omega^6 & \omega^4 & \omega^2 \\ 1 & \omega^7 & \omega^6 & \omega^5 & \omega^4 & \omega^3 & \omega^2 & \omega \end{pmatrix}$$

where $\omega = e^{2\pi i / 8} = e^{\pi i / 4}$.

14.2.2 Unitarity of the QFT

The QFT is unitary: $\text{QFT}_n \cdot \text{QFT}_n^\dagger = I$.

Proof: The $(j, k)$ entry of $\text{QFT}_n \cdot \text{QFT}_n^\dagger$ is:

$$(\text{QFT}_n \cdot \text{QFT}_n^\dagger)_{jk} = \frac{1}{2^n} \sum_{m=0}^{2^n-1} e^{2\pi i j m / 2^n} \cdot e^{-2\pi i k m / 2^n} = \frac{1}{2^n} \sum_{m=0}^{2^n-1} e^{2\pi i (j-k) m / 2^n}$$

By the geometric series formula (or the orthogonality of characters of $\mathbb{Z}_{2^n}$):

$$\sum_{m=0}^{2^n-1} e^{2\pi i (j-k) m / 2^n} = \begin{cases} 2^n & \text{if } j = k \\ 0 & \text{if } j \neq k \end{cases}$$

Therefore $(\text{QFT}_n \cdot \text{QFT}_n^\dagger)_{jk} = \delta_{jk}$, confirming unitarity.

Recurring Theme — Quantum is Linear Algebra, Not Magic: The QFT is a unitary matrix. Its action on quantum states is just matrix-vector multiplication. The "magic" of the QFT is not in the physics — it is in the fact that this particular unitary transformation reveals periodic structure in amplitudes, and it can be implemented efficiently on a quantum computer.

14.3 The Product Representation

The most useful form of the QFT for circuit construction is the product representation. Write $j$ in binary: $j = j_1 j_2 \ldots j_n$ where $j_1$ is the most significant bit. The integer value is $j = j_1 2^{n-1} + j_2 2^{n-2} + \cdots + j_n 2^0$. Using binary fractions $0.j_\ell j_{\ell+1} \ldots j_n = j_\ell/2 + j_{\ell+1}/4 + \cdots + j_n/2^{n-\ell+1}$:

$$\text{QFT}_n |j_1 j_2 \ldots j_n\rangle = \frac{1}{\sqrt{2^n}} \bigotimes_{\ell=1}^{n} \left( |0\rangle + e^{2\pi i \, 0.j_\ell j_{\ell+1} \ldots j_n} |1\rangle \right)$$

Expanded:

$$\text{QFT}_n |j\rangle = \frac{1}{\sqrt{2^n}} \left( |0\rangle + e^{2\pi i \, 0.j_n} |1\rangle \right) \otimes \left( |0\rangle + e^{2\pi i \, 0.j_{n-1} j_n} |1\rangle \right) \otimes \cdots \otimes \left( |0\rangle + e^{2\pi i \, 0.j_1 j_2 \ldots j_n} |1\rangle \right)$$

This is the key insight: The QFT decomposes into a product of single-qubit states, each depending on a subset of the input bits. The first qubit (most significant) depends on all $n$ bits; the last qubit depends only on $j_n$.

14.3.1 Derivation of the Product Representation

Starting from the definition:

$$\text{QFT}_n |j\rangle = \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i j k / 2^n} |k\rangle$$

Write $k$ in binary: $k = k_1 2^{n-1} + k_2 2^{n-2} + \cdots + k_n 2^0 = k_1 k_2 \ldots k_n$.

$$|k\rangle = |k_1\rangle \otimes |k_2\rangle \otimes \cdots \otimes |k_n\rangle$$

The exponent becomes:

$$e^{2\pi i j k / 2^n} = e^{2\pi i j (k_1 2^{n-1} + k_2 2^{n-2} + \cdots + k_n 2^0) / 2^n}$$

$$= e^{2\pi i j k_1 / 2} \cdot e^{2\pi i j k_2 / 4} \cdots e^{2\pi i j k_n / 2^n}$$

$$= \prod_{\ell=1}^{n} e^{2\pi i j k_\ell / 2^\ell}$$

Now, $j / 2^\ell$ in binary fraction notation is $0.j_1 j_2 \ldots j_n$ truncated to $n - \ell + 1$ bits after the point, plus an integer part that doesn't affect the phase (since $e^{2\pi i \cdot \text{integer}} = 1$). So:

$$e^{2\pi i j k_\ell / 2^\ell} = e^{2\pi i \cdot 0.j_{n-\ell+1} j_{n-\ell+2} \ldots j_n \cdot k_\ell}$$

Wait, let me be more careful. We have:

$$j k_\ell / 2^\ell = k_\ell \cdot j / 2^\ell$$

And $j / 2^\ell$ can be decomposed as:

$$j / 2^\ell = \lfloor j / 2^\ell \rfloor + \{j / 2^\ell\}$$

where $\{j / 2^\ell\}$ is the fractional part. The integer part contributes $e^{2\pi i \cdot \text{integer}} = 1$. The fractional part $\{j / 2^\ell\}$ is exactly $0.j_{n-\ell+1} j_{n-\ell+2} \ldots j_n$... hmm, let me reconsider.

Actually, let me use the standard notation. We write $j = j_1 2^{n-1} + j_2 2^{n-2} + \cdots + j_n$ where $j_1$ is the MSB. Then:

$$j \cdot k_\ell / 2^\ell$$

We need $e^{2\pi i j k_\ell / 2^\ell}$. Since $e^{2\pi i m} = 1$ for integer $m$, we only need the fractional part of $j / 2^\ell$.

$j / 2^\ell = j_\ell 2^{n-\ell-1} + j_{\ell+1} 2^{n-\ell-2} + \cdots + j_n 2^0 + j_1 2^{n-\ell-1} + \cdots$

Actually, let me just use the standard result. The key identity is:

$$j \cdot k_\ell / 2^\ell \equiv 0.j_{n-\ell+1} j_{n-\ell+2} \ldots j_n \pmod{1}$$

Wait, I'm confusing the indexing. Let me use the convention from Nielsen & Chuang, where $j = j_1 j_2 \ldots j_n$ (MSB first).

$$\text{QFT}_n |j_1 j_2 \ldots j_n\rangle = \frac{1}{\sqrt{2^n}} \bigotimes_{\ell=1}^{n} \left( |0\rangle + e^{2\pi i \, 0.j_\ell j_{\ell+1} \ldots j_n} |1\rangle \right)$$

The $\ell$-th output qubit depends on bits $j_\ell, j_{\ell+1}, \ldots, j_n$ of the input. The most significant output qubit ($\ell = 1$) depends on all input bits, while the least significant output qubit ($\ell = n$) depends only on $j_n$.

Important note: The product representation produces the qubits in reverse order. The first qubit (MSB of the output) is $\left(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 \ldots j_n}|1\rangle\right)$, which depends on all input bits. But in the standard circuit, this becomes the MSB of the output, which requires SWAP gates to correct.

14.3.2 Worked Example: QFT of |5⟩ for n=3

Compute $\text{QFT}_3|5\rangle$, where $5 = 101$ in binary ($j_1 = 1, j_2 = 0, j_3 = 1$).

Using the product representation:

$$\text{QFT}_3|101\rangle = \frac{1}{\sqrt{8}} \left( |0\rangle + e^{2\pi i \cdot 0.101}|1\rangle \right) \otimes \left( |0\rangle + e^{2\pi i \cdot 0.01}|1\rangle \right) \otimes \left( |0\rangle + e^{2\pi i \cdot 0.1}|1\rangle \right)$$

Now, $0.101$ in binary $= 1/2 + 0/4 + 1/8 = 5/8$, so $e^{2\pi i \cdot 5/8} = e^{5\pi i/4}$.

$0.01$ in binary $= 0/2 + 1/4 = 1/4$, so $e^{2\pi i \cdot 1/4} = e^{\pi i/2} = i$.

$0.1$ in binary $= 1/2$, so $e^{2\pi i \cdot 1/2} = e^{\pi i} = -1$.

$$\text{QFT}_3|5\rangle = \frac{1}{\sqrt{8}} \left( |0\rangle + e^{5\pi i/4}|1\rangle \right) \otimes \left( |0\rangle + i|1\rangle \right) \otimes \left( |0\rangle - |1\rangle \right)$$

Let me verify this by computing the full QFT matrix applied to $|5\rangle$. The 5th column of $\text{QFT}_3$ (0-indexed, so the column for $j = 5$) gives:

$$\text{QFT}_3|5\rangle = \frac{1}{\sqrt{8}} \sum_{k=0}^{7} \omega^{5k} |k\rangle$$

where $\omega = e^{2\pi i / 8} = e^{\pi i / 4}$.

For $k = 0$: $\omega^0 = 1$ For $k = 1$: $\omega^5 = e^{5\pi i/4}$ For $k = 2$: $\omega^{10} = e^{10\pi i/4} = e^{5\pi i/2} = e^{\pi i/2} = i$ For $k = 3$: $\omega^{15} = e^{15\pi i/4} = e^{7\pi i/4}$ For $k = 4$: $\omega^{20} = e^{5\pi i} = e^{\pi i} = -1$ For $k = 5$: $\omega^{25} = e^{25\pi i/4} = e^{\pi i/4}$ For $k = 6$: $\omega^{30} = e^{30\pi i/4} = e^{7\pi i/2} = e^{3\pi i/2} = -i$ For $k = 7$: $\omega^{35} = e^{35\pi i/4} = e^{3\pi i/4}$

This gives $\text{QFT}_3|5\rangle = \frac{1}{\sqrt{8}}(|0\rangle + e^{5\pi i/4}|1\rangle + i|2\rangle + e^{7\pi i/4}|3\rangle - |4\rangle + e^{\pi i/4}|5\rangle - i|6\rangle + e^{3\pi i/4}|7\rangle)$.

Try It Yourself: Compute $\text{QFT}_2|2\rangle$ using the product representation. Verify that the result matches the matrix-vector product with the QFT matrix for $n = 2$.

14.4 QFT Circuit Construction

The product representation directly yields a circuit. We build it qubit by qubit, from most significant to least significant.

Step-by-step construction for $n=3$:

Step 1 — Qubit 1 (MSB): |j_1⟩ --[H]--[R_2]--[R_3]--•----------------
                               |      |             |
Step 2 — Qubit 2:      |j_2⟩ --------•------[H]--[R_2]--•-----------
                                                      |      |
Step 3 — Qubit 3 (LSB): |j_3⟩ ---------------------------•------[H]--

where R_k = |0⟩⟨0| + e^{2πi/2^k} |1⟩⟨1| = diag(1, e^{2πi/2^k})

How the circuit works:

1. First qubit (MSB): Apply $H$ to $|j_1\rangle$, producing $\frac{1}{\sqrt{2}}(|0\rangle + (-1)^{j_1}|1\rangle)$. Wait, actually $H|j_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle + (-1)^{j_1}|1\rangle)$. But the product representation says the first qubit should be $\frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 \ldots j_n}|1\rangle)$. The Hadamard gives the $j_1$-dependent phase, and the controlled rotations add the $j_2, \ldots, j_n$-dependent phases.

More precisely: after $H$ on qubit 1, the state is $\frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i \cdot j_1/2}|1\rangle)$. Then the controlled-$R_2$ from qubit 2 adds $2\pi i \cdot j_2/4$ to the phase when $j_2 = 1$. The controlled-$R_3$ from qubit 3 adds $2\pi i \cdot j_3/8$. After all controlled rotations, the phase is $2\pi i (j_1/2 + j_2/4 + j_3/8) = 2\pi i \cdot 0.j_1 j_2 j_3$.

2. Second qubit: Apply $H$ to $|j_2\rangle$, producing $\frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i \cdot j_2/2}|1\rangle)$. The controlled-$R_2$ from qubit 3 adds $2\pi i \cdot j_3/4$. The total phase is $2\pi i (j_2/2 + j_3/4) = 2\pi i \cdot 0.j_2 j_3$.

3. Third qubit (LSB): Apply $H$ to $|j_3\rangle$, producing $\frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i \cdot j_3/2}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i \cdot 0.j_3}|1\rangle)$. No controlled rotations needed.

Full QFT circuit for $n$ qubits:

     ┌───┐ ┌─────────────┐ ┌─────────────┐       ┌─────────────┐
q_0: ┤ H ├─┤ R_2(θ=π/2)  ├─┤ R_3(θ=π/4)  ├─ ... ─┤ R_n(θ=π/2^{n-1}) ├───────────────────────────
     └───┘ └──────┬──────┘ └──────┬──────┘       └──────┬──────┘
                  │               │                      │
q_1: ─────────────■───────────────┼──────────────────────┼───────────┌───┐ ┌─────────────┐
                                  │                      │           ┤ H ├─┤ R_2(θ=π/2)  ├─ ... 
                                  │                      │           └───┘ └──────┬──────┘
q_2: ─────────────────────────────■──────────────────────┼───────────────────────■────────────
                                                         │
...                                                      │
                                                          │
q_{n-1}: ────────────────────────────────────────────────■────────────────────────────────────
                                                                                      ┌───┐
q_n: ─────────────────────────────────────────────────────────────────────────────────┤ H ├──────────
                                                                                      └───┘

The controlled phase gate $R_k$:

$$R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^k} \end{pmatrix}$$

$R_2 = S$ (phase gate), $R_3 = T$ ($\pi/8$ gate), $R_4 = \text{diag}(1, e^{\pi i/8})$, etc.

Gate count: - $n$ Hadamard gates - $n(n-1)/2$ controlled phase gates - Total: $O(n^2)$ gates

SWAP gates at the end: The product representation produces the qubits in reverse order (LSB first). To get the standard ordering, we apply $\lfloor n/2 \rfloor$ SWAP gates at the end. Each SWAP can be decomposed into 3 CNOT gates, adding $O(n)$ more gates.

14.4.1 Detailed Circuit for n=3

     ┌───┐ ┌─────────┐ ┌─────────┐ ┌───┐
q_0: ┤ H ├─┤ R_2(S)  ├─┤ R_3(T)  ├─┤ × ├───
     └───┘ └────┬────┘ └────┬────┘ └─┬─┘
q_1: ────────────■──────────┼──────■─┤ × ├───
                            │       │ └─┬─┘
q_2: ───────────────────────■───────┼───■───┤ H ├
                                    │       └───┘

Wait, let me draw this more carefully for $n = 3$:

       ┌───┐   ┌──────┐  ┌──────┐                      ┌───┐
q_0: ──┤ H ├───┤ CR_2 ├──┤ CR_3 ├──────────────────────╲╱──┤SWAP│──
       └───┘   └───┬───┘  └───┬──┘                      ╱╲  └──┬─┘
q_1: ──────────────■──────────┼─────────┌───┐ ┌──────┐╲╱─────│──
                              │         ┤ H ├─┤ CR_2 ├────────┤──
q_2: ─────────────────────────■─────────└───┘ └──┬───┘────────┘──
                                                ■──────────────

After the SWAP, the output qubits are in the correct order.

14.4.2 Gate Decomposition of Controlled Phase Gates

Each controlled-$R_k$ gate can be decomposed into elementary gates:

• Controlled-$R_2$ (= C-S gate): a standard 2-qubit gate
• Controlled-$R_3$ (= C-T gate): a standard 2-qubit gate
• Controlled-$R_k$ for $k > 3$: can be decomposed into CNOT and single-qubit gates

The total gate count after decomposition is still $O(n^2)$.

14.5 Complexity: QFT vs. Classical FFT

The crucial caveat: The QFT uses $O(n^2)$ gates to place the Fourier-transformed amplitudes into a quantum state, but measuring that state only gives one sample from the distribution $|y_k|^2$. You cannot read out all $N$ Fourier coefficients efficiently. This is why the QFT alone does not provide an exponential speedup for computing Fourier transforms — it must be embedded in a larger algorithm (phase estimation, Shor's) that extracts useful global information from the Fourier-transformed state.

Recurring Theme — Noise is the Enemy: The QFT requires precise controlled phase rotations $R_k$ with angles $2\pi/2^k$. For large $k$, these angles become extremely small ($R_{20}$ requires a rotation of $2\pi/2^{20} \approx 0.000006$ radians), and implementing them with high fidelity is challenging. The approximate QFT (Section 14.10) drops these tiny rotations with negligible impact on algorithm performance.

14.6 The Inverse Quantum Fourier Transform (IQFT)

The inverse QFT is the Hermitian conjugate of the QFT:

$$\text{IQFT}_n |k\rangle = \frac{1}{\sqrt{2^n}} \sum_{j=0}^{2^n-1} e^{-2\pi i j k / 2^n} |j\rangle$$

The circuit for IQFT is the QFT circuit run in reverse, with all phase rotations negated (or equivalently, with $R_k^\dagger$ gates):

     ┌───┐┌─────────┐┌─────────┐     ┌─────────┐
q_0: ┤ H ├┤ R_2^{-1} ├┤ R_3^{-1} ├─...─┤ R_n^{-1} ├
     └───┘└────┬─────┘└────┬─────┘     └────┬─────┘
               │           │               │
q_1: ──────────■────────────┼───────────────┼──[H]──[R_2^{-1}]──...
                            │               │
q_2: ───────────────────────■───────────────┼────────────────────
                                            │
...                                         │
q_n: ───────────────────────────────────────■────────────────[H]─

The IQFT is essential for algorithms like phase estimation, where we need to convert a Fourier-basis state back to the computational basis.

14.6.1 Explicit IQFT Circuit for n=3

              ┌─────────┐ ┌─────────┐ ┌───┐
q_2: ─[H]────┤ CR_3^{-1} ├─┤ CR_2^{-1} ├─┤SWAP│──
              └────┬────┘ └────┬────┘ └──┬─┘
q_1: ──────[H]─────■──────────┼──────■────┤SWAP│──
                             │           └──┬─┘
q_0: ──────[H]──────────────■──────────────┘──

Note the reverse order of operations compared to the QFT: we start with the last qubit (LSB) and work backward.

14.6.2 Verifying QFT · IQFT = Identity

The QFT followed by the IQFT should return the original state. We can verify this in Qiskit:

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
from qiskit_aer import AerSimulator
import numpy as np

def verify_qft_iqft(n):
    """Verify that QFT · IQFT = I for n qubits."""
    # Prepare a random state
    qc = QuantumCircuit(n)
    # Use H gates and some rotations to create a non-trivial state
    for i in range(n):
        qc.h(i)
        qc.rz(np.random.random() * 2 * np.pi, i)

    state_before = Statevector(qc)

    # Apply QFT then IQFT
    # (In practice, we'd use our qft_circuit and iqft_circuit functions)
    # For now, we verify mathematically

    # The QFT matrix
    N = 2**n
    QFT = np.zeros((N, N), dtype=complex)
    for j in range(N):
        for k in range(N):
            QFT[j, k] = np.exp(2j * np.pi * j * k / N) / np.sqrt(N)

    # Verify unitarity
    product = QFT @ QFT.conj().T
    identity_error = np.max(np.abs(product - np.eye(N)))

    print(f"QFT · QFT† - I (max error): {identity_error:.2e}")
    print(f"This should be approximately 0 (machine precision).")

verify_qft_iqft(3)

14.7 Period Finding Intuition

The QFT's power comes from its ability to reveal periodicity. Consider a state with period $r$:

$$|\psi\rangle = \frac{1}{\sqrt{m}} \sum_{\ell=0}^{m-1} |x_0 + \ell r\rangle$$

where $m \approx N/r$. Applying the QFT:

$$\text{QFT}|\psi\rangle = \frac{1}{\sqrt{mN}} \sum_{\ell=0}^{m-1} \sum_{k=0}^{N-1} e^{2\pi i (x_0 + \ell r) k / N} |k\rangle$$

$$= \frac{1}{\sqrt{mN}} \sum_{k=0}^{N-1} e^{2\pi i x_0 k / N} \left( \sum_{\ell=0}^{m-1} e^{2\pi i \ell r k / N} \right) |k\rangle$$

The inner sum is a geometric series. It constructively interferes when $e^{2\pi i r k / N} \approx 1$, i.e., when $rk/N$ is close to an integer. This happens when $k \approx c N / r$ for integer $c$. The QFT concentrates amplitude on states $|k\rangle$ where $k$ is approximately a multiple of $N/r$.

14.7.1 Detailed Calculation of the Geometric Series

The inner sum is:

$$\sum_{\ell=0}^{m-1} e^{2\pi i \ell r k / N} = \frac{1 - e^{2\pi i m r k / N}}{1 - e^{2\pi i r k / N}}$$

This sum is large when $e^{2\pi i r k / N} \approx 1$, i.e., when $rk/N \approx$ integer, which occurs when $k \approx cN/r$ for integer $c = 0, 1, \ldots, r-1$.

At these values of $k$, the numerator $1 - e^{2\pi i m r k / N}$ can also be small (when $m = N/r$, it's $1 - e^{2\pi i k} = 0$ — but $k$ might not be exactly a multiple of $N/r$). The key point is that the amplitude is concentrated near multiples of $N/r$.

Worked Example: Period-finding for $N = 8, r = 2, x_0 = 1$.

The state is $|\psi\rangle = \frac{1}{\sqrt{4}}(|1\rangle + |3\rangle + |5\rangle + |7\rangle)$ (states $1, 3, 5, 7$ with period 2).

Applying the QFT:

$$\text{QFT}|\psi\rangle = \frac{1}{\sqrt{32}} \sum_{k=0}^{7} e^{2\pi i k/8} (1 + e^{2\pi i \cdot 2k/8} + e^{2\pi i \cdot 4k/8} + e^{2\pi i \cdot 6k/8}) |k\rangle$$

Wait, let me be more careful. The state is $\frac{1}{2}(|1\rangle + |3\rangle + |5\rangle + |7\rangle)$.

$$\text{QFT}|\psi\rangle = \frac{1}{2} \cdot \frac{1}{\sqrt{8}} \sum_{k=0}^{7} (e^{2\pi i \cdot 1 \cdot k/8} + e^{2\pi i \cdot 3 \cdot k/8} + e^{2\pi i \cdot 5 \cdot k/8} + e^{2\pi i \cdot 7 \cdot k/8}) |k\rangle$$

$$= \frac{1}{4\sqrt{2}} \sum_{k=0}^{7} e^{2\pi i k/8} (1 + e^{2\pi i \cdot 2k/8} + e^{2\pi i \cdot 4k/8} + e^{2\pi i \cdot 6k/8}) |k\rangle$$

For $k$ even ($k = 0, 2, 4, 6$): $e^{2\pi i \cdot 2k/8} = e^{2\pi i \cdot k/4}$. Since $k$ is even, $2k/4 = k/2$ is an integer, so $e^{2\pi i \cdot k/2} = 1$ for $k = 0, 2, 4, 6$... Actually, let me compute this more carefully.

For $k = 0$: inner sum $= 1 + 1 + 1 + 1 = 4$, total $= \frac{1}{4\sqrt{2}} \cdot 4 = \sqrt{2}$

For $k = 1$: inner sum $= e^{2\pi i/8}(1 + e^{2\pi i \cdot 2/8} + e^{2\pi i \cdot 4/8} + e^{2\pi i \cdot 6/8})$. Let me compute: $1 + e^{i\pi/2} + e^{i\pi} + e^{3i\pi/2} = 1 + i - 1 - i = 0$.

For $k = 2$: inner sum $= e^{2\pi i \cdot 2/8}(1 + e^{2\pi i \cdot 4/8} + e^{2\pi i \cdot 8/8} + e^{2\pi i \cdot 12/8}) = e^{i\pi/2}(1 + e^{i\pi} + e^{2i\pi} + e^{3i\pi}) = i(1 - 1 + 1 - 1) = 0$.

Hmm, that's also 0. Let me recompute.

Actually, let me use a different approach. The state $\frac{1}{2}(|1\rangle + |3\rangle + |5\rangle + |7\rangle)$ consists of the odd basis states. In the Fourier domain, this is:

$$\frac{1}{2} \cdot \frac{1}{\sqrt{8}} \sum_{k=0}^{7} \sum_{j \in \{1,3,5,7\}} e^{2\pi i j k/8} |k\rangle = \frac{1}{4\sqrt{2}} \sum_{k} S_k |k\rangle$$

where $S_k = \sum_{j \in \{1,3,5,7\}} e^{2\pi i j k/8}$.

$S_k = e^{2\pi i k/8} + e^{6\pi i k/8} + e^{10\pi i k/8} + e^{14\pi i k/8}$

$= e^{2\pi i k/8}(1 + e^{4\pi i k/8} + e^{8\pi i k/8} + e^{12\pi i k/8})$

$= e^{2\pi i k/8}(1 + e^{i\pi k/2} + e^{i\pi k} + e^{3i\pi k/2})$

For $k = 0$: $e^{0}(1 + 1 + 1 + 1) = 4$ For $k = 2$: $e^{i\pi/2}(1 + e^{i\pi} + e^{2i\pi} + e^{3i\pi}) = i(1 - 1 + 1 - 1) = 0$ For $k = 4$: $e^{i\pi}(1 + e^{2i\pi} + e^{4i\pi} + e^{6i\pi}) = (-1)(1 + 1 + 1 + 1) = -4$

Hmm, this gives amplitudes concentrated at $k = 0$ and $k = 4$, which are multiples of $N/r = 8/2 = 4$. This is consistent with the theory: the QFT concentrates amplitude at multiples of $N/r$.

For the odd-$j$ state (which has period 2 starting at $x_0 = 1$), the peaks are at $k = 0$ and $k = 4$ (i.e., multiples of $N/r = 4$), with a phase shift of $e^{2\pi i x_0 k/N}$.

Try It Yourself: For $N = 8$ and a state with period 4 ($|\psi\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |4\rangle)$), compute the QFT output and verify that the peaks are at $k = 0$ and $k = 2$ (multiples of $N/r = 2$).

This is the mechanism behind Shor's algorithm: The QFT transforms a periodic superposition into a state whose measurement reveals the period (via continued fractions). The same principle underlies quantum phase estimation.

14.8 Qiskit Implementation of QFT and IQFT

import numpy as np
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram
import math

def qft_circuit(n, inverse=False):
    """
    Construct the n-qubit Quantum Fourier Transform circuit.

    Args:
        n: Number of qubits
        inverse: If True, construct the inverse QFT

    Returns:
        QuantumCircuit implementing QFT (or IQFT)
    """
    qc = QuantumCircuit(n, name="IQFT" if inverse else "QFT")

    qubits = range(n)

    for i in range(n):
        # Hadamard on qubit i
        qc.h(i)

        # Controlled phase rotations
        for j in range(i + 1, n):
            # Phase = 2π / 2^{j-i+1}
            angle = 2 * np.pi / (2 ** (j - i + 1))
            if inverse:
                angle = -angle
            qc.cp(angle, j, i)  # control=j, target=i

    # Swap qubits to correct the bit order
    for i in range(n // 2):
        qc.swap(i, n - 1 - i)

    return qc

def iqft_circuit(n):
    """Construct the n-qubit inverse QFT circuit."""
    return qft_circuit(n, inverse=True)

# ─── Demonstration: QFT on a computational basis state ───

n = 4
N = 2**n

# Test with input state |j⟩ = |5⟩ (binary 0101)
j = 5
binary_j = format(j, f'0{n}b')
print(f"Input state: |{binary_j⟩ = |{j}⟩")
print(f"Expected QFT output: uniform magnitude with phases e^(2πi·{j}·k/{N})\n")

# Build circuit: prepare |j⟩, apply QFT, measure
qc = QuantumCircuit(n, n)

# Prepare |j⟩ = |0101⟩
for i, bit in enumerate(reversed(binary_j)):
    if bit == '1':
        qc.x(i)

qc.barrier()

# Apply QFT
qft = qft_circuit(n)
qc.compose(qft, inplace=True)

# Measure
qc.measure(range(n), range(n))

# Simulate
simulator = AerSimulator()
compiled = transpile(qc, simulator)
job = simulator.run(compiled, shots=8192)
result = job.result()
counts = result.get_counts()

print("QFT(|5⟩) measurement results (top 8):")
for state, count in sorted(counts.items(), key=lambda x: -x[1])[:8]:
    prob = count / 8192
    k = int(state, 2)
    expected_phase = (2 * np.pi * j * k / N) % (2 * np.pi)
    print(f"  |{state}⟩ (k={k:2d}): {count:5d} shots ({prob:.4f})  "
          f"expected phase: {expected_phase:.4f} rad")

# ─── Verify QFT · IQFT = Identity ───

print("\n─── Verifying QFT ∘ IQFT = I ───\n")

qc_test = QuantumCircuit(n, n)

# Prepare a superposition state
qc_test.h(range(n))
qc_test.barrier()

# Apply QFT then IQFT
qc_test.compose(qft_circuit(n), inplace=True)
qc_test.barrier()
qc_test.compose(iqft_circuit(n), inplace=True)

qc_test.measure(range(n), range(n))

compiled_test = transpile(qc_test, simulator)
job_test = simulator.run(compiled_test, shots=8192)
result_test = job_test.result()
counts_test = result_test.get_counts()

print("QFT ∘ IQFT applied to H^{⊗n}|0⟩:")
for state, count in sorted(counts_test.items(), key=lambda x: -x[1])[:5]:
    prob = count / 8192
    print(f"  |{state}⟩: {count:5d} shots ({prob:.4f})")

# The output should be approximately uniform (since H^{⊗n}|0⟩ is uniform
# and QFT ∘ IQFT = I, we get back the uniform superposition)
print("\n(Expected: approximately uniform distribution — QFT ∘ IQFT = I)")

Expected output:

Input state: |0101⟩ = |5⟩
Expected QFT output: uniform magnitude with phases e^(2πi·5·k/16)

QFT(|5⟩) measurement results (top 8):
  |0000⟩ (k= 0):   512 shots (0.0625)  expected phase: 0.0000 rad
  |0001⟩ (k= 1):   510 shots (0.0623)  expected phase: 1.9635 rad
  |0010⟩ (k= 2):   508 shots (0.0620)  expected phase: 3.9270 rad
  |0011⟩ (k= 3):   515 shots (0.0629)  expected phase: 5.8905 rad
  |0100⟩ (k= 4):   509 shots (0.0621)  expected phase: 1.5708 rad
  |0101⟩ (k= 5):   513 shots (0.0626)  expected phase: 3.5343 rad
  |0110⟩ (k= 6):   511 shots (0.0624)  expected phase: 5.4978 rad
  |0111⟩ (k= 7):   514 shots (0.0627)  expected phase: 1.0996 rad

─── Verifying QFT ∘ IQFT = I ───

QFT ∘ IQFT applied to H^{⊗n}|0⟩:
  |0000⟩:   520 shots (0.0635)
  |0001⟩:   508 shots (0.0620)
  |0010⟩:   515 shots (0.0629)
  |0011⟩:   510 shots (0.0623)
  |0100⟩:   512 shots (0.0625)

(Expected: approximately uniform distribution — QFT ∘ IQFT = I)

All 16 basis states are measured with approximately equal probability ($1/16 = 0.0625$), confirming that the QFT produces a state with uniform magnitude and that QFT followed by IQFT returns the original state.

14.8.1 Qiskit: QFT of a Periodic State

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
import numpy as np

def qft_periodic_state(n, period, offset=0):
    """
    Prepare a periodic state and apply the QFT.
    Period r: states |offset⟩, |offset+r⟩, |offset+2r⟩, ...
    """
    N = 2**n

    # Prepare periodic state
    qc = QuantumCircuit(n)

    # Create superposition of states with given period
    states = list(range(offset, N, period))
    amplitude = 1 / np.sqrt(len(states))

    # Initialize using state preparation
    for state in states:
        binary = format(state, f'0{n}b')
        for i, bit in enumerate(reversed(binary)):
            if bit == '1':
                qc.x(i)
        # This is a simplification; proper state preparation would use
        # amplitude encoding. For small n, we can use statevector.

    # For this demo, let's construct the statevector directly
    statevector = np.zeros(N, dtype=complex)
    for state in states:
        statevector[state] = 1 / np.sqrt(len(states))

    # Apply QFT to the statevector
    from qiskit.quantum_info import Statevector
    sv = Statevector(statevector)
    qft = qft_circuit(n)
    sv_transformed = sv.evolve(qft)

    # Display the result
    probs = np.abs(np.array(sv_transformed)) ** 2
    print(f"Periodic state with r={period}, offset={offset}, N={N}")
    print(f"Number of states in superposition: {len(states)}")
    print(f"Expected peaks at multiples of N/r = {N//period}")
    print(f"\nQFT output probabilities (top 8):")
    for idx in np.argsort(-probs)[:8]:
        binary = format(idx, f'0{n}b')
        print(f"  |{binary}⟩ (k={idx:3d}): {probs[idx]:.4f}  "
              f"({'peak' if idx % (N//period) == 0 else ''})")

# Test with a periodic state
qft_periodic_state(4, period=4, offset=0)
print()
qft_periodic_state(4, period=2, offset=1)

14.8.2 Qiskit: Statevector Simulation of QFT

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
import numpy as np

def qft_statevector_demo(n, input_state='computational_basis', j=0):
    """
    Demonstrate QFT on various input states using statevector simulation.
    """
    N = 2**n

    if input_state == 'computational_basis':
        # Prepare |j⟩
        qc = QuantumCircuit(n)
        binary_j = format(j, f'0{n}b')
        for i, bit in enumerate(reversed(binary_j)):
            if bit == '1':
                qc.x(i)
        state_before = Statevector(qc)
        print(f"Input: |{binary_j}⟩ = |{j}⟩")

    elif input_state == 'hadamard':
        # Prepare H^{⊗n}|0⟩ = uniform superposition
        qc = QuantumCircuit(n)
        qc.h(range(n))
        state_before = Statevector(qc)
        print(f"Input: H^⊗n|0⟩ (uniform superposition)")

    elif input_state == 'periodic':
        # Prepare a periodic state
        period = j  # repurpose j as period
        sv = np.zeros(N, dtype=complex)
        for i in range(0, N, period):
            sv[i] = 1.0
        sv /= np.linalg.norm(sv)
        state_before = Statevector(sv)
        print(f"Input: periodic state with period {period}")

    # Apply QFT
    qft = qft_circuit(n)
    state_after = state_before.evolve(qft)

    probs = np.abs(np.array(state_after)) ** 2
    phases = np.angle(np.array(state_after))

    print(f"\nQFT output (top 8 states by probability):")
    for idx in np.argsort(-probs)[:8]:
        if probs[idx] > 0.001:
            binary = format(idx, f'0{n}b')
            print(f"  |{binary}⟩ (k={idx:3d}): prob={probs[idx]:.4f}, "
                  f"phase={phases[idx]:.4f}")

# Test various inputs
print("=== QFT of |5⟩ (computational basis) ===")
qft_statevector_demo(4, 'computational_basis', j=5)

print("\n=== QFT of H^⊗n|0⟩ (uniform superposition) ===")
qft_statevector_demo(4, 'hadamard')

print("\n=== QFT of periodic state (period 4) ===")
qft_statevector_demo(4, 'periodic', j=4)

14.9 QFT as a Subroutine: The Bigger Picture

The QFT is rarely used as a standalone algorithm. Its power emerges when embedded in larger quantum algorithms:

1. Quantum Phase Estimation (Chapter 16): The QFT is the final step of phase estimation. After controlled unitary operations encode an eigenvalue $e^{2\pi i \phi}$ into the phases of a register, the IQFT converts this phase information into a computational basis state $|\phi\rangle$ that can be measured.

2. Shor's Algorithm (Chapter 15): The QFT transforms the periodic superposition created by modular exponentiation into a state whose measurement reveals the period $r$, which is then used to find factors.

3. Quantum Simulation (Chapter 17): The QFT can be used to diagonalize certain Hamiltonians, enabling efficient simulation of quantum systems.

4. Hidden Subgroup Problem: The QFT over abelian groups solves the abelian hidden subgroup problem, which generalizes period finding, discrete logarithm, and Simon's problem.

5. Quantum Counting: Combining Grover's algorithm with QFT-based phase estimation yields an algorithm for counting the number of solutions to a search problem.

Recurring Theme — Quantum Advantage is Problem-Specific: The QFT provides an exponential compression of Fourier information (from $O(n 2^n)$ classical operations to $O(n^2)$ quantum gates), but this information can only be extracted in limited ways. The genius of Shor's algorithm and phase estimation is that they extract specific global properties (the period or the phase) from the Fourier-transformed state, rather than trying to read out all $2^n$ amplitudes.

14.9.1 The QFT in the Algorithmic Template

Recall the quantum algorithmic template from Chapter 11:

The QFT is the $U_{\text{interference}}$ step in several algorithms:

• Deutsch-Jozsa / Bernstein-Vazirani: $U_{\text{interference}} = H^{\otimes n}$ (the QFT over $\mathbb{Z}_2^n$)
• Shor's algorithm: $U_{\text{interference}} = \text{QFT}_{2^n}$ (the QFT over $\mathbb{Z}_{2^n}$)
• Phase estimation: $U_{\text{interference}} = \text{IQFT}_{2^n}$ (the inverse QFT)

The pattern is consistent: encode information into phases, then use a Fourier transform to convert phase information into measurable computational basis information.

14.10 Approximate QFT

For large $n$, many of the controlled phase rotations involve extremely small angles ($\theta = 2\pi / 2^k$ for large $k$). These can be omitted with negligible impact on fidelity, yielding the approximate QFT with $O(n \log n)$ gates:

14.10.1 Bounded-Error Approximate QFT

The key observation is that controlled phase rotations $R_k$ with $k > m$ (for some cutoff $m$) have very small rotation angles and contribute negligibly to the output. Dropping these rotations reduces the gate count from $O(n^2)$ to $O(nm)$ while introducing an error that can be bounded.

Theorem (Coppersmith, 1994): If we keep only controlled rotations $R_k$ with $k \leq m$, the approximate QFT $\widetilde{\text{QFT}}_n$ satisfies:

$$\|\text{QFT}_n - \widetilde{\text{QFT}}_n\| \leq \frac{n}{2^{m+1}}$$

Choosing $m = O(\log n)$ gives error $O(1/\text{poly}(n))$, which is sufficient for most quantum algorithms.

14.10.2 Implementation of Approximate QFT

def approx_qft_circuit(n, precision=None):
    """
    Approximate QFT: drop phase rotations below a threshold.

    Args:
        n: Number of qubits
        precision: Maximum value of (j-i) for which we include R_k gates.
                   If None, use full QFT.
    """
    if precision is None:
        precision = n

    qc = QuantumCircuit(n, name=f"AQFT({precision})")

    for i in range(n):
        qc.h(i)
        for j in range(i + 1, min(i + 1 + precision, n)):
            angle = 2 * np.pi / (2 ** (j - i + 1))
            qc.cp(angle, j, i)

    for i in range(n // 2):
        qc.swap(i, n - 1 - i)

    return qc

14.10.3 Fidelity Analysis

The fidelity of the approximate QFT is:

$$F = |\langle \psi_{\text{exact}} | \psi_{\text{approx}} \rangle|^2 \geq 1 - \frac{n^2}{4 \cdot 2^{2(m+1)}}$$

where $m$ is the precision parameter. For $m = \lceil \log_2 n \rceil + 3$, the error is $O(1/n)$, which is negligible.

Worked Example: For $n = 8$ and $m = 4$, the approximate QFT keeps only $R_2, R_3, R_4, R_5$ rotations (dropping $R_6, R_7, R_8$). The error is at most $\frac{8}{2^5} = 0.25$, which may be too large. For $m = 6$, the error drops to $\frac{8}{2^7} = 0.0625$. For $m = 10$, the error is $\frac{8}{2^{11}} \approx 0.004$.

In practice, the approximate QFT is used in Shor's algorithm with $m = 2\log_2 n + O(1)$, which gives $O(n \log n)$ gates and error $O(1/n)$.

Common Misconception: "The approximate QFT is too inaccurate for practical use"

The approximate QFT introduces a small, controllable error that can be made exponentially small by keeping a logarithmic number of controlled rotations per qubit. In practice, the approximate QFT is sufficient for all known quantum algorithms, including Shor's factoring algorithm. The exact QFT is a theoretical ideal; the approximate QFT is what actually gets implemented.

14.11 Connection to the Hadamard Transform

The Hadamard transform $H^{\otimes n}$ is a special case of the QFT — specifically, the QFT over the group $\mathbb{Z}_2^n$. To see this, note that the characters of $\mathbb{Z}_2^n$ are $\chi_y(x) = (-1)^{x \cdot y}$, and the QFT over $\mathbb{Z}_2^n$ is:

$$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_y (-1)^{x \cdot y} |y\rangle$$

This is exactly the formula for the QFT with $N = 2$ (each qubit is treated independently), but with the group structure $\mathbb{Z}_2^n$ instead of $\mathbb{Z}_{2^n}$.

The key difference: - Hadamard transform ($\text{QFT over } \mathbb{Z}_2^n$): characters are $(-1)^{x \cdot y}$, phase rotations are $\pm 1$ only, implemented with Hadamard gates. - QFT over $\mathbb{Z}_{2^n}$: characters are $e^{2\pi i x y / 2^n}$, phase rotations can be any root of unity, implemented with Hadamard gates and controlled phase rotations.

The Hadamard transform is "free" — it requires only $n$ Hadamard gates. The full QFT over $\mathbb{Z}_{2^n}$ requires $O(n^2)$ gates. The additional gates (controlled phase rotations) are what enable the QFT to detect periods that the Hadamard transform cannot.

14.12 The Measurement Problem and the Power of the QFT

The QFT produces a state whose amplitudes are the Fourier transform of the input amplitudes. But measurement collapses this state to a single basis vector $|k\rangle$ with probability $|y_k|^2$. We cannot read out all $2^n$ Fourier coefficients.

This is the measurement problem — the fundamental barrier to using the QFT as a fast classical FFT. The QFT places exponentially many Fourier coefficients into a quantum state, but we can only extract $n$ bits of classical information from this state.

How algorithms circumvent the measurement problem:

1. Shor's algorithm: The QFT converts a periodic state (with a single dominant period $r$) into a state where most of the amplitude is concentrated on multiples of $N/r$. A single measurement gives $k \approx cN/r$ with high probability, from which $r$ can be extracted via continued fractions.

2. Phase estimation: The QFT converts a state $|\phi\rangle$ (where $\phi$ is encoded in the phases) into a computational basis state that directly encodes $\phi$ in binary. The entire phase is read out in a single measurement.

3. Deutsch-Jozsa / Bernstein-Vazirani: The Hadamard transform converts a phase pattern (which encodes a global property of $f$) into a measurement outcome that reveals this property. The measurement is "smart" — it extracts exactly the information we need.

The common pattern: the QFT is combined with other operations that concentrate the relevant information into a small number of amplitudes, so that measurement extracts exactly what we want.

Recurring Theme — We're at the Beginning: The QFT is one of the most powerful tools in the quantum algorithm designer's toolkit, and we are still discovering new ways to use it. Recent work on quantum machine learning, quantum chemistry, and quantum optimization has found novel applications of the QFT beyond factoring and phase estimation. The full potential of the QFT as a subroutine is far from exhausted.

14.13 The Measurement Problem and the Power of the QFT

The QFT produces a state whose amplitudes are the Fourier transform of the input amplitudes. But measurement collapses this state to a single basis vector $|k\rangle$ with probability $|y_k|^2$. We cannot read out all $2^n$ Fourier coefficients.

This is the measurement problem — the fundamental barrier to using the QFT as a fast classical FFT. The QFT places exponentially many Fourier coefficients into a quantum state, but we can only extract $n$ bits of classical information from this state.

How algorithms circumvent the measurement problem:

1. Shor's algorithm: The QFT converts a periodic state (with a single dominant period $r$) into a state where most of the amplitude is concentrated on multiples of $N/r$. A single measurement gives $k \approx cN/r$ with high probability, from which $r$ can be extracted via continued fractions.

2. Phase estimation: The QFT converts a state $|\phi\rangle$ (where $\phi$ is encoded in the phases) into a computational basis state that directly encodes $\phi$ in binary. The entire phase is read out in a single measurement.

3. Deutsch-Jozsa / Bernstein-Vazirani: The Hadamard transform converts a phase pattern (which encodes a global property of $f$) into a measurement outcome that reveals this property. The measurement is "smart" — it extracts exactly the information we need.

The common pattern: the QFT is combined with other operations that concentrate the relevant information into a small number of amplitudes, so that measurement extracts exactly what we want.

Recurring Theme — We're at the Beginning: The QFT is one of the most powerful tools in the quantum algorithm designer's toolkit, and we are still discovering new ways to use it. Recent work on quantum machine learning, quantum chemistry, and quantum optimization has found novel applications of the QFT beyond factoring and phase estimation. The full potential of the QFT as a subroutine is far from exhausted.

14.13.1 The Holevo Bound and the QFT

The Holevo bound states that $n$ qubits can encode at most $n$ bits of classical information. The QFT encodes $2^n$ Fourier coefficients in $n$ qubits, but we can extract only $n$ bits. This is not a limitation of the QFT — it is a fundamental limit of quantum mechanics.

This means the QFT cannot be used as a "fast FFT" to compute all $2^n$ Fourier coefficients of a classical signal. The best we can do is extract one coefficient (by measuring) or a few related coefficients (by using the QFT in a larger algorithm like phase estimation).

What the QFT can do efficiently: - Compute the period of a periodic function (Shor's algorithm) - Estimate the phase of a unitary's eigenvalue (phase estimation) - Determine the hidden subgroup of an abelian group (hidden subgroup problem)

What the QFT cannot do efficiently: - Compute all Fourier coefficients of an arbitrary quantum state - Act as a general-purpose signal processing tool - Replace the classical FFT for arbitrary data

14.14 Connections to Other Chapters

The QFT is a central subroutine that connects to virtually every major quantum algorithm:

Connection to Deutsch-Jozsa and Bernstein-Vazirani (Chapter 12): The Hadamard transform $H^{\otimes n}$ is the QFT over $\mathbb{Z}_2^n$. The key identity $\sum_x (-1)^{x \cdot y} = 2^n \delta_{y,0}$ that powers these algorithms is the orthogonality relation of the characters of $\mathbb{Z}_2^n$, which is the same mathematical structure that underlies the full QFT over $\mathbb{Z}_{2^n}$.

Connection to Grover's Algorithm (Chapter 13): The diffusion operator in Grover's algorithm is $D = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n}$, which uses the Hadamard transform (a 1-qubit QFT) to implement inversion about the mean. The full QFT over $\mathbb{Z}_{2^n}$ is not needed for Grover's algorithm, but quantum counting (which estimates the number of solutions) uses phase estimation, which requires the QFT.

Connection to Shor's Algorithm (Chapter 15): Shor's algorithm is the most famous application of the QFT. After modular exponentiation creates a periodic superposition, the QFT transforms it into a state whose measurement reveals the period. The QFT over $\mathbb{Z}_{2^n}$ is used rather than the Hadamard transform because the period can be any value from 1 to $2^n - 1$, not just 1 or 2.

Connection to Phase Estimation (Chapter 16): Phase estimation uses the inverse QFT to convert phase information encoded in a register of ancilla qubits into a computational basis state. This is the direct inverse of the QFT: instead of converting position information (computational basis) into frequency information (phases), it converts frequency information into position information.

The unifying pattern: All quantum algorithms that achieve exponential speedup use some form of Fourier transform to extract global structural information from a quantum state:

14.15 QFT over General Groups

The QFT is not limited to $\mathbb{Z}_{2^n}$. It can be defined over any finite group, and the choice of group determines the type of periodicity the QFT can detect.

QFT over $\mathbb{Z}_N$ (cyclic group): This is the QFT we've been studying. It uses roots of unity $e^{2\pi i/N}$ and can detect periodicity in $\mathbb{Z}_N$. This is the basis for Shor's algorithm.

QFT over $\mathbb{Z}_2^n$ (binary group): This is the Hadamard transform $H^{\otimes n}$, which uses only $\pm 1$ phases. It can detect periodicity in $\mathbb{Z}_2^n$ (parity structure), which is what Deutsch-Jozsa and Bernstein-Vazirani exploit.

QFT over general abelian groups: The QFT over a general abelian group $G$ decomposes $G$ into its character group $\hat{G}$, and the QFT maps characters to computational basis states. This is the basis for solving the abelian hidden subgroup problem, which encompasses Shor's algorithm, Simon's algorithm, and discrete logarithm algorithms.

QFT over non-abelian groups: The QFT over non-abelian groups (like the symmetric group $S_n$) is more complex and less well-understood. It is the subject of ongoing research, as it would enable efficient solutions to the non-abelian hidden subgroup problem (which includes graph isomorphism).

14.15.1 The Hidden Subgroup Problem Framework

The hidden subgroup problem (HSP) generalizes all of the algorithms we've discussed:

HSP: Given a function $f: G \to S$ on a group $G$ that is constant on the cosets of a hidden subgroup $H$ and distinct on different cosets, find $H$.

The quantum algorithm for HSP over abelian groups uses the QFT over $G$ to determine $H$ with polynomially many queries. This is the unifying framework for understanding why all these algorithms work: they all use the Fourier transform to convert a function that is constant on cosets of $H$ into a state whose measurement reveals $H$.

14.16 Practical Considerations and Noise

14.16.1 Gate Errors in the QFT

The QFT requires precise controlled phase rotations $R_k = \text{diag}(1, e^{2\pi i/2^k})$. For large $k$, these rotations have very small angles:

• $R_2$: $\theta = \pi/2 \approx 1.571$ rad (phase gate $S$)
• $R_3$: $\theta = \pi/4 \approx 0.785$ rad ($T$ gate)
• $R_5$: $\theta = \pi/16 \approx 0.196$ rad
• $R_{10}$: $\theta = \pi/512 \approx 0.006$ rad
• $R_{20}$: $\theta = \pi/524288 \approx 0.000006$ rad

For $n = 20$ qubits, the most precise rotation needed is $R_{20}$ with angle $\approx 6$ microradians. Current quantum hardware cannot implement such precise rotations. The approximate QFT (Section 14.10) drops these small rotations with negligible impact on algorithm performance.

14.16.2 QFT Circuit Depth

The QFT circuit has $O(n^2)$ gates, but each gate must be implemented with high fidelity. On current hardware: - Single-qubit gates: fidelity $\approx 99.9\%$ to $99.99\%$ - Two-qubit gates (CNOT): fidelity $\approx 99\%$ to $99.9\%$ - Multi-qubit controlled gates: must be decomposed into CNOT + single-qubit gates

For $n = 10$ qubits, the QFT requires about 55 controlled phase rotations + 10 Hadamard gates + 5 SWAP gates. After decomposition into CNOT gates, this is approximately 200-300 elementary gates. At a CNOT error rate of $10^{-3}$, the total error is about $20\%$, making the result unreliable.

14.16.3 Approximate QFT as a Practical Necessity

For practical quantum algorithms, the approximate QFT (AQFT) is used instead of the exact QFT. The AQFT drops controlled phase rotations with angles below a threshold, reducing the gate count from $O(n^2)$ to $O(n \log n)$ while maintaining fidelity above $1 - 1/\text{poly}(n)$.

In Shor's algorithm, the AQFT with $O(\log n)$ precision per qubit is sufficient to determine the period $r$ with high probability, because the continued fraction algorithm that processes the QFT output can tolerate small errors in the measured phase.

Recurring Theme — Noise is the Enemy: The QFT is one of the most demanding quantum subroutines in terms of gate precision. For large-scale algorithms like Shor's, error-corrected quantum computers with gate fidelities above $99.99\%$ are needed. The approximate QFT helps reduce the gate count, but the fundamental precision requirements remain.

14.17 Advanced Topic: QFT and Phase Estimation

The QFT's most important application is as a subroutine in quantum phase estimation (QPE), which we cover in detail in Chapter 16. Here we give an overview of how they connect.

14.17.1 The Phase Estimation Problem

Given a unitary $U$ with eigenvector $|u\rangle$ and eigenvalue $e^{2\pi i \phi}$ (where $\phi$ is unknown), phase estimation determines $\phi$ to $n$ bits of precision.

The QPE circuit:

1. Prepare $n$ ancilla qubits in $|0\rangle^{\otimes n}$ and the eigenvector $|u\rangle$.
2. Apply $H^{\otimes n}$ to the ancilla register.
3. Apply controlled-$U^{2^j}$ gates (controlled by ancilla qubit $j$).
4. Apply the inverse QFT to the ancilla register.
5. Measure the ancilla register.

The result is an $n$-bit approximation to $\phi$.

Why the IQFT (not QFT)? The controlled-$U$ operations encode the phase $\phi$ into the ancilla register as:

$$\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i k \phi} |k\rangle$$

This is the QFT of $|\phi\rangle$ (approximately). The IQFT converts this phase encoding back to the computational basis, giving us $|\phi\rangle$ (approximately).

14.17.2 Connection to Period Finding

Phase estimation with $U = U_f$ (where $U_f|x\rangle = |x + 1 \pmod{r}\rangle$ on the subspace spanned by $|0\rangle, |1\rangle, \ldots, |r-1\rangle$) directly gives Shor's period-finding algorithm. The QFT (over $\mathbb{Z}_{2^n}$) transforms the periodic superposition into a state whose measurement reveals the period.

The algorithmic chain: 1. Quantum parallelism evaluates $f(x)$ on a superposition of inputs. 2. The periodic structure of $f$ creates a periodic superposition. 3. The QFT converts the periodic superposition into a state concentrated at multiples of $N/r$. 4. Measurement gives $k \approx cN/r$, from which $r$ is extracted via continued fractions.

Each step uses a different quantum technique (superposition, entanglement, Fourier transform, measurement), and together they achieve an exponential speedup over the best known classical algorithm.

14.18 The QFT and Quantum Advantage

14.18.1 What Makes the QFT Special?

The QFT achieves something that no classical algorithm can: it transforms $2^n$ amplitudes using only $O(n^2)$ gates. This exponential compression is only possible because the amplitudes live in a quantum state, not in classical memory.

However, the QFT alone does not provide a computational advantage for computing Fourier transforms, because we cannot read out all $2^n$ amplitudes. The advantage comes only when the QFT is combined with other operations that concentrate the relevant information into a small number of measurable amplitudes.

14.18.2 When Does the QFT Provide an Advantage?

The QFT provides a quantum advantage in the following scenarios:

1. Period finding: When the input state has a periodic structure with a single dominant period, the QFT concentrates amplitude at multiples of $N/r$. A single measurement gives useful information about $r$.

2. Phase estimation: When the phase $\phi$ is encoded in a quantum state, the IQFT extracts $\phi$ with high precision using $O(n)$ qubits and $O(n)$ operations.

3. Hidden subgroup problems: When the function $f$ has a hidden subgroup structure, the QFT over the appropriate group reveals this structure.

4. Quantum simulation: When the Hamiltonian has a special structure (e.g., it is diagonal in the Fourier basis), the QFT can be used to efficiently simulate time evolution.

In all these cases, the QFT is combined with problem-specific operations (oracle queries, controlled unitaries, etc.) that prepare the input state in a way that makes the QFT's output informative.

14.18.3 When Does the QFT NOT Provide an Advantage?

The QFT does NOT provide an advantage when:

1. Arbitrary Fourier transforms: If we want to compute the DFT of an arbitrary classical signal, we cannot efficiently prepare the quantum state encoding that signal, and we cannot efficiently read out all the Fourier coefficients.

2. Generic signal processing: The QFT cannot replace classical FFT for general-purpose signal processing, because the input/output bottleneck negates the internal speedup.

3. Unstructured data: If the input data has no periodic or algebraic structure, the QFT output will not concentrate amplitude on any particular measurement outcome, making the result uninformative.

Recurring Theme — Quantum Advantage is Problem-Specific: The QFT provides an exponential internal speedup (transforming $2^n$ amplitudes in $O(n^2)$ gates), but this speedup only translates to a computational advantage when the problem structure allows us to extract the right information from the output. The QFT is a powerful subroutine, not a standalone algorithm.