10.2 量子優勢與應用領域#

概念說明#

什麼是量子優勢？ 嚴格定義：某任務在量子裝置上的（時間/資源）成本，被證明或實測明顯低於任何古典演算法。分三個層次：

計算類別層次：BQP 相對 P/BPP 有指數優勢的問題——目前最乾淨的證據是 Shor（相對已知的古典演算法）與量子系統模擬（Feynman 論證）。
黑箱下界層次：Grover 的 \(\Omega(\sqrt N)\) 下界保證了平方加速無法被任何量子演算法超越。
實驗宣稱層次：Google Sycamore（2019，53 位元隨機電路取樣 200 秒 vs 宣稱古典 1 萬年——後被古典演算法改進到數分鐘，是活躍的攻防）、中科大九章（光量子取樣）。這些是「里程碑」而非「實用優勢」，且古典模擬技術每年都在進步。

最有希望的應用領域：

量子化學與材料：模擬分子電子結構（FeMoco 固氮酶、高溫超導機制、電池電解質）。這是「天生的」量子問題——哈密頓量本身就是量子的，預期是第一個真正實用的領域（估計需容錯機器 + 數十萬邏輯閘）。
密碼學：Shor 威脅 RSA/ECC；Grover 威脅對稱密碼（安全等級減半）。因應：後量子密碼（PQC，NIST 已於 2024 標準化 ML-KEM/ML-DSA/SLH-DSA）與「先偷存、後解密」的 harvest-now-decrypt-later 風險使遷移刻不容緩。
最佳化：QAOA 等變分方法，實用性尚未證明。
機器學習：量子核方法、量子神經網路——理論上有「資料載入瓶頸」（把古典資料灌進量子態本身可能是 \(O(N)\) ），優勢條件尚不明確。
取樣與統計：量子增強蒙地卡羅（振幅放大的 \(O(1/\sqrt p)\) ）。

務實的時間線（業界共識估計）：NISQ 探索期（現在）→ 早期容錯演示（~2027-2030）→ 有實用價值的量子模擬（~2030s）→ 密碼相關規模的 Shor（更遠，但 PQC 遷移現在就要開始）。

Python 範例：比較演算法時間標度#

import numpy as np

# 以「每秒 10^12 次基本運算」估計各方法的執行時間（秒）
OPS = 1e12
n_bits = np.arange(16, 64, 4)     # 分解 N 的位元數

def seconds(n, unit_cost):        # unit_cost: 每「位元規模」的運算次數係數
    return unit_cost(n) / OPS

shor  = seconds(n_bits, lambda n: 100 * n**3)          # O(n^3)（粗估）
gnfs  = seconds(n_bits, lambda n: np.exp(1.9 * n**(1/3) * np.log(n)**(2/3)))
print(" 分解 N 的位元數   數域篩法(年)    Shor(秒)")
for n, g, s in zip(n_bits, gnfs, shor):
    print(f"  n={n:>3}          {g/3.15e7:>10.2e}    {s:>10.2e}")
# 2048 位元時，古典估計遠超宇宙年齡；Shor 約數千秒（未計糾錯開銷）

# Grover 對稱金鑰搜尋：安全等級減半
print("\n 對稱金鑰長度 k 位元的暴力搜尋（量子 √N）：")
for k in [64, 128, 192, 256]:
    print(f"  AES-{k}: 古典 ~2^{k-1} 次；Grover ~2^{k//2} 次"
          f" -> 等效安全 {k//2} 位元")
print("  結論：128 位元金鑰僅剩 64 位元安全，建議遷移到 256 位元")

複雜度分析#

任務	最佳古典	最佳量子	加速
大數分解	次指數	\(O(n^3)\)	超多項式
無序搜尋	\(O(N)\)	\(O(\sqrt N)\)	平方
線性方程組（HHL 條件下）	\(O(N)\)	\(O(\log N)\) （需稀疏+良態+樣本輸出）	指數（條件性）
量子系統模擬	\(e^{O(n)}\)	\(O(\text{poly}(n))\)	指數
3-SAT	\(O(2^n)\)	\(O(2^{n/2})\)	平方

練習#

解釋為什麼「Google 2019 年的量子優勢宣稱」後來被古典演算法追上，這對「實驗驗證優勢」的方法論有什麼啟示？
計算：若 Grover 用 \(10^9\) 閘/秒的機器攻擊 AES-128，需要多少年？AES-256 呢？
（觀念）「harvest-now-decrypt-later」攻擊為什麼使 PQC 遷移不能等量子電腦成熟？列出你認為組織應立即行動的三個理由。