Interactive Notes

Quantum Algorithms:
Deutsch & Shor

From the first quantum algorithm in history to the one that threatens modern cryptography.

Contents

Section 01

Deutsch's Algorithm — The First Quantum Algorithm in History

In 1985, David Deutsch published the first quantum algorithm ever devised. It is beautifully simple, yet it captures the essence of quantum advantage: solving a problem with one query to a black box where a classical computer would need two. This algorithm directly inspired Shor's factoring algorithm a decade later.

The Problem

You are given a black-box function f : {0,1} → {0,1}. You cannot see inside the box — you can only feed it an input and read the output. Your task: determine whether f(0) = f(1) (constant) or f(0) ≠ f(1) (balanced), using as few calls to f as possible.

There are exactly four possible functions of this type:

CONSTANT 0 x f(x) 0010 CONSTANT 1 x f(x) 0111 BALANCED (ID) x f(x) 0011 BALANCED (NOT) x f(x) 0110

x	f(x)
0	0
1	0

x	f(x)
0	0
1	1

Classical approach: You must call f twice — once with input 0, once with input 1 — and compare the results. There is no shortcut: after a single call, you simply don't have enough information to decide.

The Quantum Oracle U_f

The quantum version of the black box acts on two qubits: an input register |x⟩ and an ancilla register |y⟩. It computes:

U_f |x⟩|y⟩ = |x⟩|y \oplus f(x)⟩ where \oplus is addition modulo 2 (XOR) x y x y \oplus f(x) 0 0 0 0 \oplus f(0) = f(0) 0 1 0 1 \oplus f(0) = f̄(0) 1 0 1 0 \oplus f(1) = f(1) 1 1 1 1 \oplus f(1) = f̄(1) Invertible? Yes! Apply U_f twice: |x⟩|y⟩ \to |x⟩|y\oplusf(x)⟩ \to |x⟩|y\oplusf(x)\oplusf(x)⟩ = |x⟩|y⟩ ✓ (since a\oplusa = 0)

The Deutsch Circuit

The circuit uses a clever trick: if we put the ancilla qubit in the state |−⟩ = (|0⟩−|1⟩)/√2, the oracle "kicks back" the phase of f(x) into the input register — without ever collapsing it.

|0⟩

U_f

"0" if f(0)=f(1)
"1" if f(0)≠f(1)

|1⟩

U_f

(ancilla, not measured)

Step-by-Step Calculation

Initial state: |0⟩|1⟩ After H\otimesH: |+⟩|-⟩ = 1/2 (|0⟩+|1⟩)(|0⟩-|1⟩) = 1/2 (|00⟩-|01⟩+|10⟩-|11⟩) After U_f: |0,f(0)⟩ + |1,f(1)⟩ - |0,f̄(0)⟩ - |1,f̄(1)⟩ (unnorm.) Regroup: = |0⟩(|f(0)⟩-|f̄(0)⟩) + |1⟩(|f(1)⟩-|f̄(1)⟩) Key trick: Note |f(x)⟩-|f̄(x)⟩ = \pm(|0⟩-|1⟩) = \pm|-⟩\cdot\sqrt2, so the sign is (-1) f(x) . Therefore state \propto (-1) f(0) |0⟩ + (-1) f(1) sup>|1⟩, times |-⟩. If f(0)=f(1): First register \propto (-1) f(0) (|0⟩+|1⟩) = |+⟩ \to After H: |0⟩ \to measure "0" If f(0)\neqf(1): First register \propto (-1) f(0) (|0⟩-|1⟩) = |-⟩ \to After H: |1⟩ \to measure "1"

The quantum advantage in one sentence: By putting the input into superposition, U_f evaluates f(0) and f(1) simultaneously. The subsequent Hadamard gate interferes these two evaluations: they add constructively for the correct answer and cancel for the wrong one. This is the blueprint for every quantum algorithm that follows — including Shor's.

One oracle call vs two: Classically, you need 2 calls. Quantum: exactly 1 call suffices. This is a provable quantum advantage — not just a speedup in practice, but a fundamental difference in query complexity.

Select a function f and see what happens at each step of the circuit.

Choose f:

Ex 1.1Phase kickback

When the ancilla is in state |−⟩ and we apply U_f, the result is (−1)^f(x)|x⟩|−⟩. This is called "phase kickback." What is the phase when f(x) = 1?

Phase factor:

(−1)^f(x). If f(x)=1 then (−1)¹ = −1.

Ex 1.2How many oracle calls?

Classically, how many evaluations of f are needed in the worst case to determine if f is constant or balanced?

