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

从看似无关的主题中发现某种共同特质是件挺有意思的事,而且说不定会带来理解事物的新方式。本文探讨了著名量子算法 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 算法有关的未知性质)。但这样已经很好了。」

原文链接:https://cacm.acm.org/news/247584-bouncing-balls-and-quantum-computing/fulltext

入门量子算子弹性碰撞Grover 搜索算法
相关数据
Peter Shor人物

麻省理工学院教授。研究兴趣:量子计算、量子信息论、算法、计算几何学、组合数学、概率论。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

重构技术

代码重构(英语:Code refactoring)指对软件代码做任何更动以增加可读性或者简化结构而不影响输出结果。 软件重构需要借助工具完成,重构工具能够修改代码同时修改所有引用该代码的地方。在极限编程的方法学中,重构需要单元测试来支持。

数据库技术

数据库,简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以对文件中的数据运行新增、截取、更新、删除等操作。 所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

动量技术

优化器的一种,是模拟物理里动量的概念,其在相关方向可以加速SGD,抑制振荡,从而加快收敛

量子计算技术

量子计算结合了过去半个世纪以来两个最大的技术变革:信息技术和量子力学。如果我们使用量子力学的规则替换二进制逻辑来计算,某些难以攻克的计算任务将得到解决。追求通用量子计算机的一个重要目标是确定当前经典计算机无法承载的最小复杂度的计算任务。该交叉点被称为「量子霸权」边界,是在通向更强大和有用的计算技术的关键一步。

量子力学技术

量子力学(Quantum Mechanics),为物理学理论,是研究物质世界微观粒子运动规律的物理学分支,主要研究原子、分子、凝聚态物质,以及原子核和基本粒子的结构、性质的基础理论。

推荐文章
暂无评论
暂无评论~