Site Tools


quantum-gate-qft

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:

  1. Apply Hadamard to qubit 0
  2. For :
    • Apply controlled- (phase rotation by ) from qubits to
    • Apply Hadamard to qubit
  3. 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

quantum-gate-qft.md · Last modified: