JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Grover 搜尋演算法

Grover 演算法能在雜亂無序的「大海」中撈出那根「針」,比任何古典搜尋都快——但只是平方級地快,大約用 sqrt(N) 步而不是 N 步。它的做法是在許多輪裡把一個量子態輕輕地朝答案方向旋轉,而不是一次性檢查所有答案。本指南會誠實地幫你建立直覺,讓你確切知道這份收益到底有多大(以及有多有限)。

無結構搜尋問題

想像一本有 N 個條目的電話簿,但它被打亂成了隨機順序。給你一個電話號碼,讓你找出對應的姓名。沒有排序、沒有索引、沒有任何巧妙的捷徑——你唯一能做的,就是挑一個條目,檢查它是否匹配。這就是無結構搜尋:資料中沒有任何你可以利用的規律。

在古典做法裡,你只能一個一個地檢查條目。運氣好的話,第一次就找到答案;運氣差的話,它是你檢查的最後一個。平均下來你大約要看一半,而最壞情況要看全部 N 個。所以古典的無結構搜尋的代價大約是 N 次檢查。當資料真的毫無結構時,這一點是繞不開的。

Grover 演算法正是在量子線路上解決這個問題的。它並不會神奇地同時讀取每一個條目,然後把答案交給你。相反,它大約用 sqrt(N) 步就能找到那個被標記的條目——這是一個真實但有限的提升,我們會在結尾把它說精確。

預言機(oracle)

Grover 需要一種辦法,在看到答案時能認出它來。這個識別器就是預言機:一個量子子程序,它接受一個索引 x,並告訴你 x 是不是你要找的那個項。關鍵在於,認出答案很容易;而在 N 種可能裡把它*找出來*才是難點。(檢查一個密碼對不對是小事一樁;猜出它來可就不是了。)

因為每一個量子閘都必須是么正的且可逆的,所以預言機不能簡單地印出一個"是"就停下來。它的做法是:透過翻轉那一個態的符號(也就是相位)來標記正確答案,而其他所有態原封不動。如果 w 是獲勝的索引,那麼預言機做的是:

oracle action on each basis state |x>:

  |x>  -->  -|x>   if x is the answer (x = w)
  |x>  -->  +|x>   if x is not the answer

so a uniform superposition over 4 items:

  before:  +|00>  +|01>  +|10>  +|11>
  after:   +|00>  +|01>  -|10>  +|11>     (here w = |10>)
             ^      ^      ^      ^
           same   same   FLIPPED same
相位預言機只翻轉被標記態的符號。此時還沒有進行任何測量——這次翻轉對直接測量是不可見的,因為機率取決於 |振幅|^2,而 (-x)^2 = x^2。

振幅放大,逐步拆解

Grover 演算法的引擎是振幅放大。你讓每一個索引都從一個均等的疊加態出發,然後重複一個由兩步動作組成的回合,把振幅從錯誤答案那裡挪開、朝正確答案那裡聚攏。每一回合都依靠干涉——振幅之間的相加與抵消——而不是去查看各個態。

  1. 準備: 對每一個量子位元施加一個 Hadamard 閘,製備出一個均勻疊加態。有 N 個項時,每個振幅都是 1/sqrt(N)——每個答案的(不)可能性都相同。
  2. 標記(預言機): 翻轉獲勝態的相位。它的振幅變為負值;其餘所有的都保持為正。
  3. 擴散(關於均值的反演): 把所有振幅關於它們的平均值做反射。因為被標記的振幅突出在均值之下,這次反射會讓它變大,同時讓其餘的略微縮小。
  4. 重複: 把標記 + 擴散一起跑大約 sqrt(N) 次。每一回合都把量子態朝答案再旋轉近一點點。
  5. 測量一次: 讀出暫存器。你有很高的機率得到那個被標記的索引——但你只會得到恰好一個結果,而且量子態會塌縮,所以你沒法在中途偷看。

