Before the quantum version, let’s recall what the Discrete Fourier Transform does. You have N numbers and want to find the frequencies hidden inside them. Mathematically it maps a time-domain sequence to the frequency domain.
Classical DFT — Definition
Given x = (x₀,…,xₙ₋₁), the DFT produces X = (X₀,…,Xₙ₋₁):
The DFT is a linear map X = Fₙ x. Writing ω = ωₙ for conciseness, entry (q, k) of Fₙ is (1/√N)ωᵱ𝒌:
Fₙ = 1/√N
1
1
1
⋯
1
1
ω
ω²
⋯
ωⁿ⁻¹
1
ω²
ω⁴
⋯
ω²ⁿ⁻²
⋮
⋮
⋮
⋱
⋮
1
ωⁿ⁻¹
ω²ⁿ⁻²
⋯
ωⁿ²⁻²ⁿ
Fₙ is unitary: Fₙ†Fₙ = I. Every pair of columns is orthogonal with unit norm. This is why the DFT is perfectly reversible — and why its quantum version is a valid gate.
Interactive DFT — choose a preset and watch the frequency spectrum appear.
Xᵱ = (1/√N)·x₀·ωₙ⁰ = 1/√N for every q. A spike in time gives a flat constant spectrum.
Section 02
The Quantum Fourier Transform
The quantum analogue of the DFT replaces classical vectors with quantum states. Instead of transforming a list of numbers, the QFT transforms the amplitudes of a quantum superposition, processing all 2ⁿ amplitudes simultaneously with only O(n²) gates.
QFT — Definition
Given |ψ⟩ = ∑ₖ xₖ |k⟩, the QFT produces |Ψ⟩ = ∑ᵱ Xᵱ |q⟩ where Xᵱ is the classical DFT of the amplitudes xₖ:
Action:
QFTₙ |ψ⟩ = Fₙ |ψ⟩
On basis kets:
QFTₙ |k⟩ = (1/√N) ∑ᵱ₌₀ⁿ⁻¹ ωₙᵱ𝒌 |q⟩
Here N = 2ⁿ where n is the number of qubits in the register.
N must be a power of 2. With n qubits we have N = 2ⁿ states: 2, 4, 8, 16,… This is exactly the setting of the classical Fast Fourier Transform.
Why is this powerful?
The QFT uses quantum superposition to process all 2ⁿ amplitudes in a single circuit pass. Gate count: O(n²) vs classical O(N log N) = O(n·2ⁿ) — an exponential saving.
Exponential gate savings: For n = 1024 qubits, classical FFT needs ~10³·2₁‰²⁴ operations. The QFT needs only n² ≈ 10&sup6; gates. This is the engine behind Shor’s algorithm.
Ex 2.1QFT for N = 2
For N = 2 (one qubit), ω₂ = −1. Compute F₂ from the matrix formula. What well-known gate is it?
F₂ =
F₂ = (1/√2)[[1,1],[1,ω₂]] = (1/√2)[[1,1],[1,−1]] = H (Hadamard!).
Section 03
QFT Circuit Derivation: From Formula to Gates
The central insight is that the QFT output has a product structure: each output qubit can be written as a single-qubit superposition, with a phase that depends only on a few bits of the input. We will derive this from the formula, then read off the gate circuit directly from the maths.
Step 1 — The product representation
Any integer k between 0 and N−1 can be written in binary: k = k₀ + 2k₁ + 4k₂ + … + 2ⁿ⁻¹kₙ₋₁ where each kᵢ is 0 or 1. We write the basis state as |k⟩ = |kₙ₋₁…k₁k₀⟩. After substituting k into the QFT formula and expanding, one finds:
Output qubit m gets superposition |0⟩ + eⁱ²𝝅·(binary fraction) |1⟩. The phase for qubit m depends only on kₘ, kₘ₋₁, …, k₀ — not all of k.
Binary fraction notation: 0.kₘkₘ₋₁…k₀ = kₘ/2 + kₘ₋₁/4 + … + k₀/2ⁿ. So eⁱ²𝝅·0.k₀ = eⁱ𝝅k₀ = (−1)𝒌₀. If k₀ = 0 the phase is +1; if k₀ = 1 the phase is −1. This is exactly what Hadamard does!
Step 2 — N = 2 (one qubit): QFT is Hadamard
For n = 1, k = k₀, and the product formula gives just one factor:
Formula:
QFT₂ |k₀⟩ = (1/√2) (|0⟩ + eⁱ𝝅k₀ |1⟩)
k₀ = 0:
e⁰ = 1 → output = (|0⟩+|1⟩)/√2 = |+⟩
k₀ = 1:
eⁱ𝝅 = −1 → output = (|0⟩−|1⟩)/√2 = |−⟩
Gate:
This is exactly H! H|0⟩ = |+⟩ and H|1⟩ = |−⟩. So QFT₂ = H.
F₂ = 1/√2
1
1
1
−1
= H
Hadamard is the 1-qubit QFT. Applying H to all n qubits in |0⟩⸾n creates the equal superposition (1/√N)∑|k⟩ — the all-at-once input needed by frequency-domain algorithms.
Phase = eⁱ𝝅k₀ = (−1)𝒌₀ — depends only on k₀. Gate: H applied to wire k₀. Done.
Second factor:
Phase = eⁱ²𝝅·0.k₁k₀ = eⁱ𝝅k₁ · eⁱ𝝅k₀/2 = (−1)𝒌¹ · eⁱ𝝅k₀/2
• (−1)𝒌¹ part: H applied to wire k₁
• eⁱ𝝅k₀/2 part: add phase ω₄𝒌₀ = j𝒌₀ to |1⟩, controlled by k₀ → controlled-Ω₄ gate
Circuit recipe:
1. H on wire k₁ → creates (−1)𝒌¹ factor 2. Controlled-Ω₄ (ctrl: k₀, target: k₁ wire) → adds eⁱ𝝅k₀/2 3. H on wire k₀ → creates (−1)𝒌₀ factor 4. Output in REVERSE order → add SWAP to fix.
The controlled phase gate Ωₙ: diag(1, ωₙ) — leaves |0⟩ unchanged, multiplies |1⟩ by ωₙ = eⁱ²𝝅/ₙ.
Ωₙ =
1
0
0
ωₙ
Ω₄ = S gate (ω₄=j) Ω₈ = T gate (ω₈=eⁱ𝝅/´) general: R₂(2π/N) up to global phase
Step 4 — N = 8 (three qubits): the staircase pattern
The pattern generalises perfectly. For 3 qubits, k = k₀ + 2k₁ + 4k₂. Each output qubit m needs H plus a cascade of controlled phase gates with decreasing angle, controlled by lower-order bits:
Output q₂ (MSB):
Phase = (−1)𝒌₀ — only k₀ matters. Gate: H on k₀.
Output q₁:
Phase = (−1)𝒌¹ · eⁱ𝝅k₀/2. Gates: H on k₁, then ctrl-Ω₄ from k₀.
Output q₀ (LSB):
Phase = (−1)𝒌² · eⁱ𝝅k₁/2 · eⁱ𝝅k₀/4. Gates: H on k₂, then ctrl-Ω₄ from k₁, then ctrl-Ω₈ from k₀.
|k₀⟩●——●—
H
|q₂⟩
|k₁⟩●—
H
Ω₄
|q₁⟩
|k₂⟩
H
Ω₄
Ω₈
|q₀⟩
Recursive structure: QFT₈ contains QFT₄ as a sub-circuit. Each new qubit adds one H and a column of controlled phase gates. This triangular staircase means total gate count = n(n+1)/2.
Output reversal: The product formula outputs qₙ₋₁…q₀ in reverse order. In many algorithms this reversal is absorbed into downstream connections, so explicit SWAP gates are often omitted.
Interactive circuit builder — drag gates to build QFT₄
Drag gates from the palette onto the circuit wires. As each gate is placed, the formula panel on the right updates to show exactly what that gate added to the mathematical state — so you can watch the product form being built step by step from the maths.
Drag gates →
H
Ω₄
Ω₈
⇄
Click a placed gate to remove it
|k₀⟩
×
×
×
×
|q₁⟩
|k₁⟩
×
×
×
×
|q₀⟩
State formula
|ψ⟩ = |k₁⟩ ⊗ |k₀⟩
Initial state: two qubits
in computational basis.
Drag gates to build QFT₄:
1. H on |k₁⟩ wire
2. Ω₄ on |k₁⟩ (ctrl=k₀)
3. H on |k₀⟩ wire
4. SWAP to correct order
Ex 3.1Identifying Ω₄
What standard gate equals Ω₄ = diag(1, j)?
Ω₄ =
Ω₄ = diag(1,j) = diag(1,eⁱ𝝅/²) = S gate.
Ex 3.2QFT₂ on |+⟩
Apply QFT₂ = H to |+⟩ = (|0⟩+|1⟩)/√2. What is the result?
QFT₂|+⟩ =
H|+⟩ = H·H|0⟩ = |0⟩. DFT of (1/√2,1/√2) = (1,0) — spike at q=0.
Section 04
QFT Complexity: Counting Gates
With the circuit structure derived, gate counting is straightforward.
For a 10-qubit QFT (N=1024), compute total H gates plus controlled phase gates.
Total gates =
H: 10. Ctrl-phase: 1+2+…+9 = 45. Total = 55.
Part II — Shor’s Algorithm
Section 05
Shor’s Algorithm: The Factoring Problem
Shor’s algorithm (1994) is the reason quantum computers threaten modern cryptography. It factors a large composite integer n in polynomial time, breaking RSA encryption.
The Factoring Problem
Input: Composite n (e.g. n=15=3×5) Output: Non-trivial factors Classical: Try all primes below √n — exponential in bit-length b = log₂(n).
Why is this hard classically? RSA uses n=p·q with 512-bit primes p, q. Naive approach needs ~2⁵¹² trials. More than atoms in the universe.
Reduction to order finding
Step 1
Pick random x with 1 < x < n. Compute gcd(x,n). If gcd > 1: stop, x is a factor (lucky!).
Step 2
Order finding (the quantum step): find smallest r such that xʳ mod n = 1.
Step 3
If r is odd, or (xʳ¹²+1) mod n = 0, go back to Step 1 with new x.
Step 4
gcd(xʳ¹²−1, n) and gcd(xʳ¹²+1, n) are non-trivial factors of n!
Worked example: n = 15
Pick x=2:
gcd(2,15)=1 → proceed.
Order:
2¹=2, 2²=4, 2³=8, 2⁴ mod 15 = 1 → r=4 (even ✓)
Check:
(2²+1) mod 15 = 5 ≠ 0 ✓
Factors:
gcd(3,15) = 3 ✓ gcd(5,15) = 5 ✓
Interactive: Order Finder
n =x =
Enter n and x, then click Find order.
Ex 5.1Order of 7 mod 15
Find smallest r such that 7ʳ mod 15 = 1.
r =
7¹=7, 7²=4 mod 15, 7³=13 mod 15, 7⁴=1 mod 15. So r=4.
Section 06
Why Does Order Finding Give Factors?
Start:
xʳ mod n = 1 ⇒ xʳ−1 = qn (divisible by n).
If r even:
xʳ−1 = (xʳ¹²+1)(xʳ¹²−1) = qn
Question:
Where are the factors of n in (xʳ¹²+1)(xʳ¹²−1)?
Case 1:
n cannot be all in (xʳ¹²−1): that would mean xʳ¹² mod n = 1, contradicting minimality of r.
Case 2:
n cannot be all in (xʳ¹²+1): excluded by Step 3.
Conclusion:
Factors of n split between the two terms. gcd(xʳ¹²±1, n) gives non-trivial factors. ∎
Classical bottleneck is Step 2. Finding order classically: try r=1,2,… Expected trials ≈ n/2 = 2ᵇ⁻¹ — exponential. RSA-1024: ~2₁‰‰‰ trials. The quantum speedup lives entirely here.
Ex 6.1Factors from order
n=15, x=7, r=4. Compute gcd(7²−1,15) and gcd(7²+1,15).
gcd(48,15)=gcd(50,15)=
48=3×15+3 → gcd=3. 50=3×15+5 → gcd=5.
Section 07
Period Finding: Linking Shor to QFT
Order finding is secretly period finding. Define f(ℓ) = xᵌ⸱ mod n. Then f(ℓ+r) = f(ℓ), so f has period r. Key FFT property: a signal with period P has DFT peaks at multiples of N/P.
Exact (N mod P=0):
Peaks exactly at m = 0, N/P, 2N/P, …, (P−1)N/P
Approximate:
Peaks near m ≈ ℓ·N/P for various ℓ
Periodic signal (top) and QFT spectrum (bottom). Peaks reveal the period P.
Period P:4N:
Multiple measurements: if gcd(P,ℓ)>1 we get only a divisor of P. Take several measurements and compute P = lcm(all denominators). Example: N=312, P=24. M₁=195 → 5/8, M₂=208 → 2/3. lcm(8,3)=24=P ✓
Ex 7.1Extract period
N=240, P=20 (unknown). Measurement gives M=120. Compute C=M/N. Is the denominator equal to P?
C =denom=
C=120/240=1/2. Denominator=2, a divisor of P=20. Need another measurement to recover P=20.
Section 08
Continued Fractions: When N mod P ≠ 0
When N is not divisible by P, QFT peaks are only approximate. We get M and know M/N ≈ ℓ/P. The continued fraction algorithm finds the exact fraction.
Continued Fraction Algorithm
r₀/r₁ = q₀ + 1/(q₁ + 1/(q₂ + …)) where qᵢ = ⌊rᵢ/rᵢ₊¹⌋, rᵢ₊¹ = rᵢ₋¹ mod rᵢ. Truncating early gives approximations whose denominators are candidates for P.
Worked example: N=256, P=10, M=77
C = 77/256:
≈ 0.30078 (true ratio ℓ/P = 3/10 = 0.3)
Expand:
77/256 = 0+1/(3+1/(3+2/25))
Truncate (drop 2/25):
77/256 ≈ 1/(3+1/3) = 3/10 denominator 10 = P ✓
Interactive: Continued Fraction Calculator
M=N=
Enter M and N, then click Expand.
Ex 8.1Continued fraction
N=100, M=33. Best rational approximation of 33/100 with denominator below 100?
Best approx =
33/100 = 0+1/(3+1/33) ≈ 1/3. Denominator 3 is the P candidate.
Section 09
Shor: Full Circuit and Complexity
Initial:
|ψ₀⟩ = |0⟩⸾log₂N ⊗ |0⟩⸾log₂n
After H⸾n:
(1/√N) ∑ₖ |0⟩|k⟩
After U𝑓:
(1/√N) ∑ₖ |xᵉ mod n⟩|k⟩
Measure f(ℓ):
Periodic state with period r
Apply QFTₙ:
Peaks at multiples of N/P
Measure M:
Use continued fractions to find P = r. Done!
n=15, x=7 example
Setup:
N=1024, P=4, N/P=256
|ψ₁⟩:
(1/√N)(|1⟩|0⟩+|7⟩|1⟩+|4⟩|2⟩+|13⟩|3⟩+|1⟩|4⟩+…)
Measure |4⟩:
Collapses to period-4 state (positions 2,6,10,…)
M=768:
768/1024=3/4 → P=4. gcd(48,15)=3, gcd(50,15)=5 ✓
Complexity
QFT gates:
≈ b²
U𝑓 gates:
≈ b³ (modular exponentiation)
Total:
O(b³) — polynomial! vs Classical O(b·2ᵇ)
Ex 9.1Shor vs classical
For b=1024 bit RSA, estimate log₁‰(classical gates / Shor gates).
Grover’s algorithm (1996) solves unstructured search with a quadratic quantum speedup. Given N items and one special target x*, classically you need N/2 checks on average. Grover does it in about √N steps.
The Search Problem
Given: f: {0,…,N−1} → {0,1} with exactly one x* where f(x*)=1. Find: x*. Classical: N/2 evaluations. Quantum: O(√N).
Repeat Steps 2–3 ≈ √N times, then measure → x* with probability ≈ 1.
Amplitude distribution. Step through to see the oracle flip and diffusion amplification in action.
Ex 10.1Oracle action
What does U𝑓 do to |x*⟩ where f(x*)=1?
U𝑓|x*⟩ =
U𝑓|x⟩ = (−1)𝑓⁺𝒙⁻|x⟩. For x=x*, f(x*)=1, so U𝑓|x*⟩ = −|x*⟩.
Section 11
The Diffusion Operator: Inversion about the Mean
After U𝑓 flips the phase of x*, the diffusion operator U𝒊 converts this phase flip into an amplitude boost by reflecting every amplitude about the current mean μ.
Diffusion Operator
U𝒊 = 2|s⟩⟨s| − I where |s⟩ = H⸾n|0⟩ = 1/√N ∑ₖ |x⟩
Action on ∑ₖ αₖ |x⟩: each amplitude αₖ → 2μ − αₖ, where μ = (1/N)∑ₖ αₖ is the mean.
Why this amplifies x*
Before U𝑓:
All αₖ = 1/√N. Mean μ = 1/√N.
After U𝑓:
αₖ* = −1/√N; αₖ = +1/√N for x≠x*. New mean μ ≈ (N−2)/(N√N).
Geometric picture: Inversion about the mean is a reflection. x* sits below the mean (negative amplitude), so reflecting about the mean throws it upward by twice the distance. Each round amplifies x* by ~2/√N.
Precise calculation for one round
After round r:
Amplitude of x* ≈ (2r+1)/√N → P(x*) = (2r+1)²/N
U𝒊 is unitary: U𝒊†U𝒊 = (2|s⟩⟨s|−I)² = 4|s⟩⟨s|s⟩⟨s| − 4|s⟩⟨s| + I = I ✓ (using ⟨s|s⟩=1)
Ex 11.1Amplitude after one round, N=4
For N=4 after U𝑓: αₖ* = −1/2, αₖ = +1/2 for the other 3 states. Mean μ = (−1/2+3·1/2)/4 = 1/4. Compute x* amplitude after U𝒊.
αₖ* after U𝒊 =
2μ − αₖ* = 2·(1/4) − (−1/2) = 1/2 + 1/2 = 1. P(x*) = 1² = 100%! Grover finds x* in ONE round for N=4.
Section 12
Optimal Rounds and Summary
How many rounds?
After r rounds the x* amplitude is ≈(2r+1)/√N. For P(x*)≈1 we need (2r+1)²≈N, giving:
Optimal rounds:
r ≈ (π/4)√N
Complete circuit
|0⟩ⁿ
H⸾n
U𝑓
U𝒊
U𝑓
U𝒊
…×√N…
M
x* w.p. ≈ 1
Interactive: Grover Probability Simulator
N=x*=
Click Start to initialise.
Algorithm summary
U𝑓|x⟩
= (−1)𝑓⁺𝒙⁻ |x⟩ (phase oracle)
U𝒊
= 2|s⟩⟨s| − I (diffusion = inversion about mean)
|s⟩
= (1/√N) ∑ₖ |x⟩ = H⸾n|0⟩
Speedup:
Classical N/2 → Quantum O(√N) — quadratic speedup
Ex 12.1Grover rounds for N=64
Use r ≈ (π/4)√N to compute the number of rounds for N=64.
r ≈
r ≈ (π/4)·8 ≈ 6.28 → r ≈ 6 rounds.
Ex 12.2Shor vs Grover speedup
Which provides a greater speedup: Shor or Grover?
Answer:
Shor: exponential speedup O(b³) vs O(b·2ᵇ). Grover: quadratic speedup O(√N) vs O(N). Shor’s advantage is vastly greater.