Quantum Fourier Transform (QFT) algorithm

The Quantum Fourier Transform: A Complete Guide

Understanding the algorithm that powers Shor's factoring algorithm, quantum phase estimation, and much of modern quantum computing

Contents

1. Introduction
2. From the Classical DFT to the Quantum Version
3. Mathematical Definition of the QFT
4. Building the Quantum Circuit
5. Step-by-Step Walkthrough
6. Worked Example (2-Qubit QFT)
7. Complexity: Why QFT Is Exponentially Faster
8. Implementation in Qiskit
9. Applications
10. Limitations and Common Misconceptions
11. Conclusion

1. Introduction

The Quantum Fourier Transform (QFT) is one of the most important subroutines in quantum computing. It is the quantum analogue of the classical Discrete Fourier Transform (DFT), but instead of operating on a list of numbers, it operates on the amplitudes of a quantum state. The QFT is not a standalone application — you rarely run "just the QFT" and read out a useful answer. Instead, it is a building block used inside larger algorithms, most famously Shor's algorithm for integer factorization and Quantum Phase Estimation (QPE), which itself underlies many other quantum algorithms (chemistry simulation, HHL for linear systems, and more).

What makes the QFT remarkable is efficiency: the classical Fast Fourier Transform (FFT) on \(N = 2^n\) points takes \(O(N \log N)\) operations, while the QFT achieves the same transformation using only \(O(n^2) = O((\log N)^2)\) quantum gates. That's an exponential speedup in circuit size — though, as we'll discuss later, this speedup comes with important caveats about how you can actually extract information from the result.

2. From the Classical DFT to the Quantum Version

The classical DFT takes a vector of \(N\) complex numbers \(x_0, x_1, \dots, x_{N-1}\) and produces another vector \(y_0, y_1, \dots, y_{N-1}\) defined by:

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

The QFT performs the exact same transformation, but on the amplitudes of a quantum state rather than on classical array elements. Given a quantum state

\[ |\psi\rangle = \sum_{j=0}^{N-1} x_j |j\rangle \]

the QFT maps it to a new state:

\[ \text{QFT}|\psi\rangle = \sum_{k=0}^{N-1} y_k |k\rangle, \quad \text{where } y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1} x_j\, e^{2\pi i jk/N} \]

The key difference is that this transform is now implemented as a unitary operation on qubits, which means it can be built out of a small number of quantum gates acting on superposition states — something with no classical parallel.

3. Mathematical Definition of the QFT

For an \(n\)-qubit system (so \(N = 2^n\) basis states), the QFT acts on a single computational basis state \(|j\rangle\) as follows:

\[ \text{QFT}|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk/N} |k\rangle \]

There is an equivalent and extremely useful product representation. If we write \(j\) in binary as \(j = j_1 j_2 \cdots j_n\), the QFT output can be factored into a tensor product of single-qubit states:

\[ \text{QFT}|j\rangle = \frac{1}{\sqrt{N}} \big(|0\rangle + e^{2\pi i \, 0.j_n}|1\rangle\big) \otimes \big(|0\rangle + e^{2\pi i \, 0.j_{n-1}j_n}|1\rangle\big) \otimes \cdots \otimes \big(|0\rangle + e^{2\pi i \, 0.j_1 j_2 \cdots j_n}|1\rangle\big) \]

Here \(0.j_a j_{a+1} \cdots j_n\) denotes a binary fraction. This product form is the reason the QFT can be implemented with a small, efficient circuit — each output qubit's phase depends only on a partial binary expansion of the input, which can be built up one controlled-phase gate at a time.

4. Building the Quantum Circuit

The QFT circuit for \(n\) qubits uses exactly two types of gates:

• Hadamard gate (H): Puts a qubit into equal superposition and encodes the leading bit of the phase.
• Controlled phase rotation gate (\(R_k\)): Adds a phase of \(e^{2\pi i / 2^k}\), conditioned on a control qubit, to progressively encode lower-order bits.

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

