文章总结： Grover搜索算法是量子计算中解决无结构搜索问题的核心算法，通过相位标记和幅度放大机制实现平方根级加速。该算法利用相位Oracle标记目标态后，通过扩散算子进行关于均值的反射操作，在二维平面内将量子态旋转至目标方向。关键发现包括算法最优迭代次数约为√N次，过度迭代会导致概率下降。在密码学领域，该算法可将128位密钥的暴力破解查询次数从2^128降至2^64量级，但实际应用需考虑电路实现成本。 综合评分： 85 文章分类： 技术标准,解决方案,其他

---

【量子计算】Grover 搜索算法：从随机命中到幅度放大

原创

Litt1eQ Litt1eQ

Coder小Q

2026年5月6日 08:30 山东

在小说阅读器读本章

去阅读

【量子计算】Grover 搜索算法：从随机命中到幅度放大

上一篇的 Simon 算法告诉我们，量子算法的优势不只来自“同时看很多输入”，而是来自对叠加、相位和干涉的精确控制。这一篇我们换一个问题：如果函数没有 Simon 那样的隐藏周期，也没有 Deutsch-Jozsa 那样的全局结构，只是单纯在  个候选项里藏了一个目标，量子计算还能做什么？答案就是 Grover 搜索算法。[1][2][3]

Grover 算法的重要性，恰恰在于它面对的是最“朴素”的搜索问题。你只知道有一个目标，但不知道它在哪里；每问一次 Oracle，只能得到“是不是它”这一位信息。经典算法在这种无结构搜索（unstructured search）里，查询复杂度是 ；Grover 则把它降到了 。[1][2][3]

这不是指数级加速，但它有两层意义。第一，它适用范围极广。只要一个问题最后可以写成“给定候选答案，检查它是否正确”，Grover 的思路就可能介入。第二，它的机制与前面的算法完全不同。Simon 依赖的是“测出与秘密串正交的线索”，Grover 依赖的则是幅度放大（amplitude amplification）：先用 Oracle 给目标态打上相位标记，再用一次精心设计的干涉，把目标概率幅一点点推高。[2][5]

如果你读完整篇后只记住一句话，那应该是：

❝

Grover 算法不是直接把答案“并行试出来”，而是把目标态的概率幅在一个二维平面里一次次旋转到最大。

0. 引子：大海捞针为什么会有平方根加速

先看一个不带量子力学的版本。你面前有很多个完全一样的盒子，其中恰好一个盒子里有钻石。你唯一能做的事，就是选一个盒子问一句：“这里面是不是目标？”如果答案是否定的，这个信息只说明“这个盒子不是”，并不会给其他盒子带来任何额外结构。没有排序，没有梯度，没有“越靠近越热”的提示，这就是无结构搜索。

在这种承诺“恰好一个目标”的查询模型里，经典算法最坏要问到第  次才能推出最后一个就是目标；平均查询次数则约为 。如果把这个平均值写得更精确一些，它是

对大  的确就是  量级。比如  时，经典平均查询次数是  次；而 Grover 只要 1 次 Oracle 查询就能把成功概率推到 100%。[1][2]

把数量级写成表格，会更有感觉：

| 搜索空间大小 | 经典查询次数 | Grover 查询次数 | | — | — | — | | | 平均 | | | | 平均约 | 约 | | | 平均约 | 约 | | | 约 | 约 |

最后这一行，就是密码学里反复出现 Grover 的原因。它常被概括成一句话：在理想的查询模型里，128 位对称密钥的穷举搜索，会被 Grover 压到大约  次量子查询。不过这句话只是“理想上界”而不是“现实马上如此”，后面我们会回到这个问题。

1. 先把问题说准确：Grover 到底在搜索什么

Grover 处理的问题可以写成下面这个函数问题：

并且承诺恰好存在一个输入 ，使得

当

这里的  就是我们想找的目标输入， 是输入位数，搜索空间大小是

例如当  时，一共有四个候选态 。如果目标是 ，那么函数表就是：

| 输入 | | | — | — | | | | | | | | | | | | |