Answer:

Section 02

Factorization = Order Finding

Shor's algorithm (1994) is the most famous quantum algorithm. Its primary application: factor large integers efficiently. This threatens RSA encryption, which relies on the difficulty of factoring numbers that are products of two large primes.

Why factoring is hard classically: To factor n, the naive approach tries all primes less than n — roughly √n candidates. For a 1024-bit RSA number, that's about 2^>512 trials. The best known classical algorithm still runs in sub-exponential but super-polynomial time — impractical for large n.

The Key Insight: Reduction to Order Finding

Shor's brilliant observation is that factoring reduces to finding the "order" of an element in modular arithmetic. This connection transforms an apparently number-theoretic problem into a signal processing problem.

The Algorithm (4 steps)

Choose a random x ∈ ℤ, x < n.
If gcd(x,n) > 1 → x is already a factor of n! (Lucky stop.)
Find the order r: the smallest r such that x^r mod n = 1. (⟵ THE HARD STEP)
If r is odd, or if (x^r/2+1) mod n = 0 → go back to step 1.
Compute gcd(x^r/2−1, n) and gcd(x^r/2+1, n). These are non-trivial factors of n!

Why Does This Work?

Start: x r mod n = 1 ⟹ x r = q\cdotn + 1 ⟹ x r - 1 = q\cdotn If r even: (x (r/2) - 1)(x (r/2) + 1) = q\cdotn Therefore: n divides the product (x (r/2) -1)(x (r/2) +1). If neither factor is divisible by all of n, then gcd extracts the factor we want. Why not trivial? n cannot have all its factors inside x r/2 -1 alone, because that would mean x r/2 mod n = 1, contradicting r being the smallest such integer (by definition of order). Similarly for x (r/2) +1 (the step ③ condition eliminates this case).

gcd is cheap! The Euclidean algorithm computes gcd(a,b) in O(log²(n)) time — polynomial. So steps ①, ③, ④ are all easy. The entire difficulty concentrates in step ②: finding the order r. That's exactly what Shor's quantum algorithm solves.

Enter n and x to trace through the factoring algorithm. (Works for small numbers.)

n: x:

Ex 2.1Why is step ③ needed?

Step ③ says: if r is odd, restart. Why can't we use an odd r in step ④?

Because x^(r/2) needs to be an integer. If r is odd, r/2 is not an integer and x^(r/2) mod n is undefined. We need r to be even so that x^(r/2) ∈ ℤ.

Ex 2.2Verify the factoring of 15

For n=15 and x=7: the order is r=4 (meaning 7⁴ mod 15 = 1). Compute gcd(7²−1, 15) = gcd(48, 15). What factor do you get?

gcd(48,15) =

48 = 3×16, 15 = 3×5. gcd(48,15) = 3. And gcd(50,15) = 5. So factors of 15 are 3 and 5. ✓

Section 03

Order Finding = Period Finding

The order problem has a beautiful signal-processing interpretation. Let's define the function:

The Modular Exponentiation Function

f(ℓ) = x ℓ mod n ℓ = 0, 1, 2, ...

This function is periodic with period r:

f(ℓ) = x ℓ mod n = x (ℓ+r) mod n = f(ℓ+r) for all ℓ Because x r mod n = 1, so multiplying by x r changes nothing.

The chain of reductions:

Factoring n \equiv Order finding of x mod n (for random x) Order finding \equiv Period finding of f(ℓ) = x ℓ mod n Period finding \equiv Finding peaks in the Fourier transform of f

Modular exponentiation f(ℓ) = x^ℓ mod n — observe the periodic pattern.

n: x:

Ex 3.1Find the period

Compute f(ℓ) = 2^ℓ mod 7 for ℓ = 0,1,2,3,4,5. What is the period r?

r =

2⁰ =1, 2¹ =2, 2² =4, 2³ =1 (mod 7). So r=3 (the sequence 1,2,4 repeats).

Section 04

Period Finding with Fourier Transforms

You already know this idea from signal processing: a periodic signal has a spectrum with sharp lines. We'll use the Discrete Fourier Transform (DFT) to detect the period.

Continuous time analogy

A continuous signal with period T has a Fourier transform with lines at frequencies f₀ = 1/T, 2f₀, 3f₀, ... This is the Fourier series. For a discrete signal of length N with period P (where P < N):

Key DFT Result

If x_k = x_k+P (periodic with period P), and N = P·M (P divides N exactly), then the DFT has peaks exactly at:

m = 0, M, 2M, 3M, ..., (P-1)M i.e. m = ℓ \cdot (N/P) for ℓ \in ℤ

