Your objective
Summarize Shor’s algorithm, focus on the period‑finding subroutine, and understand how it leads to integer factorization.
8.1 Period‑Finding Reduction
To factor N, pick a random a coprime to N and find r such that aʳ ≡ 1 (mod N). The factors emerge from r.
Pick a → Compute aʳ mod N → r = period
8.2 Quantum Period Finding
Prepare a superposition over x, compute aˣ mod N in the second register, then apply QFT to the first register to reveal r.
|0⟩ → H^{⊗n} → |x⟩ → Uₐ → |x, aˣ mod N⟩ → QFT → Measure → r8.3 Factoring from r
If r is even and a^{r/2} ≠ -1 (mod N), then gcd(a^{r/2}±1, N) yields a non‑trivial factor.
Compute gcd(a^{r/2}±1, N) → factorPut it together
Worked example
Factor N=15 by choosing a=2. Find period r=4 (since 2⁴=16 ≡ 1 mod 15). Compute gcd(2^{2}±1,15)=gcd(3,15)=3 and gcd(5,15)=5, yielding the factors 3 and 5.
Key takeaways
• Shor’s algorithm reduces factoring to period finding. • Quantum Fourier transform extracts the period exponentially faster than classical methods. • The algorithm succeeds with high probability after a few repetitions.
Knowledge check / 3 questions