量子加速（quantum speed-up）發生在某個問題能被量子電腦比古典電腦更快解決時。

例如要在一份無序清單的 n 個項目中搜尋某一項，古典電腦平均需要 n/2 次運算（平均搜尋到一半就會找到），而沒有任何古典演算法能做得比 n/2 更好。

然而存在一個量子演算法，只需要約 √n 次運算——比 n/2 小上數個數量級。

例如 n = 1,000,000 時，n/2 是 500,000，而 √n 只有 1000。

我們用時間複雜度（以 O() 記法表示）來量化量子與古典演算法的差異。上例中量子演算法是 O(√n)，古典演算法不可能快於 O(n)。由於差異來自平方指數，我們稱之為平方加速（quadratic speed-up）。

指數加速與 Simon 問題#

指數加速是量子計算的聖杯。

它發生在「古典電腦上需要指數時間（如 O(2^n)）的任務，在量子電腦上能以多項式複雜度（O(n^k)）完成」時。

這種指數加速能把一件實際上不可能的任務變成可能的任務。（回想第 9 章：密碼學家與複雜度理論家把指數時間與「不可能」連結，把多項式時間與「實用」連結。）

指數加速的代表作是 Simon 問題：

一個函式 f() 把 n 位元字串轉成 n 位元字串，使得 f() 的輸出看起來隨機，但存在一個值 m，使得任何滿足 f(x) = f(y) 的 x、y 都有 y = x ⊕ m。問題就是找出 m。

量子電路的做法：把 2n 個 qubit 初始化為 |0⟩，對前 n 個 qubit 套用 Hadamard 閘（H），再對兩組共 n 個 qubit 套用閘 Qf。給定兩個 n-qubit 群組 x 與 y，Qf 把量子態 |x⟩|y⟩ 變換成 |x⟩|f(x) ⊕ y⟩——也就是可逆地在量子態上計算函式 f()（因為你可以算出 f(x) 並與 f(x) ⊕ y XOR，從新狀態回到舊狀態）。

Simon 問題的指數加速只在非常特定的情況下能用來對付對稱密碼。真正的密碼殺手級應用見下。

Shor 演算法的威脅#

1995 年，AT&T 研究者 Peter Shor 發表了一篇令人震驚的論文〈Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer〉。

這些問題你用古典電腦解不了，但用量子電腦可以。這意味著你能用量子電腦攻破任何依賴這些問題的密碼演算法——包括 RSA、Diffie–Hellman、橢圓曲線密碼學，以及目前所有已部署的公鑰密碼機制。

換句話說：你能把 RSA 或橢圓曲線密碼學的安全性降低到凱撒密碼的水準。

（Shor 大可把論文標題取成「用量子電腦攻破所有公鑰密碼學」。）

知名複雜度理論家 Scott Aaronson 稱 Shor 演算法為「20 世紀後期主要的科學成就之一」。

它解的是更一般的問題#

Shor 演算法實際上解的是比因式分解與離散對數更廣的一類問題：

這看起來與前述的 Simon 問題非常相似，事實上 Simon 演算法正是 Shor 演算法的主要靈感來源。

Shor 演算法能有效率地計算函式週期的能力對密碼學家至關重要，因為這個能力可以被用來攻擊公鑰密碼學。

用 Shor 演算法解因式分解問題#

假設你想分解大數 N = pq。

流程：

1. 挑一個小於 N 的隨機數 a。

2. 請 Shor 演算法找出函式 f(x) = a^x mod N 的週期 ω。

3. 找到週期後，你會有 a^x mod N = a^(x+ω) mod N（也就是 a^x mod N = a^x · a^ω mod N），這意味著：

   a^ω mod N = 1
   ⟹ a^ω − 1 mod N = 0

   換句話說，a^ω − 1 是 N 的倍數：a^ω − 1 = kN（k 未知）。

4. 關鍵觀察：你可以輕易把 a^ω − 1 分解成兩項的乘積：

   a^ω − 1 = (a^(ω/2) − 1)(a^(ω/2) + 1)

