QCQI - Chapter 7: Shor’s Algorithm & Phase Estimation

Learning Objectives¶

• QPE circuit and accuracy.

• Shor: factoring $\to$ order finding $\to$ continued fractions.

• Modular exponentiation resources and IPEA.

QPE in One Slide¶

Control $U^{2^k}$ from $|+\rangle$ qubits $\Rightarrow$ inverse QFT reveals bits of $\phi$.

Eureka! Global eigenphase $\to$ measurable bit string.

From Order to Factors¶

If $r$ even and $a^{r/2}\not\equiv -1 \ (\mathrm{mod}\ N)$ then $\gcd(a^{r/2}\pm1,N)$ are nontrivial.

Eureka! Quantum finds $r$, classical extracts the factors.

Modular Exponentiation (Sketch)¶

Repeated squaring: multiply by constants $c_k=a^{2^k}\bmod N$ controlled on exponent bits.

Ancillas uncompute to keep the map reversible.

Schematic: QPE (concept)¶

Hands-on Notebook¶

Companion notebook (multi-backend): L09_QCQI_Ch07_Shor_Algorithm_and_Phase_Estimation

Set backend in the first cell to cirq, pennylane, braket, pyquil, or qiskit.

Mini-Lab¶

• QPE for $U=\mathrm{diag}(1,e^{2\pi i\phi})$.

• Iterative vs. standard QPE.

• Small-$N$ order-finding and factor recovery.