格罗弗算法：量子搜索
“量子”课程第 11 课，共 23 课。免费，有动画和小测验。
盒子问题
你面前有 N 个盒子，礼物在其中一个里。没有提示：打开、看、关上。平均要开一半，最坏要全开。量子版本：我们有一个“预言机”，就是能回答“是不是这个盒子”的电路。1996 年，贝尔实验室的洛夫·格罗弗展示了怎样用大约 √N 次提问找到礼物。一百万个盒子，大约问 800 次，而不是五十万次。
原理：标记加翻转
先用 H 门让所有盒子的振幅一样高。第一步：预言机给正确盒子的振幅加负号，就是配方里的“标记”。第二步：“绕平均值翻转”。因为有了负号，平均值稍微降了一点，然后把每个振幅都绕着平均值翻过去。普通盒子变矮一点，那个负的却一下子跳得很高。重复“标记 + 翻转”，正确的盒子一次比一次高。
关键是适时停下
一个不太直观的细节：格罗弗算法不是“越久越好”。正确盒子的振幅像一支转动的箭头那样增长。64 个盒子大约 6 步后概率接近 100%，再继续，箭头就转过头了，概率开始下降。所以步数要提前算好：大约 π/4 · √N。如果不知道有几个礼物，也有巧妙的变体算法，不过那就是细节了。
格罗弗与加密
猜密码密钥，本质上就是在海量盒子里找一个。AES-128 有 2 的 128 次方种可能。格罗弗开个根号，剩 2 的 64 次方步，也就是“128 位”安全变成“64 位”。实际上这依然很多：格罗弗的步骤必须一步接一步地做，没法像普通暴力破解那样轻松分到上千台机器上。不过解决办法很简单，而且已经在用：AES-256 被格罗弗打折后还剩 128 位。
速度极限
会不会有人发明更快的搜索？不会：1997 年，本内特、伯恩斯坦、布拉萨尔和瓦齐拉尼四位研究者证明，对“盲目”搜索来说，√N 是任何量子计算机的极限。由此得出一个重要结论：很多难题，比如最优配送路线，本质上就是在试各种可能。量子计算机最多把它们加速到根号级，而不是瞬间解决。至今没人为这类问题找到指数级加速。
格罗弗真正有用的地方
听起来像“量子版谷歌”，但对普通数据库搜索来说，格罗弗几乎没用。要问预言机，得先把数据装进量子存储器，光这一步就要 N 量级的步骤，优势全被吃掉。真正有用的场景是“盒子”不是存出来的，而是用公式算出来的：猜密钥、验证答案、作为更复杂算法的子程序。而且这些都需要带纠错的大型量子计算机。
自测一下
- 10,000 个选项大约要格罗弗多少步？
正确答案: 大约 80. √10,000 = 100，π/4 · 100 ≈ 79。是平方级加速，不是瞬间。 - 朋友“为了保险”把格罗弗步数多做了三倍，会怎样？
正确答案: 概率下降：箭头转过了答案. 格罗弗是一种旋转。过了最佳点，正确盒子的振幅又会变小。 - 因为格罗弗，AES-256 需要紧急更换吗？
正确答案: 不用：被格罗弗打折后还有 128 位. 格罗弗把位数砍半，而 128 位被认为是安全的。所以长期推荐用 AES-256。