第 10 章 彼得·秀爾與格羅弗：量子演算法對古典計算複雜度的降維打擊#
本章導言#
1994 年，一位 AT&T 貝爾實驗室的數學家在量子計算會議上宣布了一個結果，密碼學界為之坐立不安。本章三節：10.1 Shor；10.2 Grover；10.3 後量子密碼學的賽跑。
10.1 秀爾演算法：1994 年量子質因數分解多項式時間突破，對傳統 RSA 密碼學的終極威脅#
10.1.1 貝爾實驗室的那場會議#
1994 年 4 月，Peter Shor（AT&T Bell Labs）在 Santa Fe 的量子計算會議（及隨後 IEEE FOCS 1994 論文）宣布：量子計算機可在多項式時間內分解大整數、解離散對數。會場聽眾（含許多密碼學家）意識到：RSA 與 Diffie–Hellman 的數學地基可能在量子時代塌陷。
10.1.2 演算法的三段式結構#
Shor 的天才在於把數論與量子傅里葉變換（QFT）縫合：
- 經典約化：分解 \(n\) 化歸為求隨機 \(a\) 的階 \(r\)（\(a^r \equiv 1 \bmod n\)）；
- 量子部分：以疊加態同時計算 \(a^x \bmod n\)，再以 QFT 提取週期 \(r\) 的頻率峰（這是唯一「量子加速」的段落）；
- 經典後處理：連分數展開、輾轉相除（1.1 的兩千年老演算法！）恢復 \(r\)，進而 \(\gcd(a^{r/2}\pm1,\ n)\) 得因數。
複雜度：\(O((\log n)^3)\) 級——對比已知最好的古典算法（數域篩法，亞指數）是指數級的差距。歷史的迴響：歐幾里得的程序在量子算法的收尾處再次登場。
10.1.3 從理論到硬體的距離#
現實門檻：分解 RSA-2048 估計需數百萬物理量子位元（糾錯開銷巨大）。里程碑：2019 Google Sycamore 53 量子位元「量子霸權」實驗（隨機線路採樣）；2023–24 IBM Heron、Google Willow（2024，糾錯距離提升）推進邏輯量子位元工程。NIST 的立場：2016 年即啟動後量子遷移（10.3）——密碼學家的態度是「先換鎖，等賊來不如先換」。
10.1.4 前因後果#
- 前因：Feynman 1981–82 的量子模擬倡議＋Deutsch 1985 量子圖靈機＋QFT 理論。
- 事件：1994 Shor 論文。
- 後果：量子計算獲得「殺手級應用」敘事與各國資金（中國、美國國家量子倡議）；10.3 的 PQC 賽跑由此開始。
下一節：10.2 Grover