5. 計算 (a^(ω/2) − 1) 與 N 的最大公因數（GCD），檢查是否得到 N 的非平凡因數（也就是 1 與 N 以外的值）。

6. 若沒有，就換一個 a 值重跑同樣的演算法。幾次試驗之後你就會得到 N 的一個因數。

這有多容易？

這意味著若我們有量子電腦，就能在合理的時間內（幾天？幾週？也許幾個月？）看到結果，而不是數千年。

用 Shor 演算法解離散對數問題#

DLP 的挑戰是：給定已知的 g 與 p，從 y = g^x mod p 找出 x。在古典電腦上這需要指數時間，但 Shor 演算法憑其有效率的週期尋找技術讓你能輕易找到 x。

考慮函式 f(a, b) = g^a · y^b。假設我們要找這個函式的週期——也就是使得對任何 a、b 都有 f(a + ω, b + ω′) = f(a, b) 的 ω 與 ω′。

推導（q 是 g 的階，是已知參數）：

f(a + ω, b + ω′) = f(a, b)
⟹ g^ω · y^ω′ mod p = 1
把 y 換成 g^x：
⟹ g^(ω + xω′) mod p = 1
⟹ ω + xω′ mod q = 0
⟹ x = −ω / ω′

整體複雜度同樣是 O(n²(log n)(log log n))（n 為 p 的位元長度）。

這個演算法可以推廣到任何交換群中的離散對數，不只是質數模下的整數群。

Grover 演算法#

繼 Shor 演算法對因式分解的指數加速之後，另一個重要的量子加速形式是：在 n 個項目中搜尋，所需時間正比於 n 的平方根，而任何古典演算法都需要正比於 n 的時間。

這個平方加速要歸功於 Grover 演算法（1996 年發現，在 Shor 演算法之後）。

把 Grover 演算法想成：在 n 個可能值中找出滿足 f(x) = 1 的 x（其他多數值的 f(x) = 0）。

若有 m 個 x 值滿足 f(x) = 1：

演算法	時間
Grover（量子）	O(√(n/m))
最佳古典演算法	O(n/m)

對對稱密碼的衝擊#

f() 可以是任何函式。例如它可以是：「對某已知明文 P 與密文 C，f(x) = 1 若且唯若 x 等於滿足 E(K, P) = C 的未知秘密金鑰 K」。

實務上這意味著：若你用量子電腦尋找一把 128 位元的 AES 金鑰，你會在正比於 2^64 的時間內找到它，而非古典電腦所需的 2^128。

（你會需要夠大的明文以確保金鑰的唯一性——若明文與密文只有 32 位元，會有許多候選金鑰能把該明文映射到該密文。）

Grover 演算法屆時只會把搜尋金鑰的複雜度降到「僅僅」2^256 / 2 = 2^128 次運算。

對雜湊函式的衝擊#

Grover 演算法也能找出雜湊函式的原像。要找某值 h 的原像，f() 定義為「f(x) = 1 若且唯若 Hash(x) = h，否則 f(x) = 0」。

Grover 因此以 2^(n/2) 量級的運算取得 n 位元雜湊的原像。

與加密一樣，要確保 2^n 的後量子安全性，就使用兩倍大的雜湊值——因為 Grover 演算法要找一個 2n 位元值的原像至少需要 2^n 次運算。

有一個量子演算法能以 O(2^(n/3)) 而非古典生日攻擊的 O(2^(n/2)) 時間找到雜湊函式碰撞。

這似乎暗示量子電腦在找雜湊碰撞上勝過古典電腦——但那個 O(2^(n/3)) 時間的量子演算法也需要 O(2^(n/3)) 的空間（記憶體）才能執行。

給古典演算法同樣 O(2^(n/3)) 的空間，它能跑一個平行碰撞搜尋演算法，碰撞時間只要 O(2^(n/6))——遠快於 O(2^(n/3)) 的量子演算法。

細節見 Daniel J. Bernstein 的〈Cost Analysis of Hash Collisions〉：http://cr.yp.to/papers.html#collisioncost ^↗。