The quantum Fourier transform (QFT) rearranges a quantum state so that information carried by amplitude phases becomes information carried by amplitude magnitudes. That conversion matters because measurement samples magnitudes as outcome probabilities. It is a core building block for quantum phase estimation and Shor’s algorithm, and it uses interference and quantum parallelism to process periodic quantum states efficiently. section 7.0 section 7.5
A one-qubit Hadamard pattern gives the smallest useful intuition. Prepare a geometric-sequence state whose outcome-1 amplitude has phase θ, then apply a Hadamard gate. Equal initial magnitudes cannot reveal θ through measurement; afterward, the amplitude magnitudes become cos(θ/2) and sin(θ/2), producing outcome probabilities cos²(θ/2) and sin²(θ/2). section 7.2
Formally, the QFT performs the inverse discrete Fourier transform, up to a constant, on a state vector. Fourier basis states are geometric-sequence states at distinct frequencies; each transformed amplitude expresses an inner product with one such basis. The inverse QFT (IQFT) reverses the rotation direction and recovers frequency information from phase-encoded geometric sequence states. section 7.3.2 section 7.5
A gate-based QFT circuit follows a reusable pattern:
- Apply a Hadamard gate to a target qubit. section 7.4
- Apply controlled phase rotations from the remaining qubits, with angles that shrink by powers of two. section 7.4
- Repeat across the target register, then optionally swap qubit order; reverse rotation angles to construct the IQFT. section 7.4
Listing 7.6 Quantum circuits for the QFT and IQFT
def qft(qc, targets, swap=True):
for j in range(len(targets))[::-1]:
qc.h(targets[j])
for k in range(j)[::-1]:
qc.cp(pi * 2.0 ** (k - j), targets[j], targets[k])
if swap:
qc.mswap(targets)
def iqft(qc, targets, swap=True):
for j in range(len(targets))[::-1]:
qc.h(targets[j])
for k in range(j)[::-1]:
qc.cp(-pi * 2 ** (k - j), targets[j], targets[k])
if swap:
qc.mswap(targets)
class QFT(QuantumCircuit):
def __init__(self, m, reversed=False, swap=True):
super().__init__(QuantumRegister(m))
targets = range(m)
if reversed:
targets = targets[::-1]
qft(self, targets, swap)
class IQFT(QuantumCircuit):
def __init__(self, m, reversed=False, swap=True):
super().__init__(QuantumRegister(m))
targets = range(m)
if reversed:
targets = targets[::-1]
iqft(self, targets, swap)
The paired implementations make the inverse concrete: QFT and IQFT share the Hadamard-and-controlled-phase structure, differing principally in controlled-phase signs and optional output-order swaps. section 7.4
Finding an encoded frequency
Applying the IQFT to a geometric-sequence state yields a phased discrete sinc state. For an integer encoded frequency, one outcome has magnitude 1. For a non-integer frequency, the two nearest integer outcomes have the largest magnitudes, allowing measurement results to estimate the encoded value. section 8.5
The QFT can also prepare useful quantum-state distributions. Encode selected starting frequencies from a trigonometric function’s Fourier coefficients into phase, then apply the QFT to obtain distributions such as raised cosine or sin⁴. These distributions can approximate a normal distribution and support optimization, machine-learning, and statistical applications. section 8.0 section 8.5
