Quantum Fourier Transform is an $n$-qubit unitary gate that maps the computational basis state $|j\rangle$ to a uniform superposition with phases determined by $j$. It is the quantum analogue of the classical discrete Fourier transform and is a subroutine in Shor's factoring algorithm, phase estimation, and other quantum algorithms.

For $n$ qubits, the Quantum Fourier Transform is:

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

The matrix element is $\text{QFT}[k][j] = \frac{1}{\sqrt{2^n}} e^{2\pi i jk/2^n}$ (unitary and normalized).

The QFT encodes the input $j$ as phases in the output superposition. Each output basis state $|k\rangle$ receives a phase $e^{2\pi i jk/2^n}$, proportional to the product $jk$.

• Input: localized computational basis state $|j\rangle$
• Output: uniform superposition with phases encoding $j$
• Inverse: $\text{QFT}^\dagger$ maps uniform superposition back to $|j\rangle$

The QFT can be decomposed into single-qubit rotations and two-qubit controlled-phase gates:

1. Apply Hadamard to qubit 0
2. For $j = 1, 2, \ldots, n-1$:
   • Apply controlled-$R_k$ (phase rotation by $2\pi/2^k$) from qubits $0$ to $j$
   • Apply Hadamard to qubit $j$
3. Apply bit-reversal permutation to reorder qubits

Circuit depth: $O(n^2)$ for nearest-neighbor architecture (two-qubit gates dominate)

Gate count: $O(n^2)$ two-qubit gates + $O(n)$ single-qubit gates

• Unitary: $\text{QFT}^\dagger \text{QFT} = I$ (reversible via inverse QFT)
• Efficient quantum algorithm: exponentially faster than classical FFT on quantum computers
• Maps bases: transforms computational basis to Fourier basis and vice versa
• Sparse to dense: transforms localized states to uniform superposition with phases

Shor's factoring algorithm:

• Phase estimation step uses QFT to extract period of modular exponentiation
• QFT's phase encoding reveals the period efficiently

Phase estimation:

• Given unitary $U$ and eigenstate $|u\rangle$ with eigenvalue $e^{2\pi i \theta}$, find $\theta$
• Apply controlled-$U$ gates, then inverse QFT to measure phase

Variational algorithms:

• Some VQE ansätze use QFT for Fourier feature encoding
• Efficient for periodic function learning

Quantum simulation:

• Fourier basis transforms for frequency-domain analysis
• Energy eigenstate preparation

QFT implementation complexity:

• Shallow circuit: $O(n^2)$ depth for nearest-neighbor connectivity
• All-to-all connectivity: $O(n)$ depth possible but requires long-range interactions
• Error: accumulates from $O(n^2)$ two-qubit gates; high-fidelity QFT is challenging on NISQ devices
• Practical limit: current devices (~10–20 qubits) can implement useful QFT subroutines

Approximate QFT (aDFT): omit least significant rotations to reduce gate count

• Drop controlled-$R_k$ gates for $k > m$ (smaller angles)
• Reduces gate count to $O(n \cdot m)$ for $m < n$
• Trade-off: accuracy vs. circuit depth
• Used in near-term algorithms to manage error

• Permutation gates: bit-reversal reorders QFT output
• Grover diffusion: uses inverse QFT for amplitude amplification
• Controlled-unitary gates: controlled-$U$ gates essential for phase estimation (used in QFT circuits)