Quantum Fourier Transform

The quantum version of the discrete Fourier transform, a key subroutine in many quantum algorithms.

The Quantum Fourier Transform (QFT) is a linear transformation on quantum states that’s central to algorithms like Shor’s and quantum phase estimation.

Definition

The QFT maps computational basis states as:

$$QFT|j⟩=\frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{e}^{2\pi ijk/N}|k⟩$$

where $N=2^n$ for $n$ qubits.

Matrix Form

For 2 qubits ($N=4$):

$$QF{T}_4=\frac{1}{2}\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right)$$

Why It’s Important

Classical FFT: O(N log N)

The Fast Fourier Transform revolutionized signal processing.

Quantum QFT: O(n²) = O(log² N)

Exponentially faster! This speedup is key to Shor’s algorithm.

The Circuit

The QFT has a remarkably simple circuit using only Hadamards and controlled rotations:

|x₀⟩ ──H──R₂──R₃──...──Rₙ──────────────────
          │   │       │
|x₁⟩ ─────●───┼───...─┼────H──R₂──...──Rₙ₋₁──
              │       │        │       │
|x₂⟩ ─────────●───...─┼────────●───...─┼──────
                      │                │
...                   ...              ...
                      │                │
|xₙ⟩ ─────────────────●────────────────●──H──

Plus SWAP gates at the end to reverse bit order.

Gates used:

• Hadamard: $H$
• Controlled rotation: $R_k=\left(\begin{array}{cc}1& 0\\ 0& e^{2\pi i/2^k}\end{array}\right)$

Inverse QFT

The inverse is simply the conjugate transpose:

$$QF{T}^{†}=QF{T}^{-1}$$

Same circuit but with negative rotation angles, run in reverse.

Applications

Important Caveat

The QFT is fast, but there’s a catch:

• Input: Requires preparing the input state (often expensive)
• Output: Result is in amplitudes (can’t read them all directly)

The QFT is useful when it’s part of a larger algorithm that handles input/output appropriately.

Approximate QFT

For practical purposes, very small rotations ($R_k$ for large $k$) can be omitted:

$$\text{Approximate QFT}\approx \text{Full QFT}$$

This reduces circuit depth with minimal accuracy loss.

See also: Shor’s Algorithm, Quantum Phase Estimation, Quantum Algorithm