# Quantum Fourier Transform (QFT)

**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.

## Definition

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).

## Phase Encoding

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$

## Circuit Implementation

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 [[quantum-gate-permutation|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

## Properties

- **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

## Applications

**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

## Scalability

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

## Approximations

**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

## Relation to Other Gates

- [[quantum-gate-permutation|Permutation gates]]: bit-reversal reorders QFT output
- [[quantum-gate-grover-diffusion|Grover diffusion]]: uses inverse QFT for amplitude amplification
- [[quantum-gate-controlled-unitary|Controlled-unitary gates]]: controlled-$U$ gates essential for phase estimation (used in QFT circuits)