9.3 量子計算帶來的新視角#

概念說明#

前面所有討論都建立在「古典電腦」之上。量子計算提出了根本不同的計算模型：利用疊加（superposition）與糾纏（entanglement），量子電腦可以同時「探索」指數多個狀態，並透過干涉放大正確答案的振幅。這引出兩個自然問題：量子電腦能解決 NP-complete 問題嗎？

答案普遍認為是否定的。量子計算的對應效率類別是 BQP（Bounded-error Quantum Polynomial time），目前所知：P ⊆ BPP ⊆ BQP ⊆ PSPACE。雖然 BQP 與 NP 的關係未定，但Grover 演算法告訴我們量子只能對無結構搜尋提供平方加速：O(√N) 搜尋 N 個可能性，取代 O(N)。套到 3-SAT 的 2ⁿ 種指派上，Grover 只能把 2ⁿ 降到 2^(n/2)——仍是指數，距離多項式遙遠。而且已有多項結果指出，除非複雜度階層崩塌，量子電腦無法一般性地解決 NP-complete 問題。

量子計算真正的殺傷力在有數學結構的問題：

Shor 演算法（1994）：多項式時間做質因數分解與離散對數，直接威脅 RSA 與 ECC 密碼學。質因數分解不是已知 NP-complete，但這個結果證明量子確實能突破某些古典難題。
Grover 演算法（1996）：無結構搜尋的平方加速，可加速任何暴力搜尋、碰撞搜尋。
量子模擬：模擬量子系統本身，這是量子電腦最確定、最實際的應用。

值得強調的觀念修正：「量子電腦同時嘗試所有答案」是常見的誤解。測量只能得到一個結果，威力來自把答案編碼進振幅的干涉結構——Shor 的週期尋找與 Grover 的相位翻轉正是巧妙設計干涉的範例。這也解釋了為什麼「把 SAT 直接丟進疊加態」沒有用。

演算法步驟（Grover 搜尋）#

準備 n 個量子位元的均勻疊加態 |s⟩ = (1/√N)Σ|x⟩，N = 2ⁿ。
反覆執行 Grover 迭代（約 (π/4)√N 次）：
Oracle 步驟：對滿足條件的 x 翻轉相位（|x⟩ → −|x⟩）。
擴散步驟：對均值做反射（2|s⟩⟨s| − I），把正確答案的振幅進一步放大。
測量，以高機率得到目標 x。

Python 程式碼範例#

（古典模擬：示範 Grover 振幅放大效應）

import numpy as np

def grover_simulation(N, targets, iterations=None):
    """以古典向量模擬 Grover 演算法的振幅放大"""
    state = np.full(N, 1.0 / np.sqrt(N))     # 均勻疊加
    oracle = np.ones(N)
    oracle[targets] = -1                     # 相位翻轉
    mean_reflect = 2 * np.outer(state, state) - \
                   np.eye(N)                 # 擴散算子
    iters = iterations if iterations is not None \
            else int(np.pi / 4 * np.sqrt(N))
    probs = []
    for _ in range(iters):
        state = oracle * state               # Oracle
        state = mean_reflect @ state         # 擴散
        probs.append(sum(state[t] ** 2 for t in targets))
    return state, probs

N = 1024                                   # 10 量子位元
target = [777]
state, probs = grover_simulation(N, target)
print(f"迭代 {len(probs)} 次（≈ π/4·√N）")
print(f"目標測得機率: {probs[-1]:.3f}")     # ≈ 1
# 對照：不迭代時機率只有 1/N ≈ 0.001

複雜度分析#

Grover：O(√N) 次 Oracle 呼叫，已證明為最優（量子下界）；套用於 SAT 即 O(2^(n/2))，仍指數。
Shor：多項式（約 O(n³) 邏輯閘），對 n 位整數質因數分解。
BQP 的邊界：BQP 演算法解決 NP-complete 問題 ⟹ NP ⊆ BQP ⟹ 複雜度階層崩塌，因此學界普遍排除此可能。
工程現實：目前量子電腦為 NISQ 世代（含雜訊），Grover 需要的相干深度遠超現有硬體；容錯量子電腦是未來課題。密碼學界已啟動「後量子密碼」遷移（NIST 標準化 CRYSTALS-Kyber 等）。

練習#

修改 grover_simulation，對 N = 256、target = [10, 200]（兩個解）執行，觀察最佳迭代次數變為 π/4·√(N/2)，驗證理論公式。
解釋為什麼把 2ⁿ 個 SAT 指派放入疊加態後直接測量是無用的（得到任一指派的機率都是 1/2ⁿ），干涉在其中扮演什麼角色。
查閱並說明：質因數分解為何不被認為是 NP-complete？若它被證明 NP-complete，會推出什麼驚人結論（提示：NP ∩ coNP）。