The idea behind Shor’s algorithm

Grover’s ending pointed the way: for exponential speedup, find a problem with structure. In 1994 Peter Shor found that problem — factoring large integers. Its structure is a hidden periodicity, and “finding periods with interference” has been quantum mechanics’ signature trade since the double-slit experiment. This section does not dive into number-theoretic proofs, but it works the full logical chain and the quantum part all the way through.

The problem at the door: multiplication is easy, division is deadly

$3\times5=15$ — mental arithmetic. The reverse, “15 = ? × ?”, is not hard either. But make the number 617 digits long (2048 bits): multiplying two thousand-digit primes takes a computer milliseconds; recovering the two factors from the product, using the fastest known classical algorithm (the number field sieve), takes time on the order of

$$\exp\!\left[c\,(\ln N)^{1/3}(\ln\ln N)^{2/3}\right],\qquad c\approx1.9\tag{9.9.1}$$

— sub-exponential: far worse than polynomial. For a 2048-bit $N$, all the computing power on Earth combined would need millennia. The security of RSA public-key cryptography is staked on exactly this one-way street: the public key displays $N$ in plain sight, and whoever can factor it can read every ciphertext.

First leg: factoring ⇒ period finding (classical number theory, results only)

Shor’s first move is to rewrite the problem. Pick any $a$ coprime to $N$ and look at the modular exponential

$$f(x)=a^x \bmod N\tag{9.9.2}$$

It is necessarily periodic: $f(x+r)=f(x)$, and the smallest positive period $r$ is called the order of $a$. Number theory provides a bridge (stated without proof):

If $r$ is even and $a^{r/2}\not\equiv-1\pmod N$, then $\gcd(a^{r/2}-1,\,N)$ and $\gcd(a^{r/2}+1,\,N)$ yield nontrivial factors of $N$.

The intuition in one line: $a^r\equiv1$ means $(a^{r/2}-1)(a^{r/2}+1)\equiv0\pmod N$ — $N$ divides the product yet (under the stated conditions) divides neither factor, so $N$‘s prime factors have been split between the two sides, and $\gcd$ (the Euclidean algorithm — blazingly fast) collects one from each. For a random $a$ the conditions hold with probability at least $1/2$; if they fail, pick another $a$ and try again.

Hand-compute $N=15$ with $a=7$:

$$7^1=7,\quad 7^2=49\equiv4,\quad 7^3\equiv28\equiv13,\quad 7^4\equiv91\equiv1\pmod{15}\tag{9.9.3}$$

The period is $r=4$ — even, and $7^2\equiv4\not\equiv-1$. Therefore

$$\gcd(7^2-1,15)=\gcd(48,15)=3,\qquad \gcd(7^2+1,15)=\gcd(50,15)=5\tag{9.9.4}$$

$15=3\times5$ — success. The only hard step left in the entire algorithm is finding the period $r$. Classically, period finding is no cheaper than factoring outright (you would have to grind $f$ through trillions of steps before seeing a single cycle); this is precisely the step quantum mechanics takes over.

Second leg: loading the period into a superposition

Open with the DJ recipe: hit the first register ($t$ qubits, $Q=2^t\gg r^2$) with a row of $H$‘s, compute the modular exponential for every $x$ in parallel, and write it into the second register:

$$\frac{1}{\sqrt Q}\sum_{x=0}^{Q-1}\ket{x}\ket{a^x\bmod N}\tag{9.9.5}$$

Now measure the second register (you don’t actually have to — it just makes the story easier to tell), obtaining some value $f_0$. The first register thereupon collapses to the equal-weight superposition of all the $x$ that produce that value — and these $x$ form exactly an arithmetic progression $x_0,\ x_0+r,\ x_0+2r,\dots$:

$$\ket{\Psi}=\frac{1}{\sqrt m}\sum_{j=0}^{m-1}\ket{x_0+jr},\qquad m\approx Q/r\tag{9.9.6}$$

The period is now etched into the state, but a direct measurement would just spit out one random $x_0+jr$ — the random starting point $x_0$ scrambles the period information (each rerun gives a different $x_0$). The old problem: the information went in but won’t come out. The old answer: interference. This time the interference machine is the quantum Fourier transform.

Third leg: the QFT turns the period into peaks

The quantum Fourier transform (QFT) is the deluxe version of DJ’s row of $H$‘s — upgrading “bitwise phases” to “continuous phases”:

$$\mathrm{QFT}\ket{x}=\frac{1}{\sqrt Q}\sum_{y=0}^{Q-1} \ee^{2\pi\ii xy/Q}\ket{y}\tag{9.9.7}$$

(The phases of $H^{\otimes n}$ are only $\pm1$; the QFT’s phases take $Q$ ticks around the unit circle. It can be built from $O(t^2)$ gates — $H$‘s plus controlled phase rotations; we skip the circuit here.)

Measuring after the QFT: why the peaks land on integer multiples of Q/radvanced~9 minexpand

Step 1: apply the QFT to the periodic state. Substitute $\ket{\Psi}$ into the definition:

