有一天,我们的太阳将会膨胀、膨胀,直到变成现在大小 400 倍的红巨星,进而结束生命;有一天,人类将重返月球,而这次,我们将搭建新型空间站,从这里去往月球与火星……太空如此令人着迷,那里有行星、流星和星系,也有火箭、空间站和人造卫星,更有许多奇怪的现象,如光速和太阳耀斑!
作者:Grant Sanderson
翻译:曹昕宇
审校: Nuor
1. 滑块滑起来
右侧的滑块碰撞左侧的滑块,并将全部动量转移给左侧滑块,左侧滑块碰到墙反弹回来,再与右侧滑块发生碰撞并将动量全部转移过去。期间左侧滑块一共发生了三次碰撞。
如果我们增大右侧滑块的质量,会发现一些更有趣的事情。比如右侧滑块质量变成100 kg, 那每次碰撞时只会有一小部分动量发生转移,之前总共发生3次碰撞,现在则要发生31次。
要是右侧滑块质量变成10000 kg,那整个过程将发生314次碰撞。
不断地一百倍一百倍地增加右侧滑块质量,你会发现神奇的现象:总碰撞次数与π每一位的数字越来越接近。
格雷戈里·加尔佩林(Gregory Galperin)是东伊利诺伊斯大学(Eastern Illinois University)的一位数学家,他首先注意到这一现象。在他2003年的研究成果中,他将滑块看做移动的点,点的x坐标表示其中一个滑块的位置,y坐标表示另一个滑块的位置。这个点在xy平面的运动与一个半圆相关,因此会引入π的特征。
这是一个极为引人注目的成果,虽然它讨论的是理想状况。然而在数学中,抛开现实世界的繁杂,揭示单纯的规律,往往能意外的关联到其它学科领域。
在去年(2019年)早些时候,我发布了关于以上加尔佩林研究成果的三个视频,亚当·布朗(Adam Brown)看到了这些视频。他是Google的研究员,同时是斯坦福大学的物理学家。在几个月后的一次会议上,他与我分享了他的观察结果。令他兴奋的是,如果用某种正确的方法来解释,描述滑块动力学中的数学与解释一种最著名的量子算法的数学是一致的。
2. 一种量子方法
这就把我们带入到问题的第二部分:量子搜索是如何进行的。
假设你有一长串未经过排序的名单,其中有一百万个名字。你想要找出其中一个人,唯一能用的方法就是一个个的检查,直到你找到。平均来说,你将检索五十万次。有时会多一些有时会少一些,但肯定是个漫长的过程。
计算机可以帮你处理这个问题,但是对于非常大的未排序列表,花费的时间也与列表大小成比例增长,至少对于经典计算机是这样的。但是在1996年,在贝尔实验室的格罗弗(Lov Grover)描述了量子计算机如何更快速地完成搜索 ,只需要不到一千步。一般来说,对于大小为N的列表,量子计算机需要用大概步。注意到随着N增长,量子计算机花费时间的增长远小于经典计算机。
这种高效的搜索是由于量子计算机能同时作用于列表中的每一个元素。然而,量子计算机也不仅仅只是同时处理经典计算机能处理的工作。
经典计算机类似于回答这个问题:列表中的第21个元素是我要找的名字吗?然后将这个过程推广到列表中所有的一百万个名字。非常直白,但是效率不高。
相比之下,格罗弗处理列表的算法一开始看上去很奇怪,但是最终被证明更为有效。在经典计算机中,你可以读出内存中的每一位。然而在量子计算的过程中,不确定性导致无法直接获得矢量中元素的具体值,而是列表中的每个位置都附加了概率信息。量子计算不是查找名字在哪个位置,而是当进行一次测量时,会根据概率返回一个随机的位(称为索引)。由于量子力学的影响,我们不是直接作用于概率,而是作用于概率幅,概率幅的平方对应着概率。
读取随机的索引有什么用呢?量子计算的艺术就是操纵这些概率列表,使之为我所用。在我们找名字的问题中,意味着要找出某种方法(格罗弗的算法就是在做这件事),让我们想要寻找的索引对应的概率接近1,其它所有索引对应的概率接近0。这样当你读取列表的时候,获得的索引将大概率是正在寻找的那个。
进行量子计算的工具包括可以对概率列表进行的操作。在数学中,这样的由数组成的列表可以看做矢量。矢量可以想象成坐标空间中的一个点,或者从原点指出来的箭头。
一个有两个元素的矢量可以画在二维空间中,如果是一百万个元素组成的矢量可以想象存在于一百万维的空间中。量子计算机对矢量的操作就像是对它们进行翻转和旋转,数学上这些操作可以看成是矩阵。
量子计算速度特别快,因为每一次操作都作用于概率矢量整体,而不是每次作用于其中每个元素。格罗弗发现了一种巧妙的方法,用一对交替的运算来处理给定的矢量,从而得到一个我们想要的概率矢量。值得注意的是,这个过程需要进行操作的总次数远小于列表的大小。
要是你难以在脑中刻画出这个过程,这很正常。这也是为何亚当·布朗如此兴奋能找到另一个数学谜题来表达这个抽象的矢量操作过程。
3. 潜在的关联
当布朗看到我介绍碰撞块如何计算圆周率的视频时,他正巧想起了格罗弗的算法,他发现了其中的联系。“如果你用全部的时间来思考量子搜索,就会发现所有的事都像量子搜索”, 布朗说,“幸运的是在这种情况下,它真的是量子搜索。”
加尔佩林的论文中用滑块的位置来指示点的xy坐标,然而为了与量子搜索关联起来,格罗弗用滑块的速度指示点的xy坐标。每当滑块碰撞,矢量就对应发生一次变换。例如当左侧滑块与墙碰撞时,它的速度变为原来的相反数,对应矢量的y坐标乘负一而x坐标不变,就像是沿着x轴翻转一样。
类似的,如果两个滑块碰撞,它们速度的改变看上去像矢量沿着另一个偏离x轴的方向翻转(译者注:可以从动量守恒中考虑这个问题)。这个过程不断重复,左侧滑块与墙碰撞,矢量沿x轴翻转,两个滑块碰撞,沿另一方向翻转。最终经过足够的碰撞,矢量的轨迹填满了一个圆形。
布朗观察到如果建立合适的框架,这两个往复的运动正如格罗弗在他的量子搜索算法中用到的两个操作。
为了进一步理解,可以将右侧的大滑块想成很多1 kg的滑块粘在一起。然后不是用二维矢量描述速度,而是用N维矢量描述速度。N是所有滑块总数,包括左边单独的那一块。每个滑块对应未排序名单上的一个名字,左边单独的滑块对应我们想找出的目标。
在布朗的论文中,他证明了碰撞过程导致矢量的改变完全对应格罗弗算法中改变未排序名单的量子矢量。在碰撞问题中,右侧的大滑块速度方向即将改变的时候它动能最低,能量几乎都集中在小滑块上,正对应格罗弗算法中几乎所有的概率都集中在我们想找到的目标上。
我们计数碰撞次数时出现了π,这对应着格罗弗算法的时间复杂度。平方根的出现也正暗合每当大滑块质量乘100倍,碰撞次数会多出现在10进制下π的一位数字。
“当前这更像一种由于好奇引发的探索,”布朗说。“但是在物理学中,我们认识到我们思考问题的途径越多,洞察到的就越多,有朝一日这将变得有用。我们没有很多其它好方法来将格罗弗的算法可视化。”
这种不同领域的关联性,深刻展现了通用的数学语言的魅力。用矢量来表示物理系统的状态,在宏观的滑块碰撞与在微观的量子态中同样有用。数学中的许多基本思想,初看起来与现实脱节令人失望,但事实证明是强大的工具,因为在某个领域内剔除物理细节可以揭示与另一领域隐藏的关联。
本文经授权转自《中科院物理所》微信公众号