另一个角度看量子计算：与弹球碰撞的惊人关联

选自acm.org

作者：Don Monroe

机器之心编译

编辑：Panda

从看似无关的主题中发现某种共同特质是件挺有意思的事，而且说不定会带来理解事物的新方式。本文探讨了著名量子算法 Grover 搜索算法与完全弹性碰撞这一问题之间的关联。

在科学和数学领域，许多看似无关的主题之间存在某些共同的特质。这样的相似性有时能同时为这两个领域带来重大的进展，不过很多时候这样的相似性只是单纯地很有趣。

去年 12 月，谷歌一位物理学家 Adam Brown 发现：一种基本量子计算算法与一种用于计算无理数 π 的奇妙方法之间存在一种异常精确的关系。「目前来说这个发现只是单纯很有意思，但我们希望找到思考事物的新方式，人们未来也许能使用这种方式寻找之前无法看到的联系。」Brown 说，「对于一个现象，多种思考角度是非常有用的。」

在网上发布的一篇预印本论文中（目前尚未完成同行评议），Brown 表明两个看似无关的问题之间存在某种数学上的相关性。其中一个问题是为量子计算机提出的著名的 Grover 搜索算法，理论上它比任何经典搜索算法都更快。另一个问题则是一个出人意料的过程：通过统计理想弹性球的碰撞次数来得到任意精度的 π 值。

量子算法

量子计算要用到量子比特，每个量子比特可以同时表示两个状态，而它们通常用离子或超导回路构建。从原理上看，一定数量的量子比特能表示和操作比经典比特多指数级数量的组合。之前，人们觉得利用这种概率性质来进行计算似乎是一场白日梦，但是研究者还是成功设计出了可从量子比特提取有用信息的算法。

第一个量子算法是彼得 秀尔（Peter Shor）1994 年提出的秀尔算法，当时他正在新泽西州的贝尔实验室工作。秀尔算法能高效地将整数分解为质因数，也由此给现今的许多加密方案带来了潜在的威胁。该算法的诀窍是将整数分解重构为一个新问题：确定一个序列的重复周期。这本质上是一种傅立叶变换，通过在量子比特的全集上使用全局运算就能找到这个序列。

第二个基本算法则是 Lov Grover 于 1996 年在贝尔实验室独立提出的 Grover 算法，它有着大不一样的工作方式。「秀尔算法和 Grover 算法是两种最典型的量子算法。」德克萨斯州大学奥斯汀分校的 Scott Aaronson 说，「即便在今天，我们所知的绝大部分量子算法都要么受秀尔算法启发，要么受 Grover 算法启发，要么同时受两者启发。」

Grover 算法通常被描述为一个数据库搜索过程，即检查一个包含 N 项的列表，找到其中满足所需性质的一项。如果该列表已按某种标签进行了排序（比如按字母顺序排列），那么通过不断连续减半地切分列表，就可以找到任意标签；这个过程所需的查询次数为 log N。但是，对于无序列表，检查完每一项平均需要 N/2 步（有可能需要多达 N 步）。

和其它量子算法一样，Grover 算法也会同时操作整个量子比特集，同时保留它们之间的关系（过早地查询任意量子比特会使其状态确定下来，从而将其转换成一个普通比特，这会消除量子计算所带来的优势）。但是，Grover 的研究表明：通常仅需次全局操作就能找到所需的项。

这样的提升没有秀尔算法所带来的提升多，因为秀尔算法带来的是指数级的提升。但 Brown 强调说：Grover 算法可应用于更一般的、非结构化的问题。

Grover 算法的计算首先是对所有 N 个量子比特进行均等混合。然后，该算法会反复让所有量子比特进行两种轮流交替的操作。第一个操作是嵌入该目标：它会反转一个特定但未知的比特的状态。该任务的目标是确定哪个比特被修改了，但方法不是观测所有比特。第二个操作不需要有关该目标的任何信息。Grover 发现每次重复该序列时，该目标在混合结构中的权重都会增大（尽管这无法被观测到）。重复了适当的次数之后，此时执行一次观测，则有非常高的可能性能得到正确结果。

弹性球

这些复杂的量子操作似乎和弹性球没有关系。但是，Brown 在研究与 Grover 算法相关的问题时看到了数学科普者 Grant Sanderson 做的一个动画，让他注意到了两者之间的相似性。Brown 在自己的论文中表明这两个问题之间存在一种精准的映射关系。