这里“无结构”的意思非常重要。它不是说“函数看起来乱”，而是说除了判断某个候选输入是不是目标以外，Oracle 不给你任何别的规律。你不能像二分查找那样利用有序性，也不能像 Simon 那样利用输入之间的代数关系。对于经典算法来说，查询第 37 个候选项失败，对第 38 个候选项几乎没有帮助。这正是线性复杂度的根源。[1][2][3]

量子版本里，我们通常不直接使用“把  写到辅助寄存器里”的 Oracle，而是使用更适合干涉的相位 Oracle（phase oracle）：

它的意思非常简单：

• 当  时，，所以 ；
• 当  时，，所以 。

也就是说，Oracle 并不会立刻把目标概率变大，它只是把目标态的相位翻成负号。[1][2]

这一步和 4.2、4.3 里见过的相位反冲是一脉相承的：量子算法真正操纵的不是概率，而是概率幅的符号和相位。Grover 的第一步，也只是先把目标态“标记”出来。

❝

Grover 的 Oracle 不负责“找出答案”，它只负责把答案对应的那一项概率幅变成负号。

2. 先做一件错误的事：为什么不能直接测量均匀叠加

既然量子计算机能把所有输入放进叠加，最自然的想法就是：先制备均匀叠加，然后直接测量不就行了吗？

先把这个想法真的写出来。对初始态  施加 ，得到

这里的  是均匀叠加态（uniform superposition），意思是每个基态的概率幅都相同，都是 。因此一旦直接测量，测到任何一个输入的概率都是

特别地，测到真正目标  的概率也只是 。

这一步最容易暴露一个常见误解：“量子计算机同时试了所有答案，所以一次测量应该更容易命中目标。”问题恰恰在这里。叠加只意味着所有候选项都在态向量里出现了，不意味着你已经把目标挑出来了。如果没有进一步干涉，测量只会随机坍缩成其中某一项，和“在所有候选项里随便抽一个”没有本质区别。[1][2]

所以 Grover 的关键不是“把所有输入都放进去”，因为这一点光靠 Hadamard 就做到了。真正困难的是：如何在不提前知道  的情况下，让目标项的概率幅逐步高于其他项。这就轮到 Grover 的第二个工具出场了。

3. 两个核心工具：相位标记与关于均值的反转

Grover 迭代由两个算子组成：

其中  是刚才的相位 Oracle，而

叫做扩散算子（diffusion operator），也常被叫做“关于均值的反转”。这两个名字里，后者更接近它在计算时的真实作用。

设当前量子态是

其中  是基态  的概率幅。记所有概率幅的平均值为

那么对任意一个分量，扩散算子的效果都是

这个公式值得慢慢看一眼。它的意思是：每个概率幅都绕着均值  做镜像反射。

• 如果某一项原来高于均值，它会被翻到均值下方；
• 如果某一项原来低于均值，它会被翻到均值上方；
• 离均值越远，翻过去之后离均值也越远。

这就解释了为什么 Oracle 要先把目标项变成负号。因为在均匀叠加态里，所有概率幅本来都一样，扩散算子什么都做不了。只有先让目标项掉到均值以下，扩散算子才有“把它翻到均值之上”的空间。

拿  的最小例子看最清楚。Oracle 之后，如果目标是 ，状态变成

这时四个概率幅分别是

它们的均值是

于是扩散后：

• 三个非目标项：；
• 目标项：。

所以一次扩散之后，状态直接变成了

这就是 Grover 在  时“一步到位”的原因。[1][2]

从电路角度看，扩散算子还可以拆成

这说明它本质上是：先把“均匀叠加方向”转回  方向，做一次相位反射，再转回来。也就是说，Grover 不是凭空多出一个神秘门，而是在重复使用前面章节里已经很熟悉的 Hadamard 和相位翻转。[2]

4. 真正的直觉：为什么整个算法只在二维平面里转动

上面的“关于均值反转”已经能算数值了，但还没有说明它为什么会稳定地一次次逼近目标。Grover 最关键的直觉，是它虽然运行在  维空间里，实际运动却始终被限制在一个二维平面内。[2]

我们把目标态记作 。再引入一个新符号：

这里的  表示“所有非目标态的等权叠加”。因为它只由非目标基态组成，所以与  正交：

初始均匀叠加态  就可以写成

如果把它改写成三角形式，就是

其中角度  满足

