6.3 二次加速的證明與應用#

概念說明#

迭代次數的推導：設解有 \(M\) 個， \(\sin\theta = \sqrt{M/N}\) 。 \(r\) 次迭代後成功機率

選 \(r\) 使 \((2r+1)\theta \approx \pi/2\) ，得

單解時 \(r \approx \frac{\pi}{4}\sqrt N\) ：查詢次數從古典的 \(O(N)\) 降到 \(O(\sqrt N)\) 。

這是可證明的最優：Bennett–Bernstein–Brassard–Vazirani（BBBV, 1997）用多項式法（polynomial method）證明，任何量子黑箱演算法找單一解都需要 \(\Omega(\sqrt N)\) 次查詢。所以 Grover 不是「還能更好」的演算法，而是此問題在黑箱模型下的終點——這在量子演算法理論中極為罕見（我們通常只知道上界）。

實際應用：

1. 結構化搜尋／SAT：把約束檢查當作 \(f\) ，Grover 可加速任何「逐一驗證」型問題，包括 NP 完全問題（但只有平方加速， \(2^{n/2}\) ）。
2. 密碼學：對 \(k\) 位對稱金鑰的暴力搜尋降為 \(O(2^{k/2})\) ——AES-128 的安全等級降到約 64 位元，故建議用 AES-256；對雜湊原像攻擊同理，如 SHA-256 安全性降至 128 位元。這與 Shor 對公開金鑰體系的「多項式時間崩潰」不同：Grover 對稱密碼只是安全等級減半。
3. 量子振幅放大（amplitude amplification）：Grover 的推廣框架，可加速任何成功機率為 \(p\) 的隨機程序至 \(O(1/\sqrt p)\) 。

Python 範例：驗證 \(\pi/4\sqrt N\) 公式與 BBBV 尺度#

import numpy as np

def success_prob(n, M, r):
    theta = np.arcsin(np.sqrt(M/2**n))
    return np.sin((2*r+1)*theta)**2

print(" 單解 P(r) 隨迭代次數變化：")
for r in range(0, 6):
    print(f"  r={r}: P={success_prob(6, 1, r):.4f}   (r*≈π/4√64≈{np.pi/4*8:.1f})")

print("\n 不同 N 的最優迭代次數與加速比：")
for n in [4, 8, 12, 16, 20]:
    N = 2**n
    r_opt = max(1, round(np.pi/4*np.sqrt(N) - 0.5))
    print(f"  N=2^{n:<2}={N:>8}: r≈{r_opt:<5} 古典平均 {N/2:>8.0f} 次 "
          f"加速 {N/2/r_opt:>8.0f}×")

# 多重解：M 個解時 r ∝ sqrt(N/M)
print("\n 多重解（N=2^10）：")
for M in [1, 4, 16, 64]:
    theta = np.arcsin(np.sqrt(M/1024))
    print(f"  M={M:>3}: r≈{np.pi/4/theta - 0.5:.1f}, P(r)={success_prob(10, M, round(np.pi/4/theta-0.5)):.3f}")

複雜度分析#

模擬器成本： \(r\) 次迭代 × \(O(2^n)\) 。注意 Grover 的 \(\sqrt{\cdot}\) 對指數問題仍是「半指數」，NP 完全問題在量子電腦上依舊困難。

練習#

1. 推導 \(P(r)=\sin^2((2r+1)\theta)\) ，並說明為什麼迭代次數超過理論值成功率會下降。
2. （程式）實作 3-SAT 實例的 Grover 搜尋（例如 5 變數、8 子句），統計 1000 次量測找到滿足指派的比例。
3. （觀念）BBBV 下界用了多項式法。查閱資料說明「查詢複雜度下界」與「時間複雜度下界」的差別，為什麼 Grover 的最優性只對黑箱模型成立？