量子計算基礎筆記：從疊加態到量子演算法

這份筆記旨在用最直觀的比喻與圖解，帶你從零開始理解量子計算的核心概念。只要順著往下讀，你就能略懂量子電腦究竟是如何運作，以及它為何能超越傳統電腦。

第一部分：量子世界的物理基礎

1. 單一量子位元與疊加態 (Superposition)

如上圖所示，我們首先觀察單一電子（量子位元 Qubit）。在傳統世界中，位元（Bit）就像靜止的硬幣，不是正面 (1) 就是反面 (0)；但在量子世界中，電子可以處於自旋向上與自旋向下的疊加態。這可以用一個直觀的比喻：就像一枚正在桌面上高速旋轉的硬幣，在被你拍停之前，它同時包含了正面與反面的可能性。

圖中右側給出了精確的幾何定義：

我們可以用一個二維平面上的單位圓來表示單一量子態。
橫軸為本徵態 $|0\rangle$ ，縱軸為本徵態 $|1\rangle$ 。
這個疊加態被寫為線性組合： $a|0\rangle + b|1\rangle$ 。

其中 $a$ 和 $b$ 稱為「概率幅」（Probability Amplitudes），是複數。因為電子最終一定會坍縮到某一個明確的狀態，所以這兩個概率幅的絕對值平方和必須等於 1，這就是圖下方的歸一化條件：

|a|^2 + |b|^2 = 1

2. 多量子位元與量子糾纏 (Quantum Entanglement)

當系統擴展到兩個粒子（兩個電子）時，如上圖所示，狀態空間發生了擴張。我們不再只有兩個狀態，而是產生了四種可能的組合。圖中特別標示了這是一個「量子糾纏」的狀態，意味著這兩個粒子的命運被綁定在一起，無法被單獨拆解描述。改變其中一個，會瞬間影響另一個。

這四種組合的總體量子態可以寫為：

|\psi\rangle = c_1|00\rangle + c_2|01\rangle + c_3|10\rangle + c_4|11\rangle

3. 波函數坍縮與玻恩法則

$c_1, c_2, c_3, c_4$ 平方在這裡為坍縮為不同本徵態的機率。

這句話精準地描述了量子力學中的核心定律——玻恩法則（Born Rule）。雖然在測量前，系統處於四種狀態的疊加，但當我們進行「測量」這個動作（就像拍停那枚旋轉的硬幣）時，波函數會發生「坍縮」（Collapse）。我們無法預測單次測量會得到哪一個結果，但我們能知道得到特定結果的機率，也就是概率幅的絕對值平方。

對應上圖中的具體數據，我們可以清楚看到每個本徵態的坍縮機率：

測量得到 $|00\rangle$ 的機率為 $|c_1|^2 = 28\%$
測量得到 $|01\rangle$ 的機率為 $|c_2|^2 = 24\%$
測量得到 $|10\rangle$ 的機率為 $|c_3|^2 = 20\%$
測量得到 $|11\rangle$ 的機率為 $|c_4|^2 = 25\%$ (備註：嚴謹的物理理論中，所有機率總和必須剛好等於 $100\%$ 。圖中加總為 $97\%$ 是教學演示上的近似。)

4. 維度爆炸與量子態的物理限制

在兩個粒子的情況下，系統存在 $|00\rangle, |01\rangle, |10\rangle, |11\rangle$ 四種基礎狀態，共同構成了一個四維的希爾伯特空間（Hilbert Space）。推廣至 $n$ 個量子位元時，系統將同時疊加了高達 $2^n$ 個本徵態。

為什麼說「無法真正存儲」？ 如此龐大的指數級資訊量，是量子計算強大的來源，同時也是最大的限制。例如，僅僅 50 個量子位元，就需要 $2^{50}$ 個複數概率幅來描述，這資料量超過了全世界超級電腦記憶體的總和。因此，我們在現實中無法真正完整地存儲或直接讀取整個量子態的參數細節。

大自然將這些龐大的資訊隱藏在疊加態中，我們唯一的提取手段就是**「測量」**。測量會瞬間破壞疊加態，迫使系統隨機落入其中一個確定的結果。

第二部分：硬體積木與演算法實踐