Standard QFT circuit recipe (for qubits \(q_1, q_2, \dots, q_n\)):

1. Apply a Hadamard gate to \(q_1\).
2. Apply controlled-\(R_2\) from \(q_2\) to \(q_1\), controlled-\(R_3\) from \(q_3\) to \(q_1\), ..., up to controlled-\(R_n\) from \(q_n\) to \(q_1\).
3. Apply a Hadamard gate to \(q_2\), then controlled rotations from \(q_3, q_4, \dots, q_n\) into \(q_2\).
4. Repeat this pattern, shrinking by one qubit each time, until \(q_n\) receives only a Hadamard.
5. Finally, reverse the order of the qubits using SWAP gates (because the algorithm above naturally produces the output in bit-reversed order).

Counting gates: qubit \(q_1\) needs \(n\) gates (1 Hadamard + \((n-1)\) controlled rotations), \(q_2\) needs \(n-1\), and so on, giving a total of

\[ n + (n-1) + (n-2) + \cdots + 1 = \frac{n(n+1)}{2} = O(n^2) \]

gates — plus \(O(n)\) SWAP gates for the final reversal. Compare this to the \(O(N\log N) = O(2^n \cdot n)\) cost of the classical FFT, and the exponential advantage in circuit size becomes clear.

5. Step-by-Step Walkthrough

Here's the intuition behind why the circuit works, step by step:

1. Start with a computational basis state \(|j\rangle = |j_1 j_2 \cdots j_n\rangle\).
2. Apply Hadamard to the first qubit. This creates a superposition whose relative phase depends on \(j_1\): \(\frac{1}{\sqrt2}(|0\rangle + e^{2\pi i \, 0.j_1}|1\rangle)\).
3. Apply controlled phase gates from the remaining qubits into the first qubit. Each one "adds in" the next bit of \(j\) to the phase, refining the binary fraction \(0.j_1 j_2 \cdots\).
4. Move to the second qubit and repeat — Hadamard, then controlled phases from the qubits below it.
5. Continue until every qubit carries a phase that encodes a nested binary fraction of the original bits.
6. Swap qubit order at the end to match the standard convention (since the natural circuit output has the most-significant output qubit where the least-significant one is expected).

The elegant part is that no qubit ever needs to "know" the full value of \(j\) — each controlled rotation only depends on one additional bit, which is exactly why the circuit scales polynomially rather than exponentially.

6. Worked Example (2-Qubit QFT)

Let's make this concrete with \(n = 2\) qubits, so \(N = 4\). Take the input state \(|j\rangle = |10\rangle\) (i.e., \(j = 2\)).

Circuit steps:

1. Apply H to qubit 1: \(\frac{1}{\sqrt2}(|0\rangle + e^{2\pi i \cdot 0.1}|1\rangle)\otimes|0\rangle = \frac{1}{\sqrt2}(|0\rangle - |1\rangle)\otimes|0\rangle\)
2. Apply controlled-\(R_2\) from qubit 2 (which is \(|0\rangle\)) into qubit 1 — no phase added since the control is 0.
3. Apply H to qubit 2: \(|0\rangle \rightarrow \frac{1}{\sqrt2}(|0\rangle + |1\rangle)\).
4. Swap the two qubits to fix ordering.

Result: \(\frac{1}{2}\big(|00\rangle - |01\rangle + i|10\rangle - i|11\rangle\big)\), matching exactly what you'd get from the DFT formula with \(j=2, N=4\).

7. Complexity: Why QFT Is Exponentially Faster

Transform	Input size	Gate/operation count
Naive DFT	\(N\) numbers	\(O(N^2)\)
Fast Fourier Transform (FFT)	\(N\) numbers	\(O(N \log N)\)
Quantum Fourier Transform (QFT)	\(n = \log_2 N\) qubits	\(O(n^2) = O((\log N)^2)\)

