First time studying this topic?

Launch the interactive walkthrough to discover each component, including the 3D Q-Sphere Lab & Python in Colab.

Back to Quantum Algorithms
Topic 7.5

The Quantum Fourier Transform (QFT): The Powerhouse of Shor’s Algorithm

Understand the quantum analogue of the Discrete Fourier Transform: transforming computational basis states into phase frequencies in O(n^2) gates.

Learning Objectives

  • ✓Define the Quantum Fourier Transform (QFT) mapping |j> to sum e^(2*pi*i*j*k / 2^n) |k>
  • ✓Contrast classical FFT O(N log N) with quantum QFT O((log N)^2) exponential speedup
  • ✓Examine how QFT extracts periods in Shor’s Factoring Algorithm

📖Let's Begin with a Story

In 1822, French mathematician Joseph Fourier published a radical mathematical discovery: Any wave in the universe—no matter how complex or jagged—can be decomposed into a sum of simple sine and cosine frequencies. Today, the Fast Fourier Transform (FFT) is called "the most important numerical algorithm of our lifetime." It powers JPEG image compression, MP3 audio, 5G wireless cell towers, and MRI medical scanners. Classical FFT takes an NN-element vector and computes its frequencies in O(Nlog⁡N)O(N \log N) operations. In 1994, Peter Shor adapted Fourier's insight to quantum computing: the Quantum Fourier Transform (QFT). While classical FFT takes O(Nlog⁡N)O(N \log N) time, the quantum QFT executes in only **O((log⁡N)2)O((\log N)^2) gate operations**! For a database of size N=21000N = 2^{1000}, classical FFT would take 1030010^{300} years; QFT computes it in less than a second!

Why Should You Learn The Quantum Fourier Transform (QFT): The Powerhouse of Shor’s Algorithm?

🎯 Practical & Engineering Stakes

The mathematical engine of Shor’s algorithm

QFT is the foundational subroutine that converts hidden mathematical periods into readable quantum interference peaks, breaking RSA encryption and powering Quantum Phase Estimation.

What Is It?

Simple Explanation

Classical Fourier Transform is like listening to a symphony and separating the music into individual musical notes (violins, flutes, drums). The Quantum Fourier Transform (QFT) does this exponentially faster inside a quantum register: - It takes numbers written in binary positions (|0>, |1>) - And converts them into spinning phase clocks (e2πi/2ne^{2\pi i / 2^n})! When you measure at the end, the secret period of the function pops out as a sharp interference peak!

Technical Explanation

The Quantum Fourier Transform acts on orthonormal basis states ∣j⟩|j\rangle (j∈{0,…,2n−1}j \in \{0, \dots, 2^n-1\}) via the unitary mapping: ∣j⟩↦12n∑k=02n−1ωnjk∣k⟩,ωn=e2πi/2n|j\rangle \mapsto \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \omega_n^{j k} |k\rangle, \quad \omega_n = e^{2\pi i / 2^n} The circuit is synthesized using nn Hadamard gates and n(n−1)/2n(n-1)/2 Controlled-Phase rotation gates Rk=diag(1,e2πi/2k)R_k = \text{diag}(1, e^{2\pi i / 2^k}), achieving asymptotic gate complexity O(n2)=O((log⁡N)2)\mathcal{O}(n^2) = \mathcal{O}((\log N)^2), representing an exponential speedup over classical Cooley-Tukey FFT O(Nlog⁡N)=O(n2n)\mathcal{O}(N \log N) = \mathcal{O}(n 2^n).

📚 Key Terms

Quantum Fourier Transform (QFT)

Simple: The quantum version of Fourier analysis that transforms numbers into phase frequencies.
Technical: Unitary operator implementing discrete Fourier transform over cyclic group Z2n\mathbb{Z}_{2^n} with O(n2)\mathcal{O}(n^2) circuit complexity.

Controlled Phase Gate (RkR_k)

Simple: A gate that rotates the phase by a fraction of a circle: 2π/2k2\pi / 2^k.
Technical: Two-qubit gate applying phase shift diag(1,1,1,e2πi/2k)\text{diag}(1, 1, 1, e^{2\pi i / 2^k}) conditioned on control bit.

Period Finding

Simple: Finding how often a secret math pattern repeats.
Technical: The core reduction in Shor’s algorithm mapping integer factorization to the order-finding problem in multiplicative group (Z/NZ)∗(\mathbb{Z}/N\mathbb{Z})^*.

