Shor's algorithm

Shor’s algorithm factors integers by reducing factoring to period finding, then solves period finding with the quantum Fourier transform and classical post-processing.

Why it matters

This is a flagship example of a super-polynomial quantum speedup for a problem believed to be hard classically (factoring).

In practice, the reason people care is cryptography: widely deployed public‑key systems (historically RSA) rely on the fact that multiplying large primes is easy, but factoring the product appears computationally infeasible on classical hardware at useful sizes.

Shor’s algorithm in one sentence

Pick a random number $a < N$ and use a quantum subroutine to find the period $r$ of the function $f(x)=a^x \bmod N$; once you have $r$, a few classical checks often reveal non‑trivial factors of $N$.

High-level workflow (what happens)

Shor’s factoring algorithm is a hybrid algorithm: classical → quantum → classical.

• 1) Choose $a$: pick a random integer $a$ with $1 < a < N$.
• 2) Check $\gcd(a, N)$ (classical): if $\gcd(a,N)\neq 1$, you already found a factor.
• 3) Period finding (quantum): find the order/period $r$ such that $a^r \equiv 1 \pmod N$.
• 4) Convert $r$ into factors (classical): if $r$ is even and $a^{r/2}\not\equiv -1 \pmod N$, then $\gcd(a^{r/2}\pm 1, N)$ gives non‑trivial factors.
• 5) Retry if needed: some choices of $a$ fail the classical conditions; pick another $a$ and repeat.

The “magic” is step 3: the quantum computer extracts a period efficiently.

The quantum core: QPE + inverse QFT

Most high-level explanations reduce the quantum part to two key subroutines:

• Quantum Phase Estimation (QPE): estimates an eigenphase of a unitary related to modular multiplication/exponentiation. Intuitively, this is where periodic structure gets encoded into phases.
• Inverse QFT (iQFT): converts those phases into a bitstring you can read by measurement (frequency/phase → computational basis).

Two useful prerequisites for understanding what’s going on:

• Phase kickback (how a controlled unitary “writes” a phase onto a control register)
• Quantum Fourier Transform (QFT) (how phases become readable bitstrings)

How many qubits does Shor need?

It depends heavily on the factoring target size, the circuit design, and—most importantly—whether you count logical (error‑corrected) or physical qubits.

• Physical qubits: the noisy hardware qubits available today.
• Logical qubits: error‑corrected qubits built from many physical qubits so computations can be long and reliable.

As a rough modern takeaway: breaking RSA‑2048 would require thousands to tens of thousands of logical qubits, translating into millions to tens of millions of physical qubits under many realistic error‑correction assumptions.

Can you run Shor today?

For meaningful cryptographic sizes: no.

Small “demo” factorizations exist (very small $N$), but scaling up is blocked by:

• Noise / error rates: deep circuits accumulate errors quickly.
• Coherence limits: long computations exceed how long qubits stay stable.
• Error correction overhead: fault tolerance requires many extra qubits and gates.

Where to go next

Return to the tutorial index and reinforce the basics with exercises, or read external references on the Resources page.