既然量子態如此脆弱且難以讀取，我們要怎麼用它來運算？這就需要用到量子邏輯閘。

5. 建構量子電腦的積木：量子邏輯閘

5.1 可逆性與資訊流失

傳統邏輯閘 (如 AND, OR)：圖左顯示，傳統的 AND 或 OR 閘，都是吃進兩個輸入，卻只吐出一個輸出。這種運算是不可逆的，資訊在這個過程中被抹除流失了（物理上會產生廢熱）。
量子邏輯閘 (如 H, CNOT)：圖右顯示，量子邏輯閘的輸入與輸出數量永遠相等。量子力學要求所有的量子運算（測量除外）都必須是完全可逆的（Reversible）。這確保了脆弱的波函數疊加態不會在運算途中崩潰。

5.2 Hadamard 閘 (H 閘)：疊加的引擎

H 閘是量子世界最關鍵的單一量子閘。

它能將確定的 $|0\rangle$ 轉換為均勻的疊加態 $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$ 。
將確定的 $|1\rangle$ 轉換為帶有負相位的疊加態 $\frac{|0\rangle - |1\rangle}{\sqrt{2}}$ 。
幾何意義：H 閘相當於沿著 $22.5^\circ$ (即 $\pi/8$ ) 角度的軸線進行了一次「鏡像反射」。它負責將原本貼在座標軸上的確定狀態，均勻地甩成疊加態。

5.3 CNOT 閘 (受控反閘)：糾纏的樞紐

CNOT (Controlled-NOT) 門是量子計算中創造量子糾纏的機器。

控制位 (上方 $x$ )：作為開關，數值狀態不變。
目標位 (下方 $y$ )：輸出為 $x \oplus y$ 。若控制位是 $1$ ，目標位就翻轉；若是 $0$ ，則保持原樣。

糾纏的誕生：如圖中橘色文字標示，如果你將一個**「已經處於疊加態」的量子位元送入控制位，目標位就會被迫「同時不翻轉且被翻轉」。這一瞬間，兩個量子位元的命運就被緊緊綁定，實體誕生了量子糾纏**！

5.4 CNOT 閘的數學本質：概率幅對調

套用在四個基本狀態上：

$|00\rangle \rightarrow |00\rangle$ / $|01\rangle \rightarrow |01\rangle$ （控制位為0，不變）
$|10\rangle \rightarrow |11\rangle$ / $|11\rangle \rightarrow |10\rangle$ （控制位為1，翻轉）

如果將完整的雙量子疊加態送入 CNOT 閘：

a|00\rangle + b|01\rangle + c|10\rangle + d|11\rangle

經過 CNOT 閘後，狀態變成：

a|00\rangle + b|01\rangle + d|10\rangle + c|11\rangle

從代數上看，**CNOT 閘的作用就是把 $|10\rangle$ 和 $|11\rangle$ 的概率幅（係數 $c$ 和 $d$ ）進行對調！**這種直接在數學矩陣上交換機率幅的能力，是建構演算法的基石。

第三部分：從傳統到量子的典範轉移

了解了硬體積木後，我們來探討：從傳統計算跨越到量子計算，我們的解題思維到底發生了什麼根本性的改變？ 我們以上面提到的「死活黑箱問題（多伊奇演算法）」為例：

6. 計算思維的典範轉移

讓我們先徹底搞懂 $f(0)$ 和 $f(1)$ 到底是什麼意思。假設你有一個「神秘自動販賣機（黑箱）」，按鈕只有兩個：左邊按鈕（代表輸入 $0$ ）與右邊按鈕（代表輸入 $1$ ）。掉出來的飲料只有兩種：可樂（輸出 $0$ ）或雪碧（輸出 $1$ ）。

數學上的 $f(x)$ 就是這台機器的運作規則：

$f(0)$ 就是：你按左邊按鈕，機器掉出什麼飲料？
$f(1)$ 就是：你按右邊按鈕，機器掉出什麼飲料？

這台機器只有兩種可能的設定：

