Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum analogue of the classical Discrete Fourier Transform (DFT). It transforms a quantum state’s amplitudes from a computational basis representation into a frequency-domain representation. The QFT is the key subroutine inside Shor’s algorithm, making it directly responsible for the exponential speedup that threatens RSA encryption. It also powers quantum phase estimation, a building block used across many quantum algorithms.

The speedup is striking: the classical Fast Fourier Transform (FFT) runs in $O(N \log N)$ operations. The QFT on $n$ qubits (representing $N = 2^n$ amplitudes) uses only $O(n^2)$ gates, equivalent to $O(\log^2 N)$. This is exponentially fewer operations.

The details

The QFT maps a computational basis state $|j\rangle$ to:

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

This is exactly the DFT formula, with the Fourier coefficients encoded in the amplitudes of the output quantum state.

The circuit implementing the QFT uses two types of gates:

• Hadamard gate $H$: Applied to each qubit in sequence, it generates the required superposition
• Controlled phase rotation $R_k$: $R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^k} \end{pmatrix}$, applied between pairs of qubits to encode the phase relationships

For a 3-qubit QFT, the circuit looks like:

q0 ──[H]──[R2]──[R3]──────────────────── SWAP ──
            │     │                               
q1 ────────●──────────[H]──[R2]────────── SWAP ──
                       │     │                   
q2 ───────────────────●──────────[H]──── SWAP ──

(with SWAP gates at the end to reverse the qubit order)

The total gate count for $n$ qubits is $n(n+1)/2$ two-qubit gates plus $n$ Hadamard gates, giving $O(n^2)$ depth.

A key limitation: the QFT cannot be used to directly read out all $N$ Fourier coefficients, because measuring the output collapses the superposition to one result. The QFT is useful only as a subroutine within a larger algorithm that exploits its structure without measuring every output.

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

# 4-qubit QFT
n = 4
qc = QuantumCircuit(n)
qc.compose(QFT(n), inplace=True)
print(qc.draw())

Why it matters for learners

The QFT is the reason Shor’s algorithm works. Period finding in the modular exponentiation function $f(x) = a^x \bmod N$ is the computational heart of integer factoring. The QFT extracts the period $r$ from the quantum state after computing $f(x)$ in superposition. Without QFT, no efficient period-finding procedure exists.

Quantum phase estimation (QPE) is another critical application. QPE estimates the eigenvalues (phases) of a unitary operator $U$, given access to a state $|\psi\rangle$ that is an eigenstate of $U$. QPE is used in quantum chemistry simulations to estimate molecular ground state energies, and it underlies many quantum machine learning proposals.

Understanding QFT requires being comfortable with complex exponentials, the Fourier basis, and controlled phase gates. These are the mathematical foundations of quantum signal processing. The QFT is also a canonical example of how quantum computation achieves its speed: not by evaluating $N$ outputs simultaneously, but by performing a structured transformation on the amplitudes of a superposition that encodes all $N$ inputs.

Common misconceptions

Misconception 1: QFT directly gives you the Fourier transform of any input data. Classical FFT takes a vector of $N$ numbers as input. QFT operates on a quantum state whose amplitudes are the input data. Loading classical data into quantum amplitudes (quantum state preparation) is itself a hard problem that often requires $O(N)$ operations, eliminating the speedup for many data-loading tasks.

Misconception 2: QFT is $O(\log N)$ operations, giving exponential speedup over FFT. The gate count is $O(n^2) = O(\log^2 N)$, which is exponentially better than FFT’s $O(N \log N)$, but this comparison is subtler than it appears. QFT computes on quantum amplitudes; FFT computes on classical data. The exponential speedup applies only in contexts where the input is already in a quantum state (as in Shor’s algorithm), not for general Fourier transforms of classical data.

Misconception 3: QFT gives you all Fourier coefficients at once. After the QFT, the quantum state encodes all $N$ Fourier coefficients in superposition. Measuring collapses this to one coefficient. To read out all $N$ values, you would need $O(N)$ measurements, recreating the state each time. The value of QFT lies in using the structured state as input to further quantum computation.

See also

• Shor’s Algorithm
• Hadamard Gate
• Quantum Gate
• Quantum Circuit
• Quantum Interference