Project 5: Shor’s Algorithm (The RSA Breaker)

Build a simplified Shor’s algorithm demo for small integers.

Project Overview

Attribute Value
Difficulty Level 3: Advanced
Time Estimate 2-3 weeks
Main Language Python
Alternative Languages Q#, Java
Knowledge Area Period finding
Tools Qiskit or Cirq
Main Book “Quantum Computation and Quantum Information” by Nielsen & Chuang

What you’ll build: A Shor demo that factors small composite numbers using quantum period finding and classical post-processing.

Why it teaches quantum: Shor is the flagship algorithm that shows exponential speedup for factoring.

Core challenges you’ll face:

  • Implementing modular exponentiation circuits
  • Performing QFT-based period finding
  • Translating period into factors

Real World Outcome

You will factor small numbers like 15 or 21 using the algorithm’s workflow.

Example Output:

$ python shor_demo.py --n 15
Found period r=4
Factors: 3 and 5

Verification steps:

  • Confirm factors multiply to n
  • Repeat with multiple n values

The Core Question You’re Answering

“How does period finding lead to factoring?”

This is the key insight behind Shor’s algorithm.

Concepts You Must Understand First

Stop and research these before coding:

  1. Modular arithmetic
    • Why does a^r mod n reveal factors?
    • Book Reference: Nielsen & Chuang, Ch. 5
  2. Quantum Fourier transform
    • How does QFT reveal periodicity?
    • Book Reference: Nielsen & Chuang, Ch. 5
  3. Classical post-processing
    • How do you use the period to compute gcds?
    • Book Reference: “Introduction to the Theory of Numbers” by Hardy & Wright, Ch. 3

Questions to Guide Your Design

  1. Circuit simplification
    • Which small n will you target to keep circuits feasible?
    • How will you validate the modular exponentiation block?
  2. Period extraction
    • How will you interpret measurement results to estimate r?
    • Will you use continued fractions?

Thinking Exercise

Period Example

For n=15 and a=2, compute a^x mod 15 for x=1..8. Find the period.

Questions while working:

  • Why does the period matter for factoring?
  • What happens if the period is odd?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What problem does Shor’s algorithm solve?”
  2. “Why is period finding central?”
  3. “What does the QFT do?”
  4. “Why is Shor hard to run on real hardware today?”
  5. “How do you get factors from the period?”

Hints in Layers

Hint 1: Starting Point Start with n=15 and a=2.

Hint 2: Next Level Use a classical simulator for the quantum part.

Hint 3: Technical Details Implement continued fractions to extract the period.

Hint 4: Tools/Debugging Validate modular exponentiation with classical math first.

Books That Will Help

Topic Book Chapter
Shor algorithm Nielsen & Chuang Ch. 5
QFT Nielsen & Chuang Ch. 5
Number theory “Introduction to the Theory of Numbers” by Hardy & Wright Ch. 3

Implementation Hints

  • Keep circuits minimal to avoid simulator blow-up.
  • Verify each subroutine with small inputs.
  • Expect probabilistic outcomes and repeat runs.

Learning Milestones

  1. First milestone: You can implement period finding for small n.
  2. Second milestone: You can recover factors from the period.
  3. Final milestone: You can explain Shor’s algorithm end-to-end.