Table of Contents
Quantum Fourier transform (QFT)
Quantum Fourier Transform is an -qubit unitary gate that maps the computational basis state to a uniform superposition with phases determined by . 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 qubits, the Quantum Fourier Transform is:
The matrix element is (unitary and normalized).
Phase encoding
The QFT encodes the input as phases in the output superposition. Each output basis state receives a phase , proportional to the product .
- Input: localized computational basis state
- Output: uniform superposition with phases encoding
- Inverse: maps uniform superposition back to
Circuit implementation
The QFT can be decomposed into single-qubit rotations and two-qubit controlled-phase gates:
- Apply Hadamard to qubit 0
- For :
- Apply controlled- (phase rotation by ) from qubits to
- Apply Hadamard to qubit
- Apply bit-reversal permutation to reorder qubits
Circuit depth: for nearest-neighbor architecture (two-qubit gates dominate)
Gate count: two-qubit gates + single-qubit gates
Properties
- Unitary: (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 and eigenstate with eigenvalue , find
- Apply controlled- 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: depth for nearest-neighbor connectivity
- All-to-all connectivity: depth possible but requires long-range interactions
- Error: accumulates from 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- gates for (smaller angles)
- Reduces gate count to for
- Trade-off: accuracy vs. circuit depth
- Used in near-term algorithms to manage error
Relation to other gates
- Permutation gates: bit-reversal reorders QFT output
- Grover diffusion: uses inverse QFT for amplitude amplification
- Controlled-unitary gates: controlled- gates essential for phase estimation (used in QFT circuits)
