Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is a quantum version of the discrete Fourier transform. It’s a key subroutine in many quantum algorithms, including Shor’s factoring algorithm.

What QFT Does

QFT transforms between two representations of quantum data:

Computational basis: states labeled by binary strings
Fourier basis: states labeled by phases

Mathematically: \[|x\rangle \xrightarrow{\text{QFT}} \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i xk/N}|k\rangle\]

The 2-Qubit QFT

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector
from math import pi

def qft_2():
    qc = QuantumCircuit(2)
    qc.h(1)
    qc.cp(pi/2, 0, 1)  # Controlled phase
    qc.h(0)
    qc.swap(0, 1)
    return qc

qc = qft_2()
print(qc)
print(Statevector(qc))

The Pattern

The n-qubit QFT follows a pattern:

Apply Hadamard to most significant qubit
Apply controlled phases with decreasing angles
Repeat on remaining qubits
Swap at the end (to fix qubit ordering)

def qft(n):
    qc = QuantumCircuit(n)
    for i in range(n-1, -1, -1):
        qc.h(i)
        for j in range(i):
            qc.cp(pi/(2**(i-j)), j, i)
    # Swap qubits to match little-endian convention
    for i in range(n // 2):
        qc.swap(i, n - i - 1)
    return qc

Why Controlled Phases?

The Fourier basis states are distinguished by phase patterns:

QFT|00⟩ = (|00⟩ + |01⟩ + |10⟩ + |11⟩)/2        (all same phase)
QFT|01⟩ = (|00⟩ - |01⟩ + |10⟩ - |11⟩)/2       (alternating)
QFT|10⟩ = (|00⟩ + i|01⟩ - |10⟩ - i|11⟩)/2     (phase pattern)
QFT|11⟩ = (|00⟩ - i|01⟩ - |10⟩ + i|11⟩)/2     (different pattern)

The controlled phases build these phase patterns.

QFT and Qubit Order

QFT is usually defined with big-endian ordering (qubit n-1 is most significant). Qiskit uses little-endian. The final SWAP fixes this.

# Without SWAP: output appears reversed
qc = QuantumCircuit(2)
qc.h(0)
qc.h(1)
qc.cp(pi/2, 0, 1)

print("Without swap:", Statevector(qc))

Inverse QFT

QFT is unitary, so it has an inverse (conjugate transpose):

qc = QuantumCircuit(2)
qc.x(0)  # Start with |01⟩

# Apply QFT then inverse QFT
qc.compose(qft_2(), inplace=True)
qc.compose(qft_2().inverse(), inplace=True)

print("After QFT† QFT:", Statevector(qc))

If implemented correctly, you get back to the original state.