死黑箱 (常數函數 Constant)：這是一台壞掉卡死的機器。不管你按左邊還是右邊，它永遠只掉可樂（ $f(0)=0$ 且 $f(1)=0$ ），或者永遠只掉雪碧（ $f(0)=1$ 且 $f(1)=1$ ）。因為輸入不同但結果相同，所以在數學上我們寫成 $f(0) = f(1)$ 。
活黑箱 (平衡函數 Balanced)：這是一台正常的機器。按左邊掉可樂，按右邊就一定掉雪碧；或者反過來。因為輸入不同，結果就一定跟著不同，所以在數學上我們寫成 $f(0) \neq f(1)$ 。

傳統思維 (Classical Paradigm) - 序列化嘗試

傳統電腦面對問題時，就像一個蒙眼的人在迷宮中摸索。必須先走進第一條路（輸入 $0$ 測一次），退出來，再走進第二條路（輸入 $1$ 測一次）。我們依賴的是**「時間上的重複執行」**，因此必定要查 2 次。

量子思維 (Quantum Paradigm) - 全局干涉

量子電腦解決問題的方式完全不同，它依賴三個魔法步驟：

疊加 (Superposition)：同時探索所有路徑。
相位反彈 (Phase Kickback)：讓黑箱的答案不要改變數值，而是改變波的「正負號」。
干涉 (Interference)：讓錯誤答案互相抵消，正確答案互相增強。這就是從傳統「算兩次」變成量子「算一次」的核心邏輯。

7. 圖解多伊奇演算法：一步步揭開死活黑箱

結合你最新上傳的三張圖，我們來一步步觀看這個「量子思維」是如何在實體線路中發生的。

第一步：準備狀態與製造疊加 (Superposition)

圖中最左側有兩個量子位元：

查詢位 (上方)：初始為 $|0\rangle$ ，通過 H 閘後變成 $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$ 。這等於我們同時把 $0$ 和 $1$ 送進了黑箱。
輔助位 (下方)：初始為 $|1\rangle$ ，通過 H 閘後變成 $\frac{|0\rangle - |1\rangle}{\sqrt{2}}$ 。這個帶有負號的疊加態極度重要，它是誘發後續「相位反彈」的誘餌。

如上圖所示，在即將進入大黑箱 $U_f$ 的那一刻，整個系統的聯合量子態在數學上被精確地寫為：

U_f \left| \frac{|0\rangle + |1\rangle}{\sqrt{2}}, \frac{|0\rangle - |1\rangle}{\sqrt{2}} \right\rangle

圖右側的向量坐標也清晰地標示了此時的狀態：藍色箭頭 $H|0\rangle$ （向右上方的均勻疊加）與紅色箭頭 $H|1\rangle$ （向右下方的帶負號疊加）。這就是量子運算已經準備好、即將射入黑箱中探索真相的「量子子彈」。

第二步與第三步：通過黑箱與干涉測量

當疊加態進入大黑箱 $U_f$ 時，黑箱不會直接輸出結果，而是發生了量子運算中最神奇的**「相位反彈 (Phase Kickback)」**：黑箱會把 $f(0)$ 的結果變成 $|0\rangle$ 前面的正負號，把 $f(1)$ 的結果變成 $|1\rangle$ 前面的正負號（具體來說，運算結果為 0 就是正號，為 1 就是負號）。

這時，查詢位疊加態中的波，會根據黑箱到底是「死」還是「活」而產生兩種截然不同的結局：

結局 A：它是死黑箱 (常數函數 $f(0)=f(1)$ ) 如果黑箱是壞掉的販賣機（死黑箱），代表 $f(0)$ 和 $f(1)$ 的結果一模一樣（例如都是可樂）。這意味著疊加態中 $|0\rangle$ 和 $|1\rangle$ 被賦予的正負號是相同的（不是同為正，就是同為負）。當這兩個相位相同的波再度通過第二個 H 閘時，會產生**「建設性干涉」**。波峰與波峰相疊，波谷與波谷相疊。最終，波函數 100% 退回成藍色的 $|0\rangle$ 。所以，測量儀器只要看到 $|0\rangle$ ，我們就能斷定：這是一個死黑箱。

