Shor’s Algorithm and Grover’s Algorithm Explained

Quantum computing · algorithm deep dive

Grover's & Shor's
Algorithms Explained

How quantum computers use superposition, phase, and interference to solve search and factoring problems — with worked examples and honest caveats.

constructive & destructive interference — the core mechanism of both algorithms

Foundation

Classical bits vs quantum qubits

A classical computer works with bits — each one is definitively 0 or 1. A quantum computer works with qubits, whose state before measurement is described by amplitudes, not certainties.

Classical bit

0 or 1

Always one definite value. No uncertainty until you look — it already is one or the other.

Quantum qubit

|0⟩ + |1⟩

Described by amplitudes for both outcomes. The probabilities are |a|² and |b|², and they must sum to 1.

One-qubit state |ψ⟩ = a|0⟩ + b|1⟩    where   |a|² + |b|² = 1

The Hadamard gate (H) turns a definite |0⟩ into a 50/50 superposition — equal amplitude for both outcomes:

H|0⟩ = (|0⟩ + |1⟩) / √2

Two qubits give four possible states simultaneously. Three qubits give eight. In general, n qubits span 2ⁿ states in superposition — this exponential space is what quantum algorithms exploit.

---

Grover's Algorithm

Searching by amplitude amplification

Imagine a database of N unsorted items with exactly one correct answer. A classical computer must check items one by one — on average N/2 checks. Grover's algorithm finds the answer in roughly √N steps by repeatedly making the correct answer's amplitude louder and all others quieter.

Step 1 — equal superposition

Apply H to all qubits. For 2 qubits (4 states) every state gets amplitude ½. No state is preferred yet.

|ψ⟩ = ½|00⟩ + ½|01⟩ + ½|10⟩ + ½|11⟩

Step 2 — oracle phase flip

The oracle is a circuit that knows the answer (without revealing it). It flips the phase of the target state — multiplies its amplitude by −1. This doesn't change measurement probabilities yet (|−½|² = |½|²), but it marks the answer in a way the next step can exploit.

|00⟩

+½

|01⟩

+½

|10⟩ ★

−½

|11⟩

+½

After oracle: |10⟩ (our target) has its phase flipped to −½. Other amplitudes unchanged.

Step 3 — diffusion (reflect about the mean)

The diffusion step reflects all amplitudes about their average value. The average after the oracle is (+½+½−½+½)/4 = +⅜. Each amplitude becomes: 2 × average − original amplitude.

Why this amplifies the target: the target's amplitude is below the mean (it's −½ while others are +½). Reflecting below-mean values pushes them far above the mean. Reflecting above-mean values pushes them slightly below. Repeat a few times and the target dominates.

After one Grover iteration on 4 states:

|00⟩

0

|01⟩

0

|10⟩ ★

+1

|11⟩

0

After diffusion: |10⟩ has amplitude 1 — measurement gives the correct answer with certainty.

The speedup

For N possible states, Grover needs about (π/4)√N iterations:

Classical average

524,288

checks for N = 1,048,576

Grover's algorithm

≈ 804

(π/4)√1,048,576 quantum rounds

⚠ Grover does not break modern encryption on its own

The quadratic speedup doubles the effective key length an attacker must search. AES-128 becomes roughly as hard as AES-64 under Grover — serious, but addressed simply by using AES-256. It is not an existential threat to symmetric cryptography.

---

Shor's Algorithm

Factoring by finding hidden periods

RSA encryption is secure because multiplying two large primes is easy, but finding those primes from their product is computationally infeasible for classical computers. Shor's algorithm turns factoring into a period-finding problem — and period-finding is something a quantum computer can do exponentially faster via the Quantum Fourier Transform.

The key insight: f(x) = aˣ mod N is periodic

Pick a random number a coprime to N. The function f(x) = aˣ mod N always repeats with some period r. Once you know r, simple number theory (GCD) gives you the factors of N. The hard part for classical computers is finding r for large N.

Worked example: factor N = 15, pick a = 2 f(x) = 2ˣ mod 15

