Quantum Fourier Transform (QFT)

Overview

The Quantum Fourier Transform maps quantum states to the frequency domain. It's the quantum analog of the classical discrete Fourier transform and is exponentially faster.

The Transform

For an n-qubit state |j⟩:

QFT|j⟩ = (1/√N) Σₖ e^(2πijk/N) |k⟩

This transforms computational basis states into periodic superpositions.

The Circuit

CODE
┌───┐ ┌───────┐ ┌───────┐ ╳
q_0: ┤ H ├─┤ P(π/2)├─┤ P(π/4)├─╳─
     └───┘ └───┬───┘ └───┬───┘ │
     ┌───┐     │   ┌─────┴────┐│
q_1: ┤ H ├─────■───┤  P(π/2)  ├╳─
     └───┘         └────┬─────┘│
     ┌───┐              │      │
q_2: ┤ H ├──────────────■──────╳
     └───┘

Steps (for each qubit i):

Hadamard: H on qubit i
Controlled Phases: CP(π/2^k) from qubit i+k to i
Swap: Reverse qubit order at the end

Running the Circuit

PYTHON
from quantum_fourier_transform import run_circuit, create_inverse_qft_circuit

# Run QFT on |000⟩
counts = run_circuit()
print(counts)  # Uniform distribution (all states equal)

# Create inverse QFT
inv_qft = create_inverse_qft_circuit(n_qubits=3)

Key Properties

Unitary: QFT† = QFT⁻¹
Efficient: O(n²) gates vs O(N log N) classical
Periodic states: Creates interference patterns

QFT vs Classical FFT

Feature	QFT	Classical FFT
Complexity	O(n²) gates	O(N log N)
Input size	n qubits = 2ⁿ amplitudes	N numbers
Output	Quantum state	Classical array
Readout	Probabilistic	Deterministic

Applications

Shor's Algorithm: Period finding for factoring
Quantum Phase Estimation: Eigenvalue problems
Quantum Simulation: Time evolution
Signal Processing: Quantum pattern recognition