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 当作一把锋利而专门的工具:它在无结构搜索上有经过证明的平方级优势,在同类中是最优的,但它既不是万能加速器,也不是指数级魔法的来源。准确地知道它在哪里有用——以及在哪里开销会悄悄抵消掉这份收益——正是真正理解量子计算与只会复述其炒作之间的分水岭。