第 10 章　彼得·秀爾與格羅弗：量子演算法對古典計算複雜度的降維打擊#

10.2 格羅弗演算法：未排序資料庫中實現平方根加速搜尋的量子魔術#

10.2.1 1996 年的平方根奇蹟#

Lov Grover（同在 Bell Labs）1996 年提出無序搜索的量子演算法：\(N\) 個無結構項目中找唯一標記項，古典需 \(O(N)\) 次，Grover 只需

次。證明其最優性（Bennett–Bernstein–Brassard–Vazirani 的黑盒下界）顯示：這是無結構搜索的量子極限。

10.2.2 幾何圖像：振幅旋轉#

Grover 迭代是兩次反射的乘積：先以「神諭（oracle）」翻轉目標態相位，再繞平均振幅翻轉（diffusion）——每輪把目標態振幅向 1 旋轉固定角度，約 \(\frac{\pi}{4}\sqrt{N}\) 輪後測量即以高機率得解。它是 BQP 類中「幅度放大（amplitude amplification）」的通用模板，可加速碰撞搜索、滿足性問題等。

10.2.3 對稱密碼的影響：減半的位元數#

• AES-128 在 Grover 下有效安全位數約減半（需 \(2^{64}\) 次 Grover 迭代，但每次迭代本身需大量連貫門操作）；
• 因此 NIST 與 NSA（CNSA 2.0 路線）建議過渡到 AES-256／SHA-384——對稱密碼只需「加長」，公鑰密碼則需「整族替換」；
• 這一差異塑造了 10.3 的 PQC 藍圖：真正被 Shor 摧毀的是 RSA/ECC，對稱與哈希只需對沖。

10.2.4 前因後果#

• 前因：10.1 引發的量子算法熱＋BBBV 黑盒下界＋量子門模型成熟。
• 事件：1996 Grover 論文（STOC 1996）。
• 後果：量子算法譜系成形（HHL 2009 線性系統、VQE/QAOA 變分路線）；「後量子」從學術議題變成政府標準工程（下一節）。

下一節：10.3 後量子密碼學