The quantum Fourier transform (QFT) is a core circuit primitive in quantum algorithms—most famously in quantum phase estimation and Shor’s factoring algorithm.

At a high level, it is the quantum analogue of the discrete Fourier transform (DFT): it maps information between a “time/index” representation and a “frequency/phase” representation.

The definition (what it does)

On $n$ qubits, the computational basis states $\lvert x\rangle$ represent integers $x \in \{0,1,\dots,2^n-1\}$. The QFT is the linear map defined by

$$ \text{QFT},\lvert x\rangle

\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i, xk / 2^n},\lvert k\rangle. $$

Two notes that often confuse beginners:

• Sign convention: in many classical DSP texts, the DFT uses $e^{-2\pi i\, xk/N}$. With the positive exponent above, the QFT corresponds (up to convention) to the inverse of that classical DFT definition.
• Normalization: the factor $1/\sqrt{2^n}$ keeps the map unitary (probabilities sum to 1).

Why it’s special (speed)

The classical DFT on $N=2^n$ complex numbers is a matrix-vector multiply of size $N$, which is expensive in general. The QFT, however, has a structured gate decomposition that uses only $O(n^2)$ basic gates.

That does not mean you can read out all $2^n$ Fourier coefficients (measurement still limits you), but it does mean the transform can be applied efficiently inside larger algorithms.

How to build the QFT circuit

The QFT can be implemented with a repeating pattern:

• Apply a Hadamard on a qubit.
• Apply controlled phase rotations from lower qubits onto that qubit.
• Repeat for each qubit.
• Optionally apply SWAP gates to reverse qubit order (many libraries choose a particular output bit order).

Controlled phase rotations

Define a single-qubit phase rotation

In the standard QFT decomposition, you use controlled-$R_k$ gates with angles that get smaller as the control qubit gets farther away.

A 3-qubit QFT sketch

For 3 qubits (wire order 0,1,2), one common decomposition is:

1. On qubit 0: $H$, then controlled-$R_2$ from qubit 1, controlled-$R_3$ from qubit 2
2. On qubit 1: $H$, then controlled-$R_2$ from qubit 2
3. On qubit 2: $H$
4. Swap qubit 0 and 2 (optional, for conventional ordering)

QFT in code (Qiskit)

Qiskit provides QFT as a reusable circuit. This is the easiest way to get started:

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

n = 4
qc = QuantumCircuit(n)
qc.append(QFT(n, do_swaps=True, approximation_degree=0), range(n))
qc.decompose().draw("text")

If you prefer to build it by hand for learning, you can implement the Hadamard + controlled-phase pattern with cp rotations:

import numpy as np
from qiskit import QuantumCircuit

def qft_in_place(n: int, do_swaps: bool = True) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    for target in range(n):
        qc.h(target)
        for control in range(target + 1, n):
            # angle = 2π / 2^(control-target+1)
            angle = 2 * np.pi / (2 ** (control - target + 1))
            qc.cp(angle, control, target)
    if do_swaps:
        for i in range(n // 2):
            qc.swap(i, n - 1 - i)
    return qc

qc = qft_in_place(4, do_swaps=True)
qc.draw("text")

What QFT is used for (intuition)

QFT is most useful when the amplitudes encode a periodic structure. Very roughly:

• periodicity in the “index basis” $\lvert x\rangle$
• becomes concentration/peaks in a “frequency-like basis” after QFT

That’s the reason it appears in:

• Quantum Phase Estimation (QPE): extracting phases (eigenvalues) of a unitary
• Shor’s algorithm: turning periodicity into a measurable signal for factoring

Next

• If you’re reading algorithms in order: continue to Shor’s algorithm.
• If you want the general framework behind Grover-like routines: Amplitude amplification.