Sanderson 的动画解释了东伊利诺伊大学数学家 Gregory Galperin 在 2003 年描述的一个出人意料的观察结果。在论文《Playing Pool with π》中，他想象有两个能在水平面上无摩擦地运动的理想弹性球，它们能彼此以及与左侧的墙发生完全弹性碰撞（即总动能守恒）。

如果右侧的球向左撞向左侧更轻的静止球，则左侧小球会向左运动，同时右侧大球的速度并不会变慢多少。小球会在撞上墙后反弹，然后再次撞击大球，这个过程会重复很多次。最后，这样的碰撞会让大球调转方向，直到它最终以比小球更快的速度向右远去。

在此之前，碰撞的次数会随着大球与小球的质量比的增大而变多。如果两个球的质量相等，碰撞会发生 3 次：第一次右侧球会把所有运动转移给左侧球，左侧球则在撞墙后反弹，然后又通过碰撞将动量完全返还给右侧球。如果大球的质量是小球的 100 倍，则该过程会发生 31 次碰撞。如果这一质量比为 10000，则会有 314 次碰撞。根据计算（这个实验无法实际进行），质量比每增加 99 倍，碰撞的次数除以质量比的平方根后就能让 π 的数字表示多一位数：3.141592654...。

当 Brown 偶然看到 Sanderson 的动画（动画里使用的方块）时心里正想着 Grover 算法，然后他发现两者之间存在显著的相似性。举个例子，Grover 算法的两个量子操作可以分别对应于球球碰撞和球墙碰撞。质量比对应于数据库的大校此外，最终的结果是：操作数（或碰撞数）正比于 π 以及数据库规模（质量比）的平方根。（还有两个 2 的因数只是反映了两个问题的表记方法的差异）。

除了在这两种如此不同的系统之间存在惊人的联系之外，π 在这两种情况中究竟发挥了怎样的作用？当然，π 这个无理数最出名的地方是它是圆的周长与其直径的比，不过它也出现在椭圆以及球等更高维对象的对应比值中。定义球的方法之一是通过代数在横纵坐标 x 和 y 给出限定条件：半径为 r 的圆上的点满足限定条件：x + y = r 。

事实证明，不管是上面的碰撞问题，还是 Grover 算法，都具有这种形式的限定条件。球的碰撞或操作量子系统对应于由这些限定条件定义的圆上的旋转。

例如，对于两个质量为 m（速度为 v_m）和 M（速度为 v_M）的弹性球，弹性碰撞会保留两者的总动能。完全保留大球的动能需要在坐标 v_m 和 v_M 的平面中进行 180° 转向，而 180° 就等于 π 弧度。

类似地，在量子系统中，观察到某个特定结果的概率正比于对应该结果的「波函数」的平方。目标与其它所有结果的概率（振幅平方）之和必然为 1。

历史上的其它关联案例

也许有人要问：「这能针对世界的本质提供重要见解吗？还是说只能满足一点好奇心？」Brown 表示，「也许对 Grover 算法能为我们提供有关世界本质的重要知识，也许弹性球研究是为了满足好奇心，或许将它们联系起来的原因更多的是第二个，而不是第一个。」

尽管如此，有时候这样的联系还是能引出一些重大进展，在物理和数学历史中已有为数不少的案例。举个例子，物理学家已经投入了 20 多年时间探索强相互作用的多粒子量子系统与整合了高一个维度的弯曲时空的引力模型之间的惊人对应关系。甚至时空中的虫洞有望解答与量子力学中远距离粒子「纠缠」相关的悖论。

数学常常通过与不同领域之间的联系得到发展。例如，涉及一个简单方程的整数解的费马大定理直到几个世纪之后才得到证明，而使用的方法来自「椭圆曲线」。再举个例子，计算机科学家在一月份证明了一个与阿兰 图灵的可决定计算概念有关的定理，这又进一步给其它看似无关的领域带来了冲击。

在 Aaronson 看来，Grover 算法与弹性球之间的「这种对应关系尽管很精准，但可能也就是个有趣的类比（就是说我不知道如何使用这个关系来推导任何与 Grover 算法有关的未知性质）。但这样已经很好了。」

如何根据任务需求搭配恰当类型的数据库？

在AWS推出的白皮书《进入专用数据库时代》中，介绍了8种数据库类型：关系、键值、文档、内存中、关系图、时间序列、分类账、领域宽列，并逐一分析了每种类型的优势、挑战与主要使用案例。