x	2ˣ	2ˣ mod 15	note
0	1	1	start
1	2	2
2	4	4
3	8	8
4	16	1	← repeats, r = 4
5	32	2	← repeats
6	64	4	← repeats
7	128	8	← repeats

Period r = 4. Now apply the factoring step:

a^(r/2) = 2² = 4

gcd(4 − 1, 15) = gcd(3, 15) = 3    gcd(4 + 1, 15) = gcd(5, 15) = 5

15 = 3 × 5 ✓
Two conditions must hold for this to work: r must be even, and a^(r/2) must not equal −1 mod N. If they fail, pick a different a and retry. The probability of succeeding is high — typically > 50% per attempt.

Where the quantum computer enters

Finding r classically for huge N would take roughly as long as factoring directly. Shor's algorithm evaluates f(x) on all x values simultaneously using superposition, then uses the Quantum Fourier Transform to extract r from the resulting interference pattern.

1

Create superposition

Apply H to an input register. All possible x values now exist as equal amplitudes simultaneously.

2

Compute f(x) = aˣ mod N

A quantum circuit evaluates f(x) for all x at once, entangling the output register with the input. The function's periodic structure is now encoded in the combined quantum state.

3

Apply Quantum Fourier Transform

The QFT acts like a Fourier transform on amplitudes. Interference between the periodic copies constructively adds up at frequencies that are multiples of 1/r, cancelling everywhere else.

4

Measure and extract r

Measurement yields a value related to 1/r. Classical continued-fractions arithmetic recovers r exactly. A few repetitions give high confidence.

5

Classical GCD to find factors

gcd(a^(r/2) ± 1, N) — standard arithmetic, runs in microseconds.

The Quantum Fourier Transform in plain terms

Hidden periodic signal

The quantum state holds amplitudes arranged in a repeating pattern with period r — invisible to direct measurement.

→

QFT

Quantum gates create constructive interference at period-related frequencies, destructive everywhere else. The same idea as a Fourier transform in signal processing — but acting on probability amplitudes.

→

Period is now measurable

The output state concentrates amplitude at multiples of 1/r. Measurement gives you the period.

⚠ Shor's algorithm is a real threat to RSA — but not yet

Shor's algorithm would break RSA-2048 in polynomial time. However, running it on a 2048-bit number requires thousands of logical (error-corrected) qubits, which translates to millions of physical qubits with today's error rates. Current hardware tops out around a thousand noisy physical qubits — far short. Post-quantum cryptography (NIST-standardized algorithms like CRYSTALS-Kyber) exists precisely to prepare for the day this gap closes.

---

Side by side

Grover vs Shor

	Grover's Algorithm	Shor's Algorithm
Problem	Unstructured search (find one item in N)	Integer factoring / discrete logarithm
Core technique	Oracle + diffusion (amplitude amplification)	Modular exponentiation + Quantum Fourier Transform
Speedup type	Quadratic: O(√N) vs O(N)	Exponential: polynomial vs sub-exponential classical
Quantum idea	Constructive interference on the target via repeated reflection	Constructive interference on period-related frequencies via QFT
Cryptographic impact	Halves effective key strength of symmetric ciphers (addressable)	Breaks RSA, ECC, DH completely (existential threat)
Hardware needed (today)	Fewer qubits; useful with smaller machines	Millions of physical qubits for real RSA key sizes
Practical status	Demonstrated on small instances; scaling unclear	Largest demonstrated: factor 21; not cryptographically relevant

---

Takeaway

The one idea behind both

Neither algorithm "magically" knows the answer. Both work by engineering quantum states so that amplitudes for wrong answers cancel out (destructive interference) and amplitudes for right answers add up (constructive interference). Measurement then returns the answer with high probability.

quantum algorithm =

superposition + phase + interference + measurement

Grover uses amplitude amplification: repeatedly reflect about the mean until the target's amplitude towers above everything else. Shor uses period extraction: encode a periodic function into quantum amplitudes, then let the QFT concentrate those amplitudes onto the period. Both are interference engines — they shape probability, not certainty.