Q-Sphere Lab: The Quantum Fourier Transform (QFT): The Powerhouse of Shor’s Algorithm

IBM Q-Sphere Model

Interactive 3D state vector exploration, unitary transformation gates, and Born rule collapse for Topic 7.5

Azimuth: 45°Elevation: 25°
+Z |0⟩-Z |1⟩+X |+⟩+Y |+i⟩01|ψ⟩
Q-Sphere Phase Color:
0 π/2 π 3π/2

Quantum Statevector

dim(H) = 2
|ψ⟩ = (1.000 + 0.000i)|0⟩
     + (0.000 + 0.000i)|1⟩
Polar Angle (θ):0.0° (0.000π rad)
Phase Angle (ϕ):0.0° (0.000π rad)

Born Rule Probabilities: P(x) = |⟨x|ψ⟩|²Σ P = 1.00

P(|0⟩) = |α|²100.0%
P(|1⟩) = |β|²0.0%
Quantum Measurement

Apply Single-Qubit Unitary Gates

Presets:
Continuous Polar Angle θ (0° = |0⟩, 180° = |1⟩):0.0°
Continuous Phase Angle ϕ (0° to 360°):0.0°
Recent Operations Log:
#1Initial state: |0⟩

📐 Mathematical Foundation

LaTeX KaTeX
∣j⟩→QFT12n∑k=02n−1e2πijk/2n∣k⟩=12n(∣0⟩+e2πi0.jn∣1⟩)⊗⋯⊗(∣0⟩+e2πi0.j1…jn∣1⟩)|j\rangle \xrightarrow{\text{QFT}} \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i j k / 2^n} |k\rangle = \frac{1}{\sqrt{2^n}} \big(|0\rangle + e^{2\pi i 0.j_n}|1\rangle\big) \otimes \dots \otimes \big(|0\rangle + e^{2\pi i 0.j_1 \dots j_n}|1\rangle\big)

What does it mean?

The Quantum Fourier Transform (QFT): The quantum analog of the Discrete Fourier Transform (DFT). It converts computational basis states into frequency/phase representations with exponential efficiency (O(n²) gates vs O(n 2^n) classical FFT operations). It is the mathematical engine behind Shor’s factoring and quantum phase estimation.

Understanding the Symbols

Symbol / TermMeaningBeginner Interpretation
∣j⟩|j\rangleInput computational stateInteger j∈0,…,2n−1j \in {0, \dots, 2^n - 1} encoded in binary
e2πijk/2ne^{2\pi i j k / 2^n}Fourier phase factorComplex root of unity rotating the phase proportional to frequency j · k
0.j1j2…jn0.j_1 j_2 \dots j_nBinary fraction notationsuml=1njl2−lsum_{l=1}^n j_l 2^{-l} representing fractional phase angle rotations
O(n2)\mathcal{O}(n^2)Quantum circuit gate scalingRequires only n(n+1)/2 Hadamard and Controlled-Phase gates

📊 Numerical Example

Applying QFT to a single qubit (n = 1):

