Deutsch-Jozsa 演算法：量子加速的首秀

如果你問一位量子物理學家：「量子電腦到底哪裡快？」他多半會從 1985 年大衛·多伊奇（David Deutsch）提出的這個問題講起。

Deutsch-Jozsa 演算法雖然不是一個具備商用實效的演算法，但它卻是歷史上第一次震撼世界的概念驗證。它用最純粹的數學，向人類展示了量子運算如何徹底顛覆效率的極限。

黑箱裡的秘密：常數型 vs. 平衡型

想像你有一個神祕的黑箱（我們稱之為 Oracle，預言機），它接收 n 個位元的輸入，並輸出一個位元（0 或 1）作為結果。

這個黑箱被保證只有兩種可能：

1. 常數型 (Constant)：不論你輸入什麼，結果永遠是一樣的（全都是 0，或全都是 1）。
2. 平衡型 (Balanced)：輸入的所有可能中，剛好有一半結果是 0，另一半是 1。

最少要測幾次，才能百分之百確定它是哪一種？

假設輸入有 n=10 位元，總共有 2¹⁰ = 1024 種組合

• 古典做法：你測了第 1 個是 0，第 2 個也是 0... 你必須運氣極差地測到第 513 個（一半加一個）還是 0，你才能鐵證如山地說它是常數型
• 代價：隨著輸入位元 n 增加，古典電腦需要嘗試的次數會呈現指數級爆炸

量子電腦的一擊必殺

Deutsch-Jozsa 演算法最神的地方在於：不論輸入位元 n 有多大（是 10 個還是 10 萬個），量子電腦都只需要執行一次黑箱運算，就能給出答案。

它是如何辦到的？這涉及到我們之前學過的三個核心招式：

1. 量子並行（Superposition）：我們利用 Hadamard (H) 閘，讓所有可能的輸入（2ⁿ種）同時進入黑箱。這就像是在無數個平行宇宙中同時測試了所有組合，並將結果編碼在一個巨大的波函數裡。
2. 相位踢回（Phase Kickback）：這是量子演算法中最精妙的變色龍詭計。我們不是去讀取黑箱吐出的 0 或 1，而是讓這個結果直接影響波函數的相位（正負號）。
3. 干涉毀滅（Interference）：最後，我們再施加一次 H 閘，讓這些攜帶答案的相位發生干涉。

• 如果是常數型：所有的相位會發生建設性干涉，最終測量結果一定是全 0
• 如果是平衡型：相位會發生毀滅性干涉，測量結果一定會出現 非 0 的數字

總結與會員專屬補充