Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 39 ยท Projects and Practice

Project: A Shor Factoring Simulator

Build a complete factoring program around simulated quantum order finding: classical checks, QFT sampling, continued fractions and statistics over many numbers.

In Shor's algorithm you saw the idea; now you build a full factoring tool around it. The quantum part is simulated exactly (the state after modular exponentiation, followed by a transform), so the program behaves statistically like the real algorithm. Everything else, from trivial checks to continued fractions, is the classical code a real implementation also needs.

The goal: a function factor(N) that returns a non-trivial factor of any composite N up to a few hundred, and reports how many quantum runs it used.

Design

A real Shor implementation has this structure:

flowchart TB
    A["Input N"] --> B{"N even, prime or prime power?"}
    B -->|"yes"| C["Handle classically"]
    B -->|"no"| D["Pick random a, compute gcd"]
    D -->|"gcd > 1"| E["Done: lucky factor"]
    D -->|"gcd = 1"| F["Quantum order finding"]
    F --> G{"r even and a^(r/2) != -1?"}
    G -->|"no"| D
    G -->|"yes"| H["gcd(a^(r/2) +- 1, N) -> factors"]

Classical pre-checks, quantum order finding, classical post-processing.

The classical pre-checks matter: the quantum routine assumes N is odd and not a prime power. Even numbers have the factor 2, and a prime power p^k is found by trying integer k-th roots.

The simulated order-finding routine

The routine follows the textbook steps:

  1. Choose Q = 2^q >= N^2.
  2. The first register is in superposition over x; the second register holds a^x mod N. Measuring the second register picks a random value f0 reached by the sequence, and collapses the first register to an equal superposition of all x with a^x = f0 (a periodic comb of period r).
  3. The QFT of that comb is computed here with an FFT (the same transform up to sign convention); sample y from the resulting probabilities.
  4. Recover r from y/Q using continued fractions.

Because y/Q is near s/r for a random s, and s can share factors with r, the recovered denominator may be a divisor of r. The code therefore tries small multiples of the candidate until a^r = 1.

Python The factoring program

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For each N the product of the returned factors reproduces N. The number of quantum runs is usually 1 or 2, matching theory: for a random a, at least half of the choices lead to an even order with a non-trivial factor.

Statistics: how often does a single run succeed?

A single run can fail in several ways: s shares a factor with r (the order is hidden), the order is odd, or a^(r/2) = -1 (mod N). Measure this over many random choices of a, using the simulated routine.

Python Success rates over many runs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The denominator equals the true order only in a minority of runs (when s shares a factor with r you get a divisor of r), but trying small multiples recovers a valid period far more often, and a good share of runs yields a factor of 77. Retrying a few times drives the failure probability toward zero.

What changes for real hardware

  • Gate count. The simulated "compute a^x mod N into a register" becomes a quantum circuit of modular multipliers, the dominant cost: O(n^2) to O(n^3) gates for n-bit N.
  • Qubit count. Textbook version: 3n qubits or so; optimized versions (Beauregard, Gidney-Ekera) use about 2n + O(1) or a semi-classical QFT with one counting qubit reused, plus ~n for the work register.
  • Errors. Everything must run in an error-corrected fashion; see stabilizer and surface codes.
  • Cheating demos. Published factorings of 15 and 21 often precompile the circuit using knowledge of the answer. Be skeptical of any "factoring record" that does not use a general circuit.

Extensions

  1. Discrete logarithm. Implement the two-register version: find s with g^s = h (mod p), using a 2D transform.
  2. Real gate-level QFT. Replace the FFT with the circuit from the QFT lesson and sample bit strings from it.
  3. Resource counter. Write a function that estimates logical qubits and Toffoli gates for an n-bit modulus and plot the growth.
  4. Noise. Perturb the sampled y with errors and measure how often the continued-fraction step still recovers r.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does factor(N) check for even numbers and prime powers before the quantum step?

    For those inputs the gcd trick can fail or is unnecessary, and they have easy classical solutions.
  2. 2. Why does the code try multiples of the recovered denominator?

    y/Q is near s/r; if gcd(s, r) > 1 the reduced fraction has a smaller denominator.
  3. 3. What is Q chosen to satisfy?

    Q >= N^2 guarantees the continued-fraction expansion identifies s/r uniquely.
  4. 4. Which part of the simulation is the real quantum computing cost on hardware?

    Modular multiplication circuits dominate the gate count.

Summary

  • A complete Shor program is mostly classical: pre-checks, random a, gcd, continued fractions, and the final gcd step.
  • The simulated quantum step samples from the QFT of a periodic comb, giving y/Q near s/r.
  • Each run succeeds with decent probability; retries make failure negligible.
  • On real hardware, modular exponentiation and error correction dominate the cost.

Next: Project: A Quantum Walk Simulator