一個有用的心智圖景:整個量子態就是一支箭頭(向量),它處在由"答案"和"其餘一切"張成的二維平面裡。每一個標記+擴散回合,都會把這支箭頭朝著答案那條軸旋轉一個固定的小角度。在恰當的時機停下,箭頭就會幾乎正好指向答案;越過那個點繼續做下去,它就會旋轉過頭,重新開始擺離答案。

amplitude of each item across rounds (N = 16, answer = item #6):

 start:  all bars equal (1/4 = 0.25 each)
         item:  0   1   2   3   4   5   6   7  ...
         amp:  .25 .25 .25 .25 .25 .25 .25 .25

 after a few mark+diffuse rounds:
         amp:  .10 .10 .10 .10 .10 .10 .95 .10
                                        ^^^
                              answer towers above the rest

 one Grover round =  [ oracle ]  then  [ diffusion ]
   wires:  =====[ ORACLE ]=====[ DIFFUSION ]=====  (x ~ sqrt(N) times)
每一回合都把振幅注入答案,並從其餘項裡抽走。大約 sqrt(N) 回合之後,答案就佔據了主導——然後你進行測量。

平方級加速(sqrt N)

下面是誠實版的核心結論。古典的無結構搜尋大約需要 N 次預言機檢查;Grover 大約需要 sqrt(N) 次。這是一個平方級的加速——是平方根級,而不是指數級。對於 N = 1,000,000,古典做法大約要 1,000,000 次檢查,而 Grover 大約只要 1,000 次。這是真實而有用的,但與你可能聽過的那些被吹捧的指數級飛躍相去甚遠。

   N (items)      classical ~N      Grover ~sqrt(N)
  -----------    -------------     ----------------
      100              100                10
    10,000           10,000              100
 1,000,000        1,000,000            1,000
  10^12            10^12               10^6

  speedup factor = sqrt(N)   (e.g. N=10^12 -> 1,000,000x fewer checks)
Grover 把 N 變成 sqrt(N)。差距會隨著 N 增大而拉開,但它始終是一種平方根關係——絕不是像 [[shors-algorithm|Shor 演算法]]在因數分解上做到的那種 2^n -> n 的塌縮式壓縮。

有必要把話講明白:量子電腦並不是一顆能把你現有程式碼跑得更快的 CPU。Grover 並不會並行地把全部 N 個答案都算一遍再收集起來。它是在許多輪裡透過干涉把答案的振幅逐步建立起來,而你在最後仍然只得到一個測量結果。這份加速完全來自需要更少的預言機呼叫次數——僅此而已。

它到底什麼時候有用

原則上,Grover 的適用面很廣:任何這樣的問題——你能認出一個有效答案,卻沒有比逐個試候選項更好的策略——在理論上都能獲得平方級的加速。暴力破解一個對稱金鑰、可滿足性(SAT)式的搜尋、在未排序的資料庫裡找出一條被標記的記錄——這些都符合無結構搜尋的模子。

而在實踐中,這些收益很容易被開銷吃掉。你必須把預言機建構成一個真實的、可逆的量子線路,而這個線路可能很昂貴——有時昂貴到 sqrt(N) 次代價高昂的量子步驟,反而輸給 N 次廉價的古典步驟。當今NISQ時代的硬體相干時間很短、量子閘也不完美,所以一次需要成千上萬次乾淨預言機呼叫的運行,在沒有我們尚不能大規模實現的糾錯的情況下,往往是力所不及的。

所以,請把 Grover 當作一把鋒利而專門的工具:它在無結構搜尋上有經過證明的平方級優勢,在同類中是最佳的,但它既不是萬能加速器,也不是指數級魔法的來源。準確地知道它在哪裡有用——以及在哪裡開銷會悄悄抵消掉這份收益——正是真正理解量子計算與只會複述其炒作之間的分水嶺。