第8章 Shor 質因數分解演算法#

章前言#

1994 年 Peter Shor 發表的質因數分解演算法是量子計算的「殺手級應用」：古典已知最快的分解演算法（一般數域篩法）需要次指數時間 \(e^{O((\log N)^{1/3}(\log\log N)^{2/3})}\) ，而 Shor 演算法只需 \(O((\log N)^3)\) 的多項式時間。這直接威脅 RSA——全世界的公開金鑰密碼系統幾乎都建立在「大整數難分解」的假設上。

本章把 Shor 演算法拆成三層：8.1 節做古典約化——分解 \(N\) 可以化約成「找 \(a^x \bmod N\) 的週期 \(r\) 」，這一步完全是古典數論（含隨機化與連續分數的準備）；8.2 節設計量子電路用 QFT 找週期（第 7 章的相位估計直接上場）；8.3 節用連分數從測量結果提取 \(r\) ，最後由 \(\gcd\) 得到質因數，並完整實作一個「量子週期尋找＋古典後處理」的 Shor 模擬器。

讀完本章你會發現：Shor 演算法的量子部分只佔整體流程的一小段，但它把指數難的週期尋找壓成多項式——這正是「量子子程序嫁接古典框架」的典範。

學習目標

1. 掌握從因數分解到週期尋找的數論約化鏈條。
2. 實作量子週期尋找電路並理解其資源需求。
3. 用連分數展開從測量樣本提取週期，完成完整的 Shor 模擬。