大家早安，今天我們來談談 Grover 演算法。這個經常被引用的量子計算範例，看似只是一個搜尋技巧，但它其實揭示了量子電腦到底能快多少的邊界。許多初學者最困惑的地方在於：既然 Oracle 已經標記了正解，為什麼還需要反覆迭代？要回答這個問題，我們得先釐清 Oracle 到底是什麼，以及它的發明人 Lov Grover 當年如何提出這個想法。
Grover 演算法由印度裔美國科學家 Lov Grover 在 1996 年提出，定義了量子搜尋的數學極限。
Grover 演算法由印度裔美國科學家 Lov Grover 在 1996 年提出，當時他在美國貝爾實驗室工作。這個時期正是量子計算的萌芽階段，Shor 在 1994 年剛提出能破解 RSA 的質因數分解演算法，震撼了密碼學界。Grover 的工作雖然不像 Shor 那樣直接針對密碼體系，但卻回應了一個更基本的問題：量子計算是否能加速一般的搜尋問題。
Grover 的答案是：可以，但只能提供平方根級的加速，這個結果定義了量子搜尋的上限。從此以後，Grover 的名字幾乎和量子搜尋畫上等號。Oracle 是什麼？
在量子演算法裡，Oracle 不是神祕的黑箱，而是規則檢查器的量子化版本。
- 在經典世界，它是一個函數 f(x)，輸入一個候選解，輸出 1（正解）或 0（錯誤）。
- 在量子世界，它被實作為可逆電路，能對所有輸入疊加同時作用。正解的分量會被乘上一個 −1 的相位，其他分量保持不變。
這就是 Grover Oracle 的標記：它沒有告訴你答案是誰，但在量子態裡替正解加上了一個隱形標籤。
如果在 Oracle 後立刻測量，正解的機率仍然只有 1/N。原因是一開始所有候選的幅度均勻，標記只是翻轉相位，沒有提升正解的振幅。量子測量只會隨機塌縮到某個候選解，大部分情況仍然會是錯的。換句話說，Oracle 只是讓正解的方向與其他方向不同步，提供後續干涉操作的起點。
為什麼標記不等於找到
如果在 Oracle 後立刻測量，正解的機率仍然只有 1/N。原因是一開始所有候選的幅度均勻，標記只是翻轉相位，沒有提升正解的振幅。量子測量只會隨機塌縮到某個候選解，大部分情況仍然會是錯的。換句話說，Oracle 只是讓正解的方向與其他方向不同步，提供後續干涉操作的起點。
√N 次迭代：放大正解
這張圖展示了 Grover 演算法中「機率放大」的幾何視覺化。左邊的矩陣條形圖代表搜尋空間中每個候選解的振幅分佈。最開始時所有狀態的振幅相等（約 0.027），但隨著反覆應用 Oracle 與擴散運算子，正解 ∣ 𝑘 ⟩ ∣k⟩ 的振幅逐漸被放大到接近 1（圖中約 0.964），其他狀態則保持微小。 右邊的圓圖則是「狀態向量旋轉」的幾何詮釋。初始狀態與正解方向之間有一個角度 𝜃 ≈ 1 / 𝑁 θ≈1/ N 。每次 Grover 迭代會讓整個狀態向量繞著二維平面旋轉 2 𝜃 2θ，逐步靠近正解方向。經過大約 𝜋 / 4 𝑁 π/4 N 次迭代後，狀態幾乎完全對準正解軸，測量時正解出現的機率就非常高。
Grover 的核心在於將 Oracle 與擴散算子交替使用。擴散算子會根據平均值調整幅度，把低於平均的分量壓低，把高於平均的分量抬高。當它與 Oracle 的相位標記結合後，整個量子態在「正解」與「非正解」張成的二維平面內旋轉。
- 每次迭代，正解的機率會增加一些
- 經過大約 √N 次迭代，正解的振幅接近 1
- 這時測量，幾乎必然塌縮到正解
因此，√N 次不是標記的成本，而是把隱形標籤放大成可測量答案所需的次數。
Grover 的意義與邊界
Grover 的價值不只是展示量子加速，而是界定了邊界：對於無結構搜尋，量子電腦最多能給你平方根級的提升。經典要 N 次，Grover 只要 √N 次，這已經是最優的結果。這對密碼學影響巨大，例如 128 位元密鑰在量子環境下等效於 64 位元強度，因此國際標準必須翻倍強化。Grover 同時提醒我們，量子計算不是萬能，不是所有問題都能獲得指數級加速。
Lov Grover 的名字因此永遠與這個過程綁在一起，他給出了量子搜尋的數學極限，也幫我們認清：量子計算雖然強大，但它的快是有邊界的。