For n = 1, 2^1 = 2 states: Formula: ∣j⟩|j\rangle → (1/√2) [ ∣0⟩|0\rangle + e^{2π i j / 2} ∣1⟩|1\rangle ] Case 1: Input ∣0⟩|0\rangle (j = 0): e^{2π i (0)/2} = e^0 = 1 QFT ∣0⟩|0\rangle = (1/√2) [ ∣0⟩|0\rangle + 1∣1⟩|1\rangle ] = (∣0⟩|0\rangle + ∣1⟩|1\rangle)/√2 = ∣+⟩|+\rangle (Equivalent to Hadamard!) Case 2: Input ∣1⟩|1\rangle (j = 1): e^{2π i (1)/2} = e^{i π} = -1 (Euler's identity!) QFT ∣1⟩|1\rangle = (1/√2) [ ∣0⟩|0\rangle + (-1)∣1⟩|1\rangle ] = (∣0⟩|0\rangle - ∣1⟩|1\rangle)/√2 = |–⟩

Result: For 1 qubit, the QFT is exactly the Hadamard gate. For n qubits, it maps multi-qubit periodicity directly into readable peak frequencies.

⚙️ How Does It Work?

1

Hadamard on First Qubit

Apply H to qubit 0.

2

Controlled Phase Rotations

Apply sequence of Controlled-R2, Controlled-R3, ... Controlled-Rn gates from subsequent qubits.

3

Recurse on Remaining Qubits

Repeat for qubit 1, qubit 2, through qubit n-1.

4

Swap Gates

Reverse the order of qubits at the end to correct bit reversal.

🌍 Where Is It Used?

Shor’s Factoring Algorithm

Problem: Factoring 2048-bit RSA keys into prime factors p and q.

Solution: QFT extracts the period r of modular exponentiation a^x mod N, factoring N in polynomial time.

🎯 Try It Yourself

How many quantum gates are required to compute the Quantum Fourier Transform on an n-qubit register?

Interactive activity component

🐍 Python Hands-On: Constructing the 3-Qubit Quantum Fourier Transform (QFT) in Qiskit

Build the Quantum Fourier Transform (QFT) circuit in Qiskit using Hadamard gates and controlled-phase rotations, and inspect the state evolution.

Open Colab

1Install Required Packages

For Google Colab or Jupyter notebooks, run this shell command to install the required dependencies:

Terminal / Notebook Install Commandbash
!pip install qiskit numpy
Packages:
qiskitnumpy

2Import Libraries

Import Statementspython
1from qiskit import QuantumCircuit
2from qiskit.quantum_info import Statevector
3import numpy as np

from qiskit import QuantumCircuit → Circuit constructor

from qiskit.quantum_info import Statevector → Statevector analysis

import numpy as np → Trigonometric math

3Demonstration Code & Logic

Python Execution Codepython
1# Build 3-qubit QFT circuit: maps computational basis to Fourier basis
2def build_qft_3qubit():
3    qc = QuantumCircuit(3)
4    # Qubit 0
5    qc.h(0)
6    qc.cp(np.pi / 2, 1, 0)  # Controlled-Phase pi/2 from q1
7    qc.cp(np.pi / 4, 2, 0)  # Controlled-Phase pi/4 from q2
8    # Qubit 1
9    qc.h(1)
10    qc.cp(np.pi / 2, 2, 1)  # Controlled-Phase pi/2 from q2
11    # Qubit 2
12    qc.h(2)
13    # Swap qubits 0 and 2 to reverse bit order
14    qc.swap(0, 2)
15    return qc
16 
17qft_circ = build_qft_3qubit()
18print('=== 3-Qubit Quantum Fourier Transform Circuit ===')
19print(qft_circ.draw('text'))
20 
21# Test QFT on input state |1> (|001>)
22test_qc = QuantumCircuit(3)
23test_qc.x(0)  # Input |001> = decimal 1
24test_qc.compose(qft_circ, inplace=True)
25sv = Statevector.from_instruction(test_qc)
26print('\nQFT Output Statevector on Input |1>:')
27for i, amp in enumerate(sv.data):
28    phase_angle = np.angle(amp) * 180 / np.pi
29    print(f'  |{i:03b}> : Magnitude={np.abs(amp):.3f}, Phase={phase_angle:6.1f} deg')
Step-by-Step Code Breakdown:

# Build 3-qubit QFT circuit: maps computational basis to Fourier basis

QFT definition

def build_qft_3qubit():

QFT builder function

qc = QuantumCircuit(3)

3 qubits

# Qubit 0

Wire 0

qc.h(0)

H on 0

qc.cp(np.pi / 2, 1, 0) # Controlled-Phase pi/2 from q1

CP pi/2

qc.cp(np.pi / 4, 2, 0) # Controlled-Phase pi/4 from q2

CP pi/4

# Qubit 1

Wire 1

qc.h(1)

H on 1

qc.cp(np.pi / 2, 2, 1) # Controlled-Phase pi/2 from q2

CP pi/2

# Qubit 2

Wire 2

qc.h(2)

H on 2

# Swap qubits 0 and 2 to reverse bit order

Bit swap

qc.swap(0, 2)

SWAP(0, 2)

return qc

Return circuit

qft_circ = build_qft_3qubit()

Instantiate

print('=== 3-Qubit Quantum Fourier Transform Circuit ===')

Header

print(qft_circ.draw('text'))

Print diagram

# Test QFT on input state |1> (|001>)

Test input

test_qc = QuantumCircuit(3)

Test circuit

test_qc.x(0) # Input |001> = decimal 1

Set input to 1

test_qc.compose(qft_circ, inplace=True)

Append QFT

sv = Statevector.from_instruction(test_qc)

Compute statevector

print('\nQFT Output Statevector on Input |1>:')

Output label

for i, amp in enumerate(sv.data):

Loop amplitudes

phase_angle = np.angle(amp) * 180 / np.pi

Calculate phase

print(f' |{i:03b}> : Magnitude={np.abs(amp):.3f}, Phase={phase_angle:6.1f} deg')

Display magnitude and phase

📋 Complete Script (All-in-One)

Click "Copy for Colab", open Google Colab, paste into a single cell, and run.

Google Colab Notebook Scriptpython
1# =========================================================
2# Constructing the 3-Qubit Quantum Fourier Transform (QFT) in Qiskit
3# Prepared for Google Colab (Run with Shift + Enter)
4# =========================================================
5 
6# Step 1: Install required packages
7!pip install qiskit numpy
8 
9# Step 2: Import libraries
10from qiskit import QuantumCircuit
11from qiskit.quantum_info import Statevector
12import numpy as np
13 
14# Step 3: Run Demonstration
15# Build 3-qubit QFT circuit: maps computational basis to Fourier basis
16def build_qft_3qubit():
17    qc = QuantumCircuit(3)
18    # Qubit 0
19    qc.h(0)
20    qc.cp(np.pi / 2, 1, 0)  # Controlled-Phase pi/2 from q1
21    qc.cp(np.pi / 4, 2, 0)  # Controlled-Phase pi/4 from q2
22    # Qubit 1
23    qc.h(1)
24    qc.cp(np.pi / 2, 2, 1)  # Controlled-Phase pi/2 from q2
25    # Qubit 2
26    qc.h(2)
27    # Swap qubits 0 and 2 to reverse bit order
28    qc.swap(0, 2)
29    return qc
30 
31qft_circ = build_qft_3qubit()
32print('=== 3-Qubit Quantum Fourier Transform Circuit ===')
33print(qft_circ.draw('text'))
34 
35# Test QFT on input state |1> (|001>)
36test_qc = QuantumCircuit(3)
37test_qc.x(0)  # Input |001> = decimal 1
38test_qc.compose(qft_circ, inplace=True)
39sv = Statevector.from_instruction(test_qc)
40print('\nQFT Output Statevector on Input |1>:')
41for i, amp in enumerate(sv.data):
42    phase_angle = np.angle(amp) * 180 / np.pi
43    print(f'  |{i:03b}> : Magnitude={np.abs(amp):.3f}, Phase={phase_angle:6.1f} deg')
⚡ How to Run in Google Colab (3 Quick Steps)
  1. Click "Copy for Google Colab" above.
  2. Click Open New Google Colab Notebook (opens in a new tab).
  3. Click on the first empty code cell, press Ctrl + V (or Cmd + V) to paste, then press Shift + Enter to execute!
Launch Blank Colab Notebook

🔄 Algorithmic Execution Flow

1
Hadamard & Controlled Rotations

Apply H gate followed by successive controlled-phase gates CP(pi/2^k).

→
2
SWAP Reversal

Swap outermost qubits to align frequency register bit-significance.

→
3
Fourier State Verification

Verify that all 8 basis states have equal magnitude 1/sqrt(8) with linear phase gradients.

📥 Input / Initial State
Input state |001> processed through 3-qubit QFT circuit.
📤 Expected Output
All 8 states have equal magnitude 0.354 (1/sqrt(8)) with distinct, linearly progressing phase rotations: 0, 45, 90, 135, 180, 225, 270, 315 degrees.
💡 What Does This Demonstration Show?

The QFT maps computational basis states into periodic phase patterns across all basis states in O(n^2) gates, compared to O(n * 2^n) operations for the classical Fast Fourier Transform (FFT). It is the mathematical engine of Shor's algorithm.

Course Learning Resource • Slide DeckLesson 910 Slides

Lesson 9: Grover Search and Amplitude Amplification

Oracle, diffusion operator, interference, and quadratic search speedup.

Author: Dr. Syed Muzamil Basha• FDP Approved Curriculum
Open in New Tab

📝 Learning Check

Test your understanding with these questions. Remember, this is for learning, not examination!

Question 1: What is the primary role of the Quantum Fourier Transform in Shor’s Factoring Algorithm?

Question 2: What is the Quantum Fourier Transform?

Question 3: What is the circuit complexity of QFT?

Question 4: What is QFT used for in Shor's algorithm?

Question 5: What is quantum phase estimation?

Previous: Grover’s Search Algorithm: Quadratic SpeedupNext: Quantum Algorithm Simulation: Module 7 Capstone