結局 B：它是活黑箱 (平衡函數 $f(0)\neq f(1)$ ) 如果黑箱是正常的販賣機（活黑箱），代表 $f(0)$ 和 $f(1)$ 的結果一定相反（一個可樂一個雪碧）。這意味著疊加態中 $|0\rangle$ 和 $|1\rangle$ 被賦予的正負號一定是一正一負。當這兩個相位相反的波碰撞並通過第二個 H 閘時，會產生**「破壞性干涉」**。波峰與波谷互相抵消，導致原本的狀態翻轉。最終，波函數會 100% 坍縮成紅色的 $|1\rangle$ 。所以，測量儀器只要看到 $|1\rangle$ ，我們就能斷定：這是一個活黑箱。

總結：這就是量子的勝利 傳統電腦必須把黑箱拆開看兩次。但量子電腦利用了波的疊加與干涉，讓黑箱自己把答案「算」出來並反映在最終的坍縮機率上。只需一次測量，真相大白！這就是從傳統計算跨越到量子計算，最迷人的思維轉變。

【進階補充】多伊奇演算法的嚴格數學推導 (Dirac Notation)

如果你對背後的硬核代數推導感興趣，這裡是一步步、毫無省略的完整數學證明：

2. 經過第一層 H 閘 ( $|\psi_1\rangle$ ) 兩個量子位元各自通過 Hadamard 閘。H 閘的定義是 $H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$ ，以及 $H|1\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$ 。將其張量積（ $\otimes$ ）展開： $|\psi_1\rangle = H|0\rangle \otimes H|1\rangle = \left( \frac{|0\rangle + |1\rangle}{\sqrt{2}} \right) \otimes \left( \frac{|0\rangle - |1\rangle}{\sqrt{2}} \right)$ 為了方便後續推導，我們將右側的輔助位簡寫為 $|-\rangle$ ，所以狀態可寫為： $|\psi_1\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle \otimes |-\rangle + |1\rangle \otimes |-\rangle \big)$

3. 證明「相位反彈 (Phase Kickback)」原理 量子黑箱的定義是 $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$ 。我們現在單獨來看，如果把任意狀態 $|x\rangle$ 和輔助位 $|-\rangle$ 一起送進去，會發生什麼事？ $U_f |x\rangle \left( \frac{|0\rangle - |1\rangle}{\sqrt{2}} \right) = \frac{U_f|x\rangle|0\rangle - U_f|x\rangle|1\rangle}{\sqrt{2}}$ 根據黑箱的 XOR ( $\oplus$ ) 定義，這等於： $= \frac{|x\rangle|0 \oplus f(x)\rangle - |x\rangle|1 \oplus f(x)\rangle}{\sqrt{2}}$ 這時我們分兩種情況討論 $f(x)$ 的值：

如果 $f(x) = 0$ ： $0 \oplus 0 = 0$ 且 $1 \oplus 0 = 1$ 。上面式子變成 $\frac{|x\rangle|0\rangle - |x\rangle|1\rangle}{\sqrt{2}} = |x\rangle \left( \frac{|0\rangle - |1\rangle}{\sqrt{2}} \right) = (+1) |x\rangle|-\rangle$
如果 $f(x) = 1$ ： $0 \oplus 1 = 1$ 且 $1 \oplus 1 = 0$ 。上面式子變成 $\frac{|x\rangle|1\rangle - |x\rangle|0\rangle}{\sqrt{2}} = -|x\rangle \left( \frac{|0\rangle - |1\rangle}{\sqrt{2}} \right) = (-1) |x\rangle|-\rangle$

注意到規律了嗎？無論 $f(x)$ 是 0 還是 1，我們都可以把這個結果用一個極度優雅的數學式統一表達： $U_f |x\rangle|-\rangle = (-1)^{f(x)} |x\rangle|-\rangle$ **這就是相位反彈的嚴格證明！**黑箱並沒有改變輔助位，而是把運算結果 $f(x)$ 變成了 $x$ 前面的正負號！

