〰️

Topic 5 of 12

Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum analogue of the classical Discrete Fourier Transform, but requires only O(n²) gates on n qubits instead of O(n·2ⁿ) classical operations. It detects periodicity in quantum amplitudes exponentially faster than any classical method, making it the core subroutine of Shor's factoring algorithm and quantum phase estimation.

Key Concepts

QFT Definition

The QFT maps computational basis states:

|j\rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i jk/N}|k\rangle

where

N=2^n

. Each basis state

|j\rangle

is mapped to an equal superposition with phases encoding the Fourier frequencies — precisely the classical DFT formula applied to the amplitude vector.

Efficiency

The classical Fast Fourier Transform (FFT) on

N = 2^n

points requires

O(N \log N) = O(n \cdot 2^n)

operations. The QFT uses only

O(n^2)

quantum gates. For

n = 50

qubits, that is

2500

gates versus

\approx 10^{17}

classical operations — an exponential speedup.

Hadamard as 1-Qubit QFT

For a single qubit (

n=1

N=2

), the QFT reduces exactly to the Hadamard gate:

H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)

and

H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)

. The multi-qubit QFT generalizes this with controlled phase rotations.

Controlled-Phase Gates

The QFT circuit uses

n

Hadamard gates and

n(n-1)/2

controlled-

R_k

gates where

R_k = \text{diag}(1, e^{2\pi i/2^k})

. These add fractional phases between qubits to build up the Fourier frequencies. The circuit concludes with SWAP gates to reverse the bit order.

Period Finding

The QFT can detect the period

r

of a function

f(x) = a^x \bmod N

by transforming a periodic amplitude pattern into a sharp peak at frequencies that are multiples of

N/r

. Measuring this frequency and applying the continued fractions algorithm recovers

r

— the core step of Shor's algorithm.

Quantum Phase Estimation

Using the QFT, if a unitary

U

has eigenvalue

e^{2\pi i\theta}

, quantum phase estimation finds

\theta

n

-bit precision using

n

ancilla qubits and

O(n^2)

controlled-

U

applications. Phase estimation underlies quantum chemistry simulations and the HHL algorithm.

Key Equations

QFT Action

\text{QFT}|j\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi ijk/N}|k\rangle, \quad N = 2^n

The QFT maps each basis state to an equal-amplitude superposition with Fourier phases.

Gate Count

\text{Gates}(\text{QFT}_n) = n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2} = O(n^2)

Total gates: n Hadamards plus n(n−1)/2 controlled-phase rotations.

Classical FFT Cost

\text{Classical FFT: } O(N\log N) = O(n \cdot 2^n) \gg O(n^2) \text{ (QFT)}

QFT is exponentially more gate-efficient than classical FFT.

Controlled Phase Gate

R_k = \begin{pmatrix}1 & 0 \\ 0 & e^{2\pi i/2^k}\end{pmatrix}

Adds a phase 2π/2^k to |1⟩; used in the QFT circuit for qubit-to-qubit phase coupling.

Worked Example

1-Qubit QFT

Problem

Apply the 1-qubit QFT (i.e., Hadamard) to $|1\rangle$ and find the resulting state and measurement probabilities.

Solution

The 1-qubit QFT is the Hadamard gate $H$ .

H|1\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\-1\end{pmatrix} = |{-}\rangle

The resulting state is $|{-}\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ .

P(|0\rangle) = \left|\frac{1}{\sqrt{2}}\right|^2 = 0.5, \quad P(|1\rangle) = \left|\frac{-1}{\sqrt{2}}\right|^2 = 0.5

Answer QFT|1⟩ = |−⟩; P(|0⟩) = P(|1⟩) = 0.5

Practice

Exercises

5 problems

1 of 5

The QFT on $n=4$ qubits requires $\frac{n(n+1)}{2}$ gates total. How many gates?

Your answer

gates

2 of 5

Apply the 1-qubit QFT (Hadamard) to $|0\rangle$ . What is $P(|0\rangle)$ ?

Your answer

3 of 5

For $n=8$ qubits, the QFT acts on a space of $N=2^n$ states. What is $N$ ?

Unlock Exercise 3

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

4 of 5

Classical FFT of $N=64$ points requires $N\log_2 N$ operations. How many?

Unlock Exercise 4

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

5 of 5

For $n=10$ qubits, the QFT requires at most $n^2 = 100$ two-qubit gates. Exactly how many by the formula $n(n+1)/2$ ?

Unlock Exercise 5

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

Key Takeaways

QFT maps $|j\rangle \to \frac{1}{\sqrt{N}}\sum_k e^{2\pi ijk/N}|k\rangle$ using only $O(n^2)$ gates for $N=2^n$ .
Classical FFT costs $O(n \cdot 2^n)$ operations — exponentially more than QFT's $O(n^2)$ gates.
The 1-qubit QFT is simply the Hadamard gate; the circuit generalizes with controlled-phase rotations.
QFT detects periodicities in amplitude patterns, enabling Shor's period-finding and phase estimation.
Quantum phase estimation finds eigenvalues of unitaries to $n$ -bit precision using $O(n^2)$ QFT gates.