一台不同的機器，而非一台更快的機器
在這一階梯的第一篇，你讓圖靈機擲硬幣、並接受一點小小的出錯機率；那給了你 BPP，也就是一台「隨機化」機器能高效解決的問題。量子電腦聽起來像是同一個點子加碼——「一次嘗試所有可能」——但這句口號是有史以來關於它「最誤導」的說法，而拋棄它正是這一篇的全部用意。一台量子機器不是跑得更快的圖靈機，也不是骰子更好的隨機化機器。它是一個不同的計算模型，有它自己「組態如何演化」的規則，而從那條規則就生出了它自己的複雜度類別 BQP（有界誤差量子多項式時間）。
用日常語言講，差別的誠實核心在這裡。一台隨機化機器在任一時刻「就是」處於某一個確定的組態——你只是不知道是哪一個，所以你用機率來描述它，那是一串相加為一的非負數。一台量子機器則改為攜帶一串振幅，每個可能的組態各一個，而振幅是帶正負號的（可以是正或負，實際上是複數）。當你最終測量、要讀出看到某個組態的機會時，你把它的振幅平方。機率永遠只會相加；振幅因為帶正負號，還能相減。這一件事——通往同一個結果的兩條路徑可以彼此抵消——就是量子加速的整部引擎。這裡沒有任何神秘之處；它只是「用帶號數而非無號數記帳」罷了。
干涉，用一張小小的圖
最小的誠實例子用「一個」量子位元和「一個」閘。一個量子位元的組態由兩個振幅刻畫，一個對應結果「0」、一個對應結果「1」。一個隨機化的擲硬幣閘會把確定的「0」變成一半一半的混合，而把同一枚硬幣擲「兩次」也只會把你留在一半一半——隨機性永遠無法「解混合」。它的量子對應物，Hadamard 閘，做出了隨機性做不到的事：作用在確定的「0」上，它產生對 0 與 1 相等的振幅；但作用「第二次」時，通往「1」的兩條路徑帶相反正負號而抵消，而通往「0」的兩條路徑彼此增強——於是你「確定地」落回確定的「0」。兩個隨機步驟使一切模糊；兩個量子步驟卻能使一切銳化。這就是干涉在做看得見的工作。
Coin (randomness): probabilities, never subtract
|0> --flip--> {0: 1/2, 1: 1/2} --flip--> {0: 1/2, 1: 1/2} blurred, stuck
Qubit (quantum): amplitudes are SIGNED, so they can cancel
|0> --H--> { 0: +1/sqrt2 , 1: +1/sqrt2 } (equal amplitudes)
--H--> outcome 0 : (+1/sqrt2)(+1/sqrt2) + (+1/sqrt2)(+1/sqrt2) = +1
outcome 1 : (+1/sqrt2)(+1/sqrt2) + (+1/sqrt2)(-1/sqrt2) = 0 <-- CANCELS
==> measure 0 with probability 1 (sharpened back to certainty)
Measure once -> ONE outcome, prob = amplitude^2. You never read all paths.BQP 是什麼，它落在地圖的哪裡
BQP 的定義，恰恰是 BPP 的量子鏡像。若某個多項式大小的量子閘序列能判定一個語言，這個語言就屬於 BQP：在每一個輸入上，機器以至少（譬如）2/3 的機率輸出正確答案，而且和 BPP 一樣，你可以靠重複執行並取多數決，把那個 2/3 推到要多接近確定就多接近。所以 BQP 就是「量子電腦能高效解決、且帶有一個小而可控的出錯機率」的問題。它是一個完全正當的複雜度類別，由一個模型（量子閘）上的一個資源界限（多項式時間）所定義，就和先前的 P 與 NP 一模一樣。
它嵌進你一路建立的類別地圖的哪裡？有兩個包含關係已被證明、也值得記住名字。第一，BPP 在 BQP 之中：一台量子機器永遠可以「選擇」不去干涉，純粹模擬公平的擲硬幣，所以隨機性能做的事，量子都能做。第二，也是真正的天花板，BQP 在 PSPACE 之中：你可以在一台普通的圖靈機上模擬一個量子電路，做法實際上是「對每個最終組態，把所有計算路徑上的振幅加總起來」——路徑有指數多條，但每一條都很短，所以你可以一邊重複利用、只用多項式多的空間把它們加完。光這一件事，就是對所有炒作的一記有力的可信度檢查，我們下一節就把它拆開來看。
為什麼它「不是」一台能解 NP 的魔法機器
現在來談那條頭條更正。流行的說法是：量子電腦只要「一次查驗所有候選解」，就能單純地「破解」每一個 NP 完全問題——每一道數獨、每一條旅行推銷員路線、每一個排程難題。就目前所有人曾經證明過的而言，這是錯的，而且大家根本不相信它是真的。麻煩正在於那句口號所忽略的事：在全部 2^n 個候選答案上做疊加很容易，但一次測量「只」回傳其中一個，依其振幅平方為機率挑出。要解一個困難的搜尋問題，你會需要干涉把「每一個」錯誤答案的振幅都抹掉、全部堆到那個稀有的正確答案上——而對一個沒有可利用結構的一般 NP 問題，沒有人知道該如何造出那樣的干涉。
量子電腦在「無結構搜尋」上「確實」買到的東西，是被精確度量過、而且很有限的。Grover 演算法能在約 sqrt(N) 步、而非 N 步內，搜遍一個 N 個候選的無序空間——一個貨真價實的平方根加速，而且可證明這是任何量子演算法對盲目搜尋所能做到的極限。平方根加速是真的、也有用，但它不是 NP 完全會要求的那種指數級飛躍：把 2^n 變成約 2^(n/2)，你面對的仍然是一個指數，只是把指數砍了一半。所以即使是 Grover，套用在一個 3-SAT 實例上，也不會讓 NP 完全問題變得可解；它只是削掉一點指數，如此而已。
那個著名的指數級勝利——用來分解大整數的 Shor 演算法——看似一個反例，實則恰恰相反:它是「證明了規則」的那個例外。分解整數「並非」NP 完全；它是一個帶有深層隱藏週期結構的特殊問題，而 Shor 演算法之所以管用，正是靠干涉去偵測那個週期（透過量子傅立葉變換）。教訓很犀利：量子加速來自一個問題「碰巧」具有的結構，而非來自蠻力的平行搜尋。這也是為什麼量子計算威脅到特定的密碼系統——RSA 與 Diffie–Hellman 建立在「分解整數與離散對數很難」之上，而那正是 Shor 所破解的那些有結構的問題——卻大致沒動到一般 單向函數 與精選對稱式密碼的安全性（後者只被 Grover 平方根地削弱了一點）。
它真正動搖的東西：邱奇–圖靈論題
如果量子電腦無法破解 NP，那它深層的意義在哪？不在於「什麼能被計算」——一台量子機器計算的語言，與圖靈機計算的「完全相同」，因為（如我們所見）一台古典機器可以模擬它，只是很慢。談「到底什麼可計算」的邱奇–圖靈論題絲毫未動。挑戰落在它一個更強的、量化的表親身上：延伸邱奇–圖靈論題，它主張每一台合理的物理電腦，都能被一台圖靈機以「至多多項式」的減速模擬。如果 Shor 演算法真的比任何可能的古典方法都指數級地更快分解整數——這我們相信，但再說一次，尚未證明——那麼量子電腦就是一台「物理上合理」、卻是古典機器「無法」以多項式追上的裝置，於是延伸論題就是錯的。
這才是那條誠實的頭條。量子計算的革命性主張不是「NP 現在很容易」，而是「邱奇–圖靈論題的效率版本可能是錯的——高效計算的自然單位，也許是量子電路，而非古典的圖靈機」。其餘一切都從這裡流出：也許是 BQP、而非 P 或 BPP，才是「可行可解」問題最真實的那個類別，而古典電腦在某些有結構的工作上，只是一個嚴格而更慢的子集。這是一個深刻的轉變，而且請注意它有多麼有紀律——它完全建立在你從第一階梯起就一直在用的「計算模型」思維上：定義一台機器、界住它的資源、然後誠實地問哪些問題落在裡面。