这个角度的物理含义很直接：初始态在目标方向上的投影只有 ，所以当  很大时，初始态离目标方向非常远。比如：

| | | （弧度） | 初始目标概率 | | — | — | — | — | | | | | | | | | | | | | | | | | | | | |

接下来两步就有了极其清楚的几何解释。

第一步，Oracle  把  分量取反，而  分量保持不变。因此在  这个平面里，它等价于“关于  轴的反射”。

第二步，扩散算子 ，则等价于“关于  这条轴的反射”。

而平面几何里一个很基本的结论是：

❝

先关于一条轴反射，再关于另一条轴反射，整体效果就是一次旋转；旋转角等于两条轴夹角的两倍。

在这里，两条反射轴分别是  和 ，它们夹角正好是 。因此每做一次 Grover 迭代 ，量子态就朝着目标方向旋转 。于是：

注意这个式子里， 对应的就是初始态 ；它与  的夹角本来就是 。每迭代一次，角度就再加 。所以测到目标的概率就是

这时 Grover 的主线就完全清楚了：Oracle 不是“告诉你答案”，扩散算子也不是“凭空放大概率”，两者合起来做的，是把态向量一点点旋到  那个方向上。

❝

Grover 迭代的本质是两次反射合成的一次旋转，而不是某种直接修改概率的黑箱操作。

5. 把最小例子完整算一遍： 为什么一步就成功

抽象公式已经有了，现在把最小非平凡例子从头到尾算一遍。设有两个量子比特，目标态是

5.1 初始化与均匀叠加

初始态是

施加  之后得到

这时四个基态的概率都等于 ，目标态  的测量概率只是 25%。

5.2 Oracle 只改相位，不改概率

施加相位 Oracle 后：

你会发现，目标态的符号变了，但模平方没有变，因此四个结果的测量概率仍然都是 25%。这一步再次说明：Oracle 本身不负责提高成功概率，它只是留下了一道相位痕迹，等待下一步干涉来利用。

5.3 扩散算子把“低于均值的目标项”翻到最高

Oracle 后四个概率幅是

平均值是 。应用公式 ：

| 基态 | Oracle 后的概率幅 | 扩散后的概率幅 | | — | — | — | | | | | | | | | | | | | | | | |

因此

最后一测量，必定得到目标态。

把整条演化线放在一起看，就更直观了：

| 步骤 | 状态向量 | 目标概率 | | — | — | — | | 初始 | | | | 后 | | | | Oracle 后 | | | | 扩散后 | | |

为什么这个例子如此“完美”？因为当  时，

而每次 Grover 迭代会旋转 。初始态与目标方向相差 ，所以刚好一次就转到位。

这不是一般情况，但它把 Grover 的机制揭示得非常干净：相位标记留下“谁该被放大”的信息，扩散算子再把这条信息翻译成概率幅的重新分配。

6. 一般情形：迭代多少次最合适，为什么会“过冲”

由前面的二维旋转公式，

所以要让成功概率最大，就希望

解出来得到

当  很大时， 很小，此时 ，于是

从而

这就是 Grover 最常出现的公式。更准确地说，真正执行时要取离这个值最近的整数，而不是机械地下取整；因为 Grover 不是“越做越好”，做过头反而会掉下来。

例如  时，

这时各次迭代的成功概率是：

| 迭代次数 | 成功概率 | | — | — | | | | | | | | | | | | |

可以看到，做到第 2 次已经接近峰值；再做第 3 次，概率反而大幅下降。这就是所谓的“过冲”。它并不神秘，因为 Grover 的本质就是旋转：既然会朝着目标方向靠近，当然也会在转过头以后离开目标方向。

更大一点的规模，趋势更清楚：

| | 最优迭代次数（最近整数） | 成功概率 | | — | — | — | | | | | | | | | | | | | | | | | | | | |

这也解释了一个经常被忽略的前提：Grover 通常假设你至少大致知道搜索空间大小，或者知道被标记解的数量级。否则，你就不知道该停在什么位置。如果有  个目标而不是 1 个目标，上面的角度关系会变成

于是最优迭代次数相应变为大约

这正是幅度放大的一般形式。[2]

❝

Grover 的查询次数不是”做得越多越好”，而是”把态旋到最接近目标方向的位置就停下”。