So if we observe a peak at position m, we know:

m/N \approx ℓ/P ⟹ P \approx N\cdotℓ/m

By simplifying the fraction m/N we can recover P (= the denominator after simplification)!

What if P does not divide N exactly? The peaks appear near ℓ·N/P but are slightly broadened (like a sinc function). In that case, we find an approximation m/N ≈ ℓ/P, and use the continued fraction algorithm to extract the exact denominator P from the rational approximation.

Multiple measurements to handle common factors

When we simplify m/N, we might lose factors. For example, if N=240, P=20, and we see m=12 (corresponding to ℓ=1), then m/N = 12/240 = 1/20 ✓. But if ℓ=2 we'd see m=24, and 24/240 = 1/10 — we recover only a factor of P=20, not P itself.

Solution: collect multiple measurements m₁, m₂, ... Each gives a (possibly partial) factor of P. The true period P = lcm(P₁, P₂, ...) where P_i is the denominator after simplifying m_i/N. After a few measurements we recover P with high probability.

DFT of the periodic sequence f(ℓ) = x^ℓ mod n. The peaks reveal the period.

n: x: N:

Section 05

Classical Period Finding — Why It Fails

The algorithm using DFT to find the period looks promising. But let's check its classical complexity.

Classical Period Finding Algorithm

Given a sequence x_k with period P < Q (where Q is a known upper bound on P):

Choose N > Q² (for the continued fraction step to work reliably).
Compute the DFT of the length-N sequence.
Find a peak at position m; compute m/N and extract P via continued fractions.
Verify: if x_k+P = x_k for all k, stop. Otherwise collect more measurements and take the lcm.

Why it's exponential classically

Step ②: Classical DFT costs O(N log₂N). If N is b bits \to N \approx 2 b \to cost = O(b \cdot 2 b). Exponential in b! Step ③: Even finding the peak requires examining N entries. Again exponential. Example: For RSA n = 1024 bits, we need N \approx 2 2048 . Storing the sequence alone requires 2 2048 entries. That's more atoms than in the observable universe!

Period finding with classical FT is completely impractical. The exponential blowup from having to store and process N ≈ 2^2b values makes this approach useless for large inputs. This is precisely where the Quantum Fourier Transform saves the day.

The QFT costs only O(b²) gates on b qubits. Instead of computing N = 2^b amplitudes explicitly, the quantum circuit implicitly operates on a superposition encoding all 2^b values simultaneously. The cost is polynomial, not exponential.

Section 06

Order Finding with QFT — Shor's Algorithm

Here is the actual quantum circuit. It has three stages, labeled ①②③ in the notes.

Setup

Given x and n, choose N > n² (so that N has at least log₂(n²) = 2b bits, where b = ⌈log₂n⌉). We need ≈ log₂N ≈ 2b qubits for the first register (the frequency register). We need ⌈log₂n⌉ = b qubits for the second register (to store x^ℓ mod n).

The Circuit

Stage ① — Create Superposition and Apply Oracle

Start: |0⟩ \otimeslog₂N \otimes |0⟩ \otimesb Apply H \otimeslog₂N on register 1: 1/\sqrtN Σ k=0 N-1 |k⟩|0⟩ Apply U_f: 1/\sqrtN Σ k=0 N-1 |k⟩|x k mod n⟩ (quantum parallelism: all values computed at once!)

The function f(k) = x^k mod n is periodic with period r (the order we want to find). So the second register cycles through the values 1, x, x², ..., x^r−1, 1, x, ... repeatedly.

Stage ② — Measure the Second Register

Measure 2nd register: Say we get result f(a) = x a mod n (for some random a \in [0, r)). Collapse: The first register collapses to all k compatible with f(k) = f(a), i.e. k = a, a+r, a+2r, ..., a+(M-1)r. (M \approx N/r terms) First register: 1/\sqrtM (|a⟩ + |a+r⟩ + |a+2r⟩ + ... + |a+(M-1)r⟩)

This is a periodic quantum state! The first register is now a uniform superposition of arithmetic progression {a, a+r, a+2r, ...}. We can't read r directly because a is unknown. But its Fourier transform has peaks at multiples of N/r — that's stage ③.

Stage ③ — Apply QFT and Measure

Apply QFT: QFT maps the periodic state in the first register to a state concentrated near m = ℓ·N/r for integer ℓ. Measure m: Read an integer m ≈ ℓ·N/r with high probability. Extract r: m/N ≈ ℓ/r. Use the continued fraction algorithm to find the best rational approximation with denominator ≤ Q ≈ n → this gives the denominator r.

