Shor's Algorithm Intuition

Shor's Algorithm, formulated by Peter Shor in 1994, is arguably the most famous quantum algorithm. It solves the problem of factoring large integers in polynomial time. Since modern classical cryptography (specifically RSA) relies on the assumption that factoring is hard, Shor's algorithm represents a direct threat to global digital security.

Imagine you are walking around a circular track with numbered stepping stones. If you take steps of a fixed size $a$, you will eventually land back on your starting stone. The number of steps it takes to return to the start is the 'period' $r$. Finding this period classically is slow, you have to keep walking and counting. Shor's algorithm uses quantum superposition to stand on all stepping stones simultaneously. By applying a modular exponentiation function and then using the QFT, the algorithm acts like a prism, splitting the quantum state into its constituent frequencies. The dominant frequency revealed by the QFT corresponds directly to the period $r$. Once we have this period, a simple classical calculation reveals the prime factors of the number.

Let $N$ be the composite integer we wish to factor. Shor's algorithm reduces the factoring problem to the problem of order finding (or period finding) using the following mathematical steps:

1. Choose a random integer $a < N$. Compute $\gcd(a, N)$ using Euclid's algorithm. If $\gcd(a, N) > 1$, we have found a factor and are done. 2. Find the period $r$ of the function: $$f(x) = a^x \pmod N$$ The period $r$ is the smallest positive integer such that $a^r \equiv 1 \pmod N$. 3. If $r$ is even, we can write: $$a^r - 1 \equiv 0 \pmod N \implies (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod N$$ This implies that $N$ shares a common factor with either $a^{r/2} - 1$ or $a^{r/2} + 1$. 4. Compute the factors using the classical greatest common divisor: $$\text{Factor} = \gcd(a^{r/2} \pm 1, N)$$

The Quantum Subroutine (Period Finding): To find $r$, we use a 2-register quantum circuit:

• Register 1 (control): $t$ qubits, initialized to $|0\rangle^{\otimes t}$.
• Register 2 (target): $n$ qubits, initialized to $|0\rangle^{\otimes n}|1\rangle$.

1. Superposition: Apply $H^{\otimes t}$ to Register 1. 2. Modular Exponentiation: Apply the unitary operator $U_{a, N}$ which maps $|x\rangle|y\rangle \to |x\rangle|y \cdot a^x \pmod N\rangle$: $$|\psi_1\rangle = \frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t-1} |x\rangle |a^x \pmod N\rangle$$ 3. Measurement of Register 2: Measuring Register 2 collapses Register 1 into a periodic state with period $r$. 4. QFT: Apply the QFT to Register 1 to extract the period $r$ from the phase frequency. 5. Continued Fractions: Use the classical continued fractions algorithm to reconstruct the exact integer $r$ from the measured phase.