1.1 從古典到量子#

為什麼需要新的計算模型？#

二十世紀後半，電腦科學建立在圖靈機與位元（bit）的概念之上：所有資訊都以 0 或 1 表示，任何計算都可以拆解成一連串的邏輯閘。這套模型極為成功，從試算表到深度學習都離不開它。然而到了 1980 年代，物理學家開始追問一個根本問題：計算的物理載體本身若遵守量子力學，計算模型會變成什麼樣子？

這個問題最早由 Paul Benioff 與 Richard Feynman 提出。Feynman 在 1982 年的著名演講中指出：模擬量子系統（例如分子的電子結構）對古典電腦而言成本會隨系統大小指數成長，因為描述 \(n\) 個相互作用的量子粒子需要指數多的古典參數；但若用一台「本身就是量子的機器」來模擬，成本可能只隨 \(n\) 線性成長。這是量子計算的第一個動機：量子系統最好的模擬器是另一個量子系統。

第二個動機來自密碼學。1994 年 Peter Shor 證明量子電腦可以在多項式時間內分解大整數，直接威脅 RSA 等廣泛使用的公開金鑰密碼系統——古典演算法中已知的最好方法（一般數域篩法）需要次指數時間，而 Shor 演算法只需 \(O((\log N)^3)\) 級的多項式時間。1996 年 Lov Grover 再證明量子電腦可以在 \(O(\sqrt{N})\) 次查詢中搜尋無序資料庫，比古典的 \(O(N)\) 有一個平方加速。

古典計算模型的極限#

從複雜度理論的角度看，古典計算機的「計算能力」由計算類別 P、BPP 等刻劃。量子計算對應的計算類別稱為 BQP（bounded-error quantum polynomial time）。我們知道

\[ \text{P} \subseteq \text{BQP} \subseteq \text{PSPACE} \]

但 BQP 與 NP 的關係至今未明。特別要注意的是：量子電腦並不能「什麼都算得快」。對大部分問題（排序、矩陣乘法、旅行推銷員等等），已知的量子演算法只有多項式等級的加速，甚至沒有加速。真正有指數级優勢的已知例子（Shor 的因數分解、量子系統模擬）是少數，這正是本書花第三章以後大量篇幅介紹特定演算法的原因。

另一個常見誤解是「量子電腦因為有 \(2^n\) 個振幅，所以等於平行計算了 \(2^n\) 種情況」。這個說法不完整：疊加確實讓 \(n\) 個量子位元同時「攜帶」 \(2^n\) 個振幅，但測量時只能取出一個結果。量子加速的真正來源不是平行計算，而是干涉——設計演算法讓錯誤答案的振幅互相抵消、正確答案的振幅互相加強。

資訊的物理本質#

Landauer 的名言「資訊就是物理（Information is physical）」提示我們：任何計算都必然由某個物理系統執行。古典位元的物理載體（磁疇、電晶體電壓）在我們的普通人觀尺度下運作，量子力學的效應被平均掉；而量子位元刻意把資訊儲存在疊加態與糾纏態這些量子性質中。這帶來兩面刃：一方面獲得古典系統不可能的干涉能力，另一方面也招致退相干（decoherence）與雜訊，這是第 9 章的主題。

用 Python 體會「指數大的狀態空間」#

下面的程式用古典方式儲存 \(n\) 位元系統的機率分佈。即使只是機率（非量子振幅），記憶體也隨 \(n\) 指數成長——這正是 Feynman 說的困境：

import numpy as np

# 古典 n 位元系統：機率分佈的大小是 2^n
for n in [4, 8, 16, 24]:
    dist = np.ones(2**n) / 2**n   # 均勻分佈
    print(f"n={n:2d} 位元，儲存機率分佈需要 {dist.nbytes:>10} 位元組")

# 結果：n=24 時已超過 1600 萬個浮點數，
# 而 40 個位元就需要 10^13 個數字，古典電腦難以負荷。

反觀真正的量子系統，40 個原子「自己就知道」自己該怎麼演化——它不需要任何外在的 \(2^{40}\) 大表格。量子模擬器的目標，就是用古典電腦盡可能逼近這種能力（目前實務上限約 40~50 量子位元）。

練習#

（觀念）有人說「量子電腦就是把所有答案平行算完再挑一個」。請用干涉的概念說明為什麼這句話是誤解。
（程式）修改上方程式，計算 \(n = 30, 32, 40\) 時的位元組需求；再估算你的電腦能儲存多少量子位元的完整複數振幅（每個振幅 16 bytes）。
（複雜度）查閱資料，說明 BQP 與 P、NP、PSPACE 中哪些關係是已被證明的、哪些是未知猜想。