Why N > n² = Q²? The continued fraction algorithm is guaranteed to recover the exact fraction ℓ/r from a rational approximation p/q if |p/q − ℓ/r| < 1/(2r²). Choosing N > r² ≤ n² ensures the approximation m/N is close enough for this to work.

Ex 6.1Why measure the second register?

After the oracle U_f, we have a superposition of all |k⟩|f(k)⟩. Why do we measure the second register before applying the QFT?

Measuring the second register collapses the first register to a purely periodic state — a uniform superposition of {a, a+r, a+2r, ...}. Without this collapse, the first register is entangled with the second and the QFT would not give clean peaks at multiples of N/r.

Section 07

QFT of the First Register — The Calculation

Let's work out what the QFT produces when applied to the periodic state from stage ②.

Case 1: P divides N exactly (N = P·M)

Input state: 1/\sqrtM (|a⟩ + |a+r⟩ + |a+2r⟩ + ... + |a+(M-1)r⟩) = 1/\sqrtM Σ d=0 M-1 |a+dr⟩ QFT output: Σ q=0 N-1 X q |q⟩ where X q = 1/\sqrtN Σ k=0 N-1 x k ω N -kq Compute X q : X q = 1/\sqrt(NM) Σ d=0 M-1 ω N (a+dr)q = 1/\sqrt(NM) ω N aq Σ d=0 M-1 (ω N rq) d Let α = ω N rq : where ω N = e j2π/N, ω N rq = e j2πrq/N . If r = N/P = M (i.e. q is a multiple of M), then α = e j2πq/M = e j2π\cdotinteger = 1. Result: |X q | = 1/\sqrtP if q = ℓ\cdot(N/P) for some integer ℓ, and |X q | = 0 otherwise. ⟹ exactly P peaks of equal height 1/\sqrtP, at positions 0, N/P, 2N/P, ..., (P-1)\cdotN/P

The QFT perfectly separates the P peaks when P | N. Each peak has amplitude 1/√P, so measurement probability 1/P for each — a uniform distribution over P possible outcomes. Any outcome m = ℓ·N/P gives m/N = ℓ/P, from which we recover P.

Case 2: P does not divide N

In general, N/P is not an integer. The peaks are broadened by a sinc-like envelope:

|X q | \approx 1/\sqrt(NM) |Σ d=0 M-1 α d | = 1/\sqrt(NM) |1 - α M |/|1 - α| where α = e j2πrq/N = ratio of sinc: \approx 1/\sqrtN |sin(πMrq/N)| / |sin(πrq/N)|

This still has peaks near q = ℓ·N/P, and measurement gives m ≈ ℓ·N/P with high probability. The continued fraction method recovers r from the rational approximation m/N ≈ ℓ/r.

QFT output |X_q|² for periodic f(ℓ) = x^ℓ mod n. Red lines mark the ideal peak positions ℓ·N/P.

x: n: N:

Ex 7.1Number of peaks

If the order of x mod n is r = P = 4 and we choose N = 1024 (so that P | N), how many distinct peaks appear in the QFT output? At what positions?

# peaks:

There are P=4 peaks, at q = 0, N/4=256, 2N/4=512, 3N/4=768. Each with amplitude 1/√P = 1/2 and probability 1/P = 25%.

Section 08

Complexity of Shor's Algorithm

Summary of Resources

Let b = ⌈log₂n⌉ (number of bits to represent n). Then:

Component Qubits Gates QFT (register 1) log₂N \approx 2b (linear in b) (log₂N)² \approx 4b² (poly in b) Modular exp U f log₂n = b + ancilla O((log₂n)³) = O(b³) (poly in b) Total \approx 2b qubits O(b³) gates

Modular Exponentiation — how it's implemented

Computing f(a) = x^a mod n for a superposition of a values requires an efficient quantum circuit. We write a in binary: a = a₀ + a₁·2 + a₂·4 + ... and precompute:

Precompute: C i = x 2 i mod n for i = 0, 1, ..., b-1 (classical precomputation) Then: x a = C 0 a₀ \cdot C 1 a₁ \cdot ... \cdot C b-1 a b-1 (mod n) Circuit: A sequence of b controlled modular multipliers, each conditioned on one bit a i .

Each controlled modular multiplier costs O(b²) operations (using binary multiplication), so the total U_f circuit costs O(b · b²) = O(b³). This dominates the QFT cost of O(b²).

Comparison with Classical Algorithms

