12.10 Shor’s factoring algorithm

Source: Ideas from Computational Physics (Landau, Páez, Bordeianu), §12.10. Original wording — no Amod15 / Qiskit dump. Continues 12.9b. Labs: 12.10b.

RSA-style cryptology leans on the hardness of factoring large integers. Shor’s algorithm finds nontrivial factors of $N$ in (believed) polynomial time on a fault-tolerant quantum computer by reducing factoring to period finding.

Classical outline

1. Pick random $1<r<N$.
2. $K=\gcd(r,N)$; if $K\neq 1$, $K$ is a factor — done.
3. Find the smallest period $T$ of $f(x)=r^x\bmod N$.
4. If $T$ is odd or $r^{T/2}\equiv-1\pmod N$, retry with a new $r$.
5. Else $\gcd(r^{T/2}\pm 1,\,N)$ yields nontrivial factors.

Example toy: $N=15$. A successful run might draw $r=8$, read phase $0.25$ ⇒ $T=4$, then recover factors 3 and 5.

Modular multiplication unitary

A unitary $U$ (for $r$ coprime to $N$) multiplies the computational register by $r$ mod $N$. Eigenstates $|u_S\rangle$ carry eigenvalues $e^{2\pi i S/T}$; estimating that phase reveals $S/T$. Pick $U|y\rangle$ and the $T=1/\phi$ reading among lookalikes in the guided card below.

Phase estimation

For unitary $U|u\rangle=e^{2\pi i\phi}|u\rangle$, a $t$-qubit control register plus Hadamards and controlled-$U^{2^j}$ kicks phases onto the controls. An inverse QFT then reads an integer $s\approx 2^t\phi$, so $\phi\approx s/2^t$.

Period finding → factors

Prepare the target register in $|1\rangle=\frac1{\sqrt T}\sum_S|u_S\rangle$. Phase estimation samples $\phi=S/T$; continued fractions recover denominator $T$. Then apply the gcd steps above.

Local Qiskit sketches combine qpe, a modular-multiply block (e.g. for $N=15$), and classical post-processing — APIs change; keep the math, update imports from current docs. Graded labs lock $\gcd$, periods, and the $N=15$ factors without calling IBM.

Lab: wire phase-est skeleton

Takeaway

Step	Tool
Random $r$, gcd	classical
Period of $r^x\bmod N$	QPE + modular $U$
$T\to$ factors	$\gcd(r^{T/2}\pm1,N)$
QFT link	inverse QFT inside QPE

Quiz

Shor

1 / 3

Shor reduces factoring mainly to…

Pick an answer to see if you are right.

Next: 12.10b Shor labs.