QCQI – Chapter 7 Detailed Summary: Shor’s Algorithm & Phase Estimation

Learning Objectives¶

• Understand Quantum Phase Estimation (QPE): circuit, accuracy, and semiclassical variants.

• Reduce integer factoring to order finding and perform recovery via continued fractions.

• Implement modular exponentiation $x\mapsto a^x \bmod N$ with repeated squaring; reason about resources.

• Analyze success probabilities and error sources (aQFT, imperfect order conditions).

Quantum Phase Estimation (QPE)¶

Given unitary $U$ with eigenpair $U|u\rangle=e^{2\pi i \phi}|u\rangle$ and $\phi\in[0,1)$, QPE estimates the binary expansion $\phi=0.\phi_1\phi_2\dots\phi_t$. The $t$-qubit phase register is prepared in $|+\rangle^{\otimes t}$ and controls powers $U^{2^k}$:

Applying $\mathrm{QFT}^{-1}$ on the phase register yields (with high prob.) $\lfloor 2^t\phi \rceil$.

Accuracy: if $\phi$ has an exact $t$-bit expansion, success is 1. In general, $\Pr[\text{nearest integer}] \ge 4/\pi^2\approx 0.405$.

Eureka! Control on $U^{2^k}$ turns global eigenphases into computational bits via $\mathrm{QFT}^{-1}$.

Iterative (Semiclassical) Phase Estimation (IPEA)¶

Measure least significant bits first, feeding forward classically controlled $Z$-rotations to cancel known phases. Requires one control qubit reused $t$ times plus the eigenstate register.

Eureka! Measurements + classical feed-forward can replace $\mathrm{QFT}^{-1}$'s entangling gates.

Order Finding & Shor’s Reduction¶

For $N$ odd composite and $a$ coprime to $N$, the order $r$ of $a$ modulo $N$ is the least $r>0$ such that $a^r\equiv 1\ (\mathrm{mod}\ N)$. Define $U:|x\rangle\mapsto|ax \bmod N\rangle$; then $U$ has eigenphases $\phi=s/r$. QPE on $U$ returns $y\approx s2^t/r$.

Recover $r$ from $y/2^t$ via continued fractions; if $\left|\frac{y}{2^t}-\frac{s}{r}\right|<\frac{1}{2r^2}$ the convergent is unique. With $t\ge 2n$ ($N<2^n$), this holds with good probability.

From order to factors. If $r$ is even and $a^{r/2}\not\equiv -1\ (\mathrm{mod}\ N)$, then $\gcd(a^{r/2}\pm 1, N)$ are nontrivial factors.

Eureka! Number theory + QPE: the quantum part finds $r$; classical post-processing extracts factors.

Modular Exponentiation Circuit (Sketch)¶

Implement $x\mapsto a^x \bmod N$ by repeated squaring:

For each bit $x_k$, conditionally multiply the work register by the precomputed constant $c_k=a^{2^k}\bmod N$ using reversible modular multiplication (adders + controlled adds, with uncomputation). Controlled-$U^{2^\ell}$ are realized by shifting which constants are applied.

Eureka! Exponentiation reduces to a sequence of controlled modular multiplies by fixed constants $c_k$.

Resource Sketch (Factoring $N$ with $n=\lceil\log_2 N\rceil$ bits)¶

• Qubits: phase register $t\approx 2n+O(1)$; work register $n$; ancillas $\tilde O(n)$ depending on adder design.

• Gates: modular exponentiation dominates: $\tilde O(n^3)$ Toffoli/CNOT-level with textbook adders (improvable with advanced arithmetic).

Success Considerations¶

Random $a\in\{2,\dots,N-2\}$ coprime to $N$ yields even $r$ and $a^{r/2}\not\equiv-1$ with probability $\ge 1/2$. Repeat with fresh $a$ if needed. aQFT and finite $t$ only slightly reduce success; classical continued fractions are robust.

Worked Nuggets¶

Small-$N$ example: For $N=15$, $a=2$ has order $r=4$; $2^{r/2}=4\not\equiv-1$; $\gcd(4\pm1,15)=\{3,5\}$.

Continued fractions criterion: If $\left|\phi-\frac{s}{r}\right|<\frac{1}{2r^2}$ then $\frac{s}{r}$ is a convergent of $\phi$’s CF expansion.

IPEA angle update: when estimating bit $k$ (LSB first), subtract the phase implied by bits already measured.

Pseudo-code Aids¶

Pseudocode — Quantum Phase Estimation (standard)

Input: unitary $U$, eigenstate $|u\rangle$, $t$ phase qubits Prepare $|+\rangle^{\otimes t}|u\rangle$ for $k=0$ to $t-1$: apply controlled-$U^{2^k}$ with control qubit $k$ apply $\mathrm{QFT}^{-1}$ to the $t$ controls; measure to get $\tilde y$ return $\tilde \phi = \tilde y / 2^t$

Pseudocode — Iterative Phase Estimation (IPEA)

Input: $U,|u\rangle$, $t$ bits for $j=t$ down to 1: prepare control in $|+\rangle$ apply controlled-$U^{2^{j-1}}$ apply $R_z$ to cancel phases from previously obtained bits apply $H$; measure to obtain bit $b_j$

Pseudocode — Shor (Factoring $N$)

Repeat: pick random $a\in\{2,\dots,N-2\}$; if $\gcd(a,N)\neq 1$, return factor run order-finding via QPE on $U:|x\rangle\mapsto|ax\bmod N\rangle$ to get $r$ if $r$ odd or $a^{r/2}\equiv -1 \ (\mathrm{mod}\ N)$: continue else return $\gcd(a^{r/2}\pm1,N)$

Schematics¶

QPE Circuit (concept)¶

Order-Finding Post-Processing¶

Hands-on Notebook (Multi-Backend)¶

Run: L09_QCQI_Ch07_Shor_Algorithm_and_Phase_Estimation

In the first cell set backend to one of: cirq, pennylane, braket, pyquil, or qiskit.

Mini-Lab Ideas¶

1. QPE on $U=\mathrm{diag}(1,e^{2\pi i\phi})$ and compare to true $\phi$.

2. IPEA vs standard QPE: shots vs. accuracy trade-off.

3. Order-finding for $N=15,21$ with small $a$; recover $r$ from CF and verify $\gcd(a^{r/2}\pm1,N)$.