Classical — Best Known General Number Field Sieve: exp(O(b 1/3 (log b) 2/3)) Sub-exponential but still super-polynomial Shor's Quantum Algorithm O(b³) Polynomial! ~2b qubits needed Example: RSA-1024 (b=1024 bits): Classical: ~2 (30 to 50) operations (impractical) Shor's: ~b³ \approx 10⁹ operations with 2048 qubits (feasible with fault-tolerant hardware)

This is an exponential speedup. Not just a constant or polynomial improvement — a genuine exponential gap. If cryptographically relevant quantum computers are built, RSA and related systems would be broken. This has driven massive investment in post-quantum cryptography.

Complexity comparison: classical O(2^b) vs Shor's O(b³). Drag the slider to see how they diverge.

b (bits): 10

Section 09

Full Example: Factoring n = 15

Let's trace through Shor's algorithm step by step for n = 15, x = 7.

Setup

n = 15: 4 bits to represent 15 \to b = 4 Choose N: N > n² = 225 \to choose N = 1024 = 2 10 \to log₂N = 10 qubits for register 1 Choose x: x = 7, gcd(7, 15) = 1 ✓ (not a factor yet) Register 2: ⌈log₂15⌉ = 4 qubits (to store values 0-14)

Stage ① — The Periodic Function

ℓ	7^ℓ mod 15
0	1
1	7
2	4
3	13
4	1 ← period!
5	7
⋮	⋮

The period is r = 4. The sequence 1, 7, 4, 13 repeats every 4 steps.

After applying H^⊗10 and then U_f, the state is:

1/\sqrt1024 Σ k=0 1023 |k⟩|7 k mod 15⟩ = 1/\sqrt1024 (|0⟩|1⟩ + |1⟩|7⟩ + |2⟩|4⟩ + |3⟩|13⟩ + |4⟩|1⟩ + ...)

Stage ② — Measure Second Register

Say we measure f(·) = 4. The first register collapses to all k where 7^k mod 15 = 4, i.e. k = 2, 6, 10, 14, ..., (2 + 4j):

1/\sqrt256 (|2⟩ + |6⟩ + |10⟩ + |14⟩ + ... + |1022⟩) (M = 1024/4 = 256 terms)

Stage ③ — QFT and Measure

Since P = 4 divides N = 1024 exactly, M = 256 and the peaks are at q = 0, 256, 512, 768.

Peaks at: m = 0, 256, 512, 768 (each with probability 1/4 = 25%) Assume m = 768: m/N = 768/1024 = 3/4 \to ℓ/r = 3/4 \to r = 4 ✓

Extract Factors

r = 4 (even ✓): x r/2 = 7² = 49: 49 mod 15 = 4 (so (x r/2 +1) mod 15 = 5 \neq 0 ✓) gcd(49-1, 15): gcd(48, 15) = gcd(15, 48 mod 15) = gcd(15, 3) = 3 gcd(49+1, 15): gcd(50, 15) = gcd(15, 50 mod 15) = gcd(15, 5) = 5 Result: 15 = 3 \times 5 ✓

Interactive: Run Shor's Algorithm

n: x:

Ex 9.1Interpreting the measurement result

For n=15, x=7, r=4, N=1024, suppose we measure m = 256 from the QFT. What fraction m/N simplifies to, and what is r?

m/N = 256/1024 = → r =

256/1024 = 1/4 (simplify by dividing both by 256). So m/N = ℓ/r = 1/4 → r = 4.

Quantum Algorithms:Deutsch & Shor

Deutsch's Algorithm — The First Quantum Algorithm in History

The Quantum Oracle Uf

The Deutsch Circuit

Step-by-Step Calculation

Factorization = Order Finding

The Key Insight: Reduction to Order Finding

Why Does This Work?

Order Finding = Period Finding

Period Finding with Fourier Transforms

Continuous time analogy

Multiple measurements to handle common factors

Classical Period Finding — Why It Fails

Why it's exponential classically

Order Finding with QFT — Shor's Algorithm

The Circuit

Stage ① — Create Superposition and Apply Oracle

Stage ② — Measure the Second Register

Stage ③ — Apply QFT and Measure

QFT of the First Register — The Calculation

Case 1: P divides N exactly (N = P·M)

Case 2: P does not divide N

Complexity of Shor's Algorithm

Modular Exponentiation — how it's implemented

Comparison with Classical Algorithms

Full Example: Factoring n = 15

Setup

Stage ① — The Periodic Function

Stage ② — Measure Second Register

Stage ③ — QFT and Measure

Extract Factors

Quantum Algorithms:
Deutsch & Shor

The Quantum Oracle U_f