如果你問一位量子物理學家：「量子電腦到底哪裡快？」他多半會從 1985 年大衛·多伊奇（David Deutsch）提出的這個問題講起。
Deutsch-Jozsa 演算法雖然不是一個具備商用實效的演算法，但它卻是歷史上第一次震撼世界的概念驗證。它用最純粹的數學，向人類展示了量子運算如何徹底顛覆效率的極限。
黑箱裡的秘密：常數型 vs. 平衡型
想像你有一個神祕的黑箱（我們稱之為 Oracle，預言機），它接收 n 個位元的輸入，並輸出一個位元（0 或 1）作為結果。
這個黑箱被保證只有兩種可能：
- 常數型 (Constant)：不論你輸入什麼，結果永遠是一樣的（全都是 0，或全都是 1）。
- 平衡型 (Balanced)：輸入的所有可能中，剛好有一半結果是 0，另一半是 1。
最少要測幾次，才能百分之百確定它是哪一種？
假設輸入有 n=10 位元，總共有 210 = 1024 種組合
- 古典做法：你測了第 1 個是 0，第 2 個也是 0... 你必須運氣極差地測到第 513 個（一半加一個）還是 0，你才能鐵證如山地說它是常數型
- 代價：隨著輸入位元 n 增加，古典電腦需要嘗試的次數會呈現指數級爆炸
量子電腦的一擊必殺
Deutsch-Jozsa 演算法最神的地方在於：不論輸入位元 n 有多大（是 10 個還是 10 萬個），量子電腦都只需要執行一次黑箱運算，就能給出答案。
它是如何辦到的？這涉及到我們之前學過的三個核心招式：
- 量子並行（Superposition）：我們利用 Hadamard (H) 閘，讓所有可能的輸入（2n種）同時進入黑箱。這就像是在無數個平行宇宙中同時測試了所有組合，並將結果編碼在一個巨大的波函數裡。
- 相位踢回（Phase Kickback）：這是量子演算法中最精妙的變色龍詭計。我們不是去讀取黑箱吐出的 0 或 1，而是讓這個結果直接影響波函數的相位（正負號）。
- 干涉毀滅（Interference）：最後，我們再施加一次 H 閘，讓這些攜帶答案的相位發生干涉。
- 如果是常數型：所有的相位會發生建設性干涉，最終測量結果一定是全 0
- 如果是平衡型：相位會發生毀滅性干涉，測量結果一定會出現 非 0 的數字
總結與會員專屬補充
- 黑箱問題：判斷函數是全等還是平衡
- 古典限制：最差需要試 2n-1 + 1 次
- 量子優勢：永遠只需要 1 次。這就是量子霸權（Quantum Supremacy）的最早理論原型
儘管 Deutsch-Jozsa 在數學上實現了指數加速，但它在當時被戲稱為解決了一個沒人想解決的問題。它向世人證明了，量子電腦的加速不是靠時脈變快，而是靠改變運算的底層邏輯（從窮舉法變成干涉法）。
現在的硬體已經可以穩定執行這類小規模演算法。這套「把答案藏在相位、最後用干涉讀取」的邏輯，後來直接啟發了震驚金融業的 Shor 演算法。
H 閘的「鏡像」本質
H 閘是它自己的逆運算。
- 如果你對 |0> 做一次 H 閘，它會變成疊加態 |+>
- 如果你再做一次 H 閘，它會「完美干涉」回到 |0>
在 Deutsch-Jozsa 演算法中，我們在 Oracle（黑箱）前後各放了一排 H 閘。
- 前面的 H 閘：負責「打開」疊加態，讓所有可能性同時進入黑箱。
- 後面的 H 閘：負責「關閉」疊加態，也就是進行干涉，將相位資訊轉化回我們可以測量的 0 與 1。
常數型的狀況：什麼都沒發生
當黑箱是常數型時，代表不論輸入什麼，黑箱給出的結果 f(x) 都是一樣的（例如全是 0）。在數學上，這意味著黑箱對所有的輸入路徑都加上了相同的相位（或者完全沒加）。
- 關鍵邏輯：因為每一條路徑（所有的 |x>）被加上的相位都一樣，這就等於「沒加相位」，或者是幫整個波函數加上了一個「全域相位」（Global Phase）。
- 全域相位的特性：全域相位在物理測量上是看不見的，它不會改變不同路徑之間的「相對關係」。
結論： 對於量子位元來說，它感覺自己進去黑箱後什麼都沒發生（或只是被整體塗了個顏色）。當它出來遇到後面的 H 閘時，就像是 |+> 再次遇到 H 閘，會發生 100% 的建設性干涉，直接回歸到初始狀態：全 0。
平衡型的狀況：相位的大亂鬥
當黑箱是平衡型時，事情就變得刺激了。有一半的路徑會被加上負號（相位翻轉），另一半則保持不變。
- 關鍵邏輯：當這些正負不一的疊加態遇到最後一排 H 閘時，它們不再能完美地整隊回歸 |0>
- 毀滅性干涉：原本應該回歸到 |0> 的路徑，會因為那些帶有負號的路徑而發生毀滅性干涉，導致測量到「全 0」的機率變成 0。
結論： 只要最後測量結果中出現了任何一個 1（即非全 0），就代表黑箱裡面一定有「相位翻轉」發生，那它絕對是平衡型。
如果我們把 H閘看作是一種基底轉換
- 全 0 態 對應的是所有路徑同相疊加
- 如果黑箱是 常數型 → 路徑依然同相 → 投影回全 0 態的機率是 1
- 如果黑箱是 平衡型 → 路徑相位正負抵消 → 投影回全 0 態的機率是 0
這就是為什麼我們不需要看遍所有答案，只需要看最後測量結果是不是全 0，就能反推黑箱內部的結構。