7. 为什么这已经是极限，以及它对密码学到底意味着什么

Grover 的另一个关键事实是：对无结构搜索来说，它已经达到查询复杂度意义下的最佳量级。换句话说，不存在一个更聪明的量子算法，把  再压成  或多项式级别。Bennett、Bernstein、Brassard、Vazirani 在 1997 年给出了无结构搜索的量子下界，因此 Grover 的平方根加速在量级上已经是最优的。[4]

这件事有两个直接后果。

第一，Grover 很强，但它并不能把 NP 完全问题一口气变成多项式时间。假如一个问题最朴素的暴力搜索空间是 ，那么 Grover 最多也只是把它降到

这仍然是指数时间。指数的底数变小了很多，但“指数”这个性质并没有消失。

第二，Grover 对密码学的影响主要落在对称密码和哈希函数上，因为这些系统常常可以抽象成“给定候选密钥或候选输入，检查它是否正确”的搜索问题。于是人们才会说：在理想查询模型里，Grover 会把 AES-128 的穷举搜索从约  压到约  次量子查询。

但这里一定要加上限定语。这个结论说的是理论上的查询复杂度缩放，并不等同于现实系统里的实际攻击成本；真正实现 Grover 还要考虑 Oracle 构造、电路深度和容错开销等额外代价。

这也是为什么更准确的说法应该是：

• 在查询复杂度模型里，Grover 给出平方根加速；
• 在现实工程里，Oracle 构造成本、纠错开销、串行深度和并行受限都会显著抬高代价；
• 所以“量子计算机会立刻把所有对称密码打穿”是错误的；
• 但对需要长期安全边际的系统来说，采用更长的对称密钥依然是稳妥策略。

因此，更稳妥的表述应当是：Grover 改写了理想模型里的穷举搜索上界，但它并不等于现实世界里可以无成本地把对称密钥强度直接“开平方”。

所以，这一章真正教给我们的不是一句口号，而是一种更准确的判断方式：Grover 确实改变了“无结构穷举”的理论上界，但它既不是“所有问题都能平方根加速”，也不是“量子来了，所有密码立刻失效”。

小结

现在把整篇文章压回量子计算的语言，可以得到一条很清楚的主线：

1. 先用  把所有候选输入放入均匀叠加。
2. 再用相位 Oracle 给目标态打上负号。
3. 扩散算子读取这道相位痕迹，把目标项从“低于均值”翻到“高于均值”。
4. 这两个反射合起来，在  的二维平面里形成一次旋转。
5. 重复大约  次后，量子态就被旋到最靠近目标态的方向。

所以 Grover 算法最值得反复记住的一句总结是：

❝

在无结构搜索里，量子优势来自“相位标记 + 干涉旋转”的幅度放大，而不是来自把所有答案并行试一遍。

这条思路和前面的 Simon 算法很不一样。Simon 是“每次得到一条线性约束，再用经典后处理拼出秘密串”；Grover 是“每次只朝答案方向再旋一点点”。但它们共同说明了一件事：量子算法之所以能快，不是因为量子态里“装得下很多候选项”，而是因为我们能控制这些候选项之间怎样相长、怎样相消。

这一篇里，我们已经多次把 Hadamard 看成一种“把某个方向旋到另一个方向”的变换。下一篇的量子傅里叶变换会把这个思想推进得更远：它不只是粗略地制造均匀叠加，而是把不同基态的相位结构精确地编码出来。Grover 让我们看到了“相位怎样变成概率”，QFT 则会进一步展示“相位怎样直接承载答案结构”。

参考资料

1. Chris Bernhardt, Quantum Computing for Everyone. The MIT Press, 2019.
2. Robert S. Sutor, Dancing with Qubits: How Quantum Computing Works and How It Can Change the World. Packt, 2019.
3. Lov K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212-219 (1996). https://doi.org/10.1145/237814.237866
4. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani, “Strengths and Weaknesses of Quantum Computing,” SIAM Journal on Computing 26(5), 1510-1523 (1997). https://doi.org/10.1137/S0097539796300933

---

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：Coder小Q Litt1eQ Litt1eQ《【量子计算】Grover 搜索算法：从随机命中到幅度放大》