Important caveat: this speedup is about transforming the amplitudes of a superposition, not about reading out a full classical vector. You cannot simply run the QFT and then measure to get all \(N\) output amplitudes — a measurement collapses the state to a single basis outcome. The exponential advantage is only useful when it's embedded inside a larger algorithm designed to extract a specific, global piece of information (like a period or a phase) via interference, exactly as Shor's algorithm does.

8. Implementation in Qiskit

Here's a minimal working example using IBM's Qiskit framework:

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
from qiskit.quantum_info import Statevector

# Build a 3-qubit QFT circuit
n = 3
qc = QuantumCircuit(n)

# Prepare an input basis state, e.g. |101> (j = 5)
qc.x(0)
qc.x(2)

# Apply the QFT (Qiskit provides a built-in library gate)
qc.append(QFT(n), range(n))

# Inspect the resulting statevector
state = Statevector.from_instruction(qc)
print(state)

Or, to build the QFT manually from primitive gates (educational version):

import numpy as np
from qiskit import QuantumCircuit

def qft_rotations(circuit, n):
    if n == 0:
        return circuit
    n -= 1
    circuit.h(n)
    for qubit in range(n):
        circuit.cp(np.pi / 2 ** (n - qubit), qubit, n)
    qft_rotations(circuit, n)

def swap_registers(circuit, n):
    for qubit in range(n // 2):
        circuit.swap(qubit, n - qubit - 1)
    return circuit

def qft(circuit, n):
    qft_rotations(circuit, n)
    swap_registers(circuit, n)
    return circuit

qc = QuantumCircuit(4)
qft(qc, 4)
print(qc.draw())

9. Applications

Shor's Algorithm

The QFT is the engine inside Shor's algorithm for factoring large integers. After using modular exponentiation to create a superposition encoding the period of a function, the QFT converts that periodicity into a measurable interference pattern in the frequency domain — this is what lets Shor's algorithm find factors exponentially faster than the best known classical methods, threatening classical RSA-style cryptography.

Quantum Phase Estimation (QPE)

QPE uses the inverse QFT to extract an unknown phase \(\theta\) associated with an eigenvalue \(e^{2\pi i \theta}\) of a unitary operator. QPE itself is a subroutine inside many other algorithms, including quantum chemistry simulations and the HHL algorithm for solving linear systems of equations.

Quantum Counting and Amplitude Estimation

Combines QPE (and thus QFT) with Grover's algorithm to estimate the number of solutions to a search problem.

Period Finding & Hidden Subgroup Problems

More generally, the QFT is the standard tool for solving hidden subgroup problems, a broad class of problems where quantum algorithms provide their most dramatic known speedups.

10. Limitations and Common Misconceptions

• "QFT is a fast way to compute a DFT of classical data." Not quite — loading classical data into a quantum state (state preparation) can itself cost \(O(N)\) operations, which erases the advantage unless the state is already available cheaply (e.g., produced by a previous quantum step).
• "You can read out the full transformed vector." No — measurement gives only one sampled outcome per run. Algorithms using QFT are designed so the *useful* information (like a period) is concentrated on a few likely measurement outcomes.
• Precision and noise: the controlled rotation angles shrink exponentially (\(e^{2\pi i/2^k}\)), so on real noisy hardware, very small-angle rotations are hard to implement accurately; an "approximate QFT" that drops very small rotations is often used in practice with minimal loss of fidelity.

11. Conclusion

The Quantum Fourier Transform is a cornerstone of quantum algorithm design: a compact, \(O(n^2)\)-gate circuit that performs an operation exponentially larger than what's classically tractable to write down explicitly. While it isn't a magic bullet for arbitrary Fourier analysis, it's the linchpin behind some of quantum computing's most celebrated results, including Shor's algorithm and quantum phase estimation. Understanding the QFT circuit — Hadamards, controlled phase rotations, and a final qubit reversal — is essential groundwork for anyone diving deeper into quantum algorithms.

---

Have questions about implementing QFT on real hardware, or want a follow-up post walking through Shor's algorithm in full? Let me know in the comments!