4. 通過黑箱 $U_f$ 得到完整狀態 ( $|\psi_2\rangle$ ) 現在我們把剛剛證明的規則，套用到步驟 2 算出來的完整狀態 $|\psi_1\rangle$ 上： $|\psi_2\rangle = U_f \left[ \frac{1}{\sqrt{2}} \big( |0\rangle|-\rangle + |1\rangle|-\rangle \big) \right]$ 因為矩陣乘法具有分配律，我們可以拆開來算： $= \frac{1}{\sqrt{2}} \big( U_f|0\rangle|-\rangle + U_f|1\rangle|-\rangle \big)$ 對這兩項分別套用我們剛剛證明的相位反彈規則： $= \frac{1}{\sqrt{2}} \big( (-1)^{f(0)}|0\rangle|-\rangle + (-1)^{f(1)}|1\rangle|-\rangle \big)$ 最後，把共同的輔助位 $|-\rangle$ 提出來，我們就得到了查詢位進入第二個 H 閘前的精確狀態： $|\psi_2\rangle = \left[ \frac{(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle}{\sqrt{2}} \right] \otimes |-\rangle$

5. 經過第二層 H 閘與最終測量 現在輔助位已經功成身退，我們只看中括號裡的「查詢位狀態」。

若為死黑箱 (常數函數)：
- 假設 $f(0)=0, f(1)=0$ ：狀態為 $\frac{+ |0\rangle + |1\rangle}{\sqrt{2}}$ 。這正是 $|+\rangle$ 態，通過 H 閘後變回 $|0\rangle$ 。
- 假設 $f(0)=1, f(1)=1$ ：狀態為 $\frac{- |0\rangle - |1\rangle}{\sqrt{2}}$ 。提出負號變為 $-(|+\rangle)$ ，通過 H 閘後變成 $-|0\rangle$ 。無論哪種，前方的正負號不會影響測量機率，測量儀器必定 100% 測出 $0$ 。
若為活黑箱 (平衡函數)：
- 假設 $f(0)=0, f(1)=1$ ：狀態為 $\frac{+ |0\rangle - |1\rangle}{\sqrt{2}}$ 。這正是 $|-\rangle$ 態，通過 H 閘後變為 $|1\rangle$ 。
- 假設 $f(0)=1, f(1)=0$ ：狀態為 $\frac{- |0\rangle + |1\rangle}{\sqrt{2}}$ 。提出負號變為 $-(|-\rangle)$ ，通過 H 閘後變成 $-|1\rangle$ 。無論哪種，測量儀器必定 100% 測出 $1$ 。

這就是量子力學如何透過嚴謹的線性代數與張量運算，毫無破綻地在一次操作內萃取出黑箱全域性質的數學奇蹟！

6. 幾何視角的終極視覺化

你上傳的這最後兩張圖，為前面枯燥的代數推導提供了最直觀的幾何與物理意義！

反射前（黑箱剛輸出時）：

綠色軸線 ( $f(0)=f(1)$ )：當黑箱為死黑箱時，查詢位的狀態向量會落在這條 $45^\circ$ 的軸線上（即數學推導出的 $\pm |+\rangle$ 態）。
紫色軸線 ( $f(0)\neq f(1)$ )：當黑箱為活黑箱時，狀態向量會落在這條 $-45^\circ$ 的軸線上（即 $\pm |-\rangle$ 態）。

反射後（經過第二個 H 閘干涉）： 這時，第二個 H 閘發揮了作用。回憶我們在第 5.2 節學到的，H 閘是一面沿著 $22.5^\circ$ （圖中黃線）擺放的鏡子。

把 $45^\circ$ 的綠色向量往黃線鏡子一照，反射下來剛剛好平貼在水平的 X 軸上，也就是 $|0\rangle$ ！
把 $-45^\circ$ 的紫色向量往黃線鏡子一照，反射上去剛剛好垂直貼在 Y 軸上，也就是 $|1\rangle$ ！

至此，多伊奇演算法的謎底徹底解開：代數上的「正負號提出公因式」，在幾何空間中就是「向量在不同對角線上的疊加」；而代數上的「波函數干涉」，在幾何空間中就是「利用 H 閘進行的完美鏡像反射」。

第四部分：尋找大海撈針：Grover 演算法 (Grover's Algorithm)

前面我們用「多伊奇演算法」證明了量子計算可以一次看透黑箱的全域性質。現在，我們要介紹量子計算史上的另一座巔峰：Grover 搜尋演算法。它展示了量子電腦如何在外送資料庫的「搜尋問題」上，展現出壓倒性的速度優勢。

8. 未排序資料庫的搜尋難題與黑箱

想像你有一個包含 $N$ 筆資料的「無序資料庫」（例如有 100 萬個沒按字母排列的名字），你的任務是從中找出唯一一個「正確的目標」。

在數學上，這同樣可以寫成一個黑箱函數 $f(x)$ ：

當輸入的 $x$ 不是目標時，黑箱輸出 $0$ （ $f(x) = 0$ ）。
當輸入的 $x$ 正是目標時，黑箱輸出 $1$ （ $f(x) = 1$ ）。

傳統思維：一個一個找 (複雜度 $O(N)$ )

在傳統電腦的世界裡，面對完全沒有規律的 $N$ 個抽屜，你唯一的辦法就是「一個一個打開來看」。

最壞情況：你要開 $N$ 次才找到。
平均情況：你要開 $N/2$ 次。如果 $N$ 是一億，傳統電腦平均需要查 5000 萬次黑箱。

量子思維：Grover 演算法 (複雜度 $O(\sqrt{N})$ )

1996 年，Lov Grover 提出了一種震驚世人的量子演算法。利用量子疊加與干涉，量子電腦只需要開啟黑箱大約 $\sqrt{N}$ 次 就能找到目標！如果 $N$ 是一億， $\sqrt{100,000,000} = 10,000$ 。傳統電腦要找 5000 萬次，量子電腦只要找 1 萬次！當數據量越大，這種「開根號」的加速效果就越恐怖。

9. 圖解 Grover 黑箱過程：振幅放大 (Amplitude Amplification)

Grover 演算法是如何在茫茫數據中，把正確答案「撈」出來的？它的核心機制分為三個不斷循環的魔法步驟：

第一步：均勻疊加 (灑下大網)

首先，我們用 H 閘對所有量子位元進行操作，創造出一個包含所有 $N$ 個可能性的「均勻疊加態」。這就像是我們同時派出 $N$ 個分身，站在每一個抽屜前面。此時，每一個答案被測量到的機率幅都是一樣平的（高度為 $\frac{1}{\sqrt{N}}$ ）。

第二步：黑箱標記 (相位反轉 Phase Inversion)

接著，我們把這個龐大的疊加態送入我們設定好的黑箱 $U_f$ 中。還記得我們在多伊奇演算法學過的**「相位反彈 (Phase Kickback)」**嗎？這裡發生了一模一樣的事！黑箱並不會告訴我們答案在哪，但它會在疊加上動手腳：

對於所有錯誤的答案（ $f(x)=0$ ），黑箱給它們乘上 $(-1)^0 = +1$ ，也就是毫無反應。
對於那個唯一的正確答案（ $f(x)=1$ ），黑箱給它乘上 $(-1)^1 = -1$ ，也就是把它的概率幅往下翻轉變成負的！

在數學視覺上，原本大家都是平平的波浪，現在正確答案的波谷突然朝下凹陷了。雖然機率（絕對值平方）還是一樣，但它已經被黑箱悄悄打上了「負號」的記號。

第三步：Grover 擴散算子 (振幅放大)

這是最精妙的一步。我們對整個系統進行一個叫做「沿著平均值翻轉 (Inversion about the mean)」的幾何操作。

計算平均高度：因為有一個答案變成負的了，所以所有答案概率幅的「平均基準線」會稍微往下降一點點。
鏡像翻轉：我們把所有的概率幅，以這條新的平均基準線為鏡子，上下顛倒過來。

發生了什麼事？

原本是正的（錯誤答案）：距離平均線很近，翻轉後變得更矮了。
原本是負的（正確答案）：距離平均線非常遠，翻轉後像彈簧一樣，直接衝上雲霄，變得超級高！

循環與最終測量

我們只要把「第二步（黑箱標記）」與「第三步（振幅放大）」重複執行約 $\sqrt{N}$ 次。每一次循環，正確答案的機率幅就會越來越高，錯誤答案的機率幅就會越來越矮。最後進行測量時，整個量子波函數幾乎會 100% 坍縮在那個唯一的正確答案上！這就是量子計算在搜尋問題上展現的終極暴力美學。