$$\mathrm{QFT}\ket{\Psi} =\frac{1}{\sqrt{mQ}}\sum_{y=0}^{Q-1} \left[\sum_{j=0}^{m-1}\ee^{2\pi\ii(x_0+jr)y/Q}\right]\ket{y}\tag{9.9.8}$$

Step 2: factor out the random start. Pull out the factor $\ee^{2\pi\ii x_0y/Q}$ — it contributes only a phase and vanishes in the modulus squared: the pesky $x_0$ exits the stage right here. The probability of measuring $y$ is

$$P(y)=\frac{1}{mQ}\left|\sum_{j=0}^{m-1}\ee^{2\pi\ii jry/Q}\right|^2\tag{9.9.9}$$

Step 3: see when the geometric series adds up. The bracket is a geometric series with ratio $\ee^{2\pi\ii ry/Q}$.

• If $ry/Q$ is exactly an integer, i.e. $y=k\,Q/r$: every term equals 1, the sum is $m$, and $P(y)=m/Q\approx1/r$ — a sharp peak;
• otherwise the phases march around the unit circle, closing on themselves and nearly cancelling: $P(y)\approx0$.

$r$ sharp peaks stand evenly spaced at $y=0,\ \tfrac{Q}{r},\ \tfrac{2Q}{r},\dots$, carrying total probability about 1. (When $r$ does not divide $Q$ the peaks acquire a slight width and sit at the nearest integers, but the conclusion stands — this is exactly why we demanded $Q\gg r^2$: peak width much smaller than peak spacing.)

Step 4: recover $r$ from the readout. Measuring some $y\approx kQ/r$ means

$$\frac{y}{Q}\approx\frac{k}{r}\tag{9.9.10}$$

The left side is the known readout; the right side is the fraction we want. A continued-fraction expansion finds the best rational approximation with denominator at most $N$, giving a candidate for $r$ (if $k$ and $r$ share a factor you get a divisor of $r$; a rerun or two and a least common multiple fixes that). Feed it back into the first leg’s $\gcd$, and the factorization is done.

Mini worked check ($N=15,a=7,r=4$, with $Q=16$): the peaks should sit at $y=0,4,8,12$. Say we measure $y=12$: $\tfrac{12}{16}=\tfrac34$, the continued fraction gives $k/r=3/4$, so $r=4$. ✓

∎Key formulas

• The reduction chain

  $$N=pq\ \Rightarrow\ r=\mathrm{ord}_N(a)\ \Rightarrow\ \gcd(a^{r/2}\pm1,N)$$

  Factoring → period finding → gcd; only the middle step needs a quantum computer

• QFT

  $$\mathrm{QFT}\ket{x}=\frac{1}{\sqrt Q}\sum_y \ee^{2\pi\ii xy/Q}\ket{y}$$

  The continuous-phase version of H^{⊗n}; realizable with O(t²) gates

• Peak positions

  $$P(y)\ \text{peaks at}\ y\approx k\,Q/r$$

  Periodic superposition through QFT interference; the random start x₀ survives only as a phase, never entering the probability

• Complexity comparison

  $$O(n^3)\ \text{vs}\ \exp[O(n^{1/3}(\log n)^{2/3})]$$

  Polynomial vs sub-exponential: a threat to RSA in principle

?Self-check4 questions

1. 1.

   N = 21, with a = 2. What is the period r of the function 2^x mod 21? (Square repeatedly: 2, 4, 8, 16, …)

   0% relative tolerance

   Submit
2. 2.

   In Shor’s algorithm, which step is the quantum computer actually responsible for?

   • Finding the period r of the modular exponential a^x mod N
   • Computing the greatest common divisor (gcd)
   • The number-theoretic reduction of N to a period problem
   • Trial-dividing by every possible factor, one at a time

   Submit
3. 3.

   If you measured the first register directly before the QFT (while it holds the periodic superposition Σ∣x₀ + jr⟩), what would you get?

   • One random x₀ + jr, with x₀ different on every run, so r cannot be extracted reliably
   • The period r directly
   • Some integer multiple of Q/r
   • A factor of N

   Submit
4. 4.

   Which statements about Shor’s algorithm’s impact on cryptography are correct? (Select all that apply.)

   Select all that apply

   • Public-key systems such as RSA and elliptic curves face a threat in principle
   • "Harvest now, decrypt later" means the migration must finish before large quantum computers exist
   • Symmetric ciphers such as AES are likewise exponentially broken
   • NIST has standardized quantum-resistant algorithms built on lattices and other hard problems

   Submit

What comes next

Shor needs trillions of gate operations to run back-to-back without a slip, and real qubits are delicate creatures: a one-percent gate error counts as excellent, and even left alone they quietly drift. Classical computers correct errors with redundant backups — but quantum states cannot be cloned (Section 9.5), and a measurement collapses them (Section 9.1) — so how do you back up, and how do you even notice an error? The next section is this chapter’s finale: quantum error correction. Its answer is unexpectedly beautiful, and it is a grand reunion of everything this chapter has built — entanglement, measurement, stable correlations.