Get best of the week

π如何结合碰撞块和量子搜索算法

一位好奇的物理学家发现了碰撞块理论与著名的量子搜索算法之间的意外联系




π的数字，碰撞块和量子搜索算法有什么共同点？超出您的想象。-这种连接是由两个幽默的科学著作提供了一个从2003年，和第二，他们结合在一起的动态，几何形状和量子计算，呈现最抽象的数学难题，怎么连可以令人惊奇揭示物理学连接的世界，从2019年12月合约。

锁


要开始理解这些连接，请想象两个金属块，每个金属块重1公斤。它们位于固定壁右侧无摩擦的表面上。最靠近墙的砌块静止不动，第二块滑向墙，向右滑动。不可避免地会发生一系列冲突。假设动能在碰撞中不会消失。在如此理想的条件下，此过程将如下进行：


右边的方块碰到了左边，给了它全部的冲动。左侧的挡块从墙上弹起，返回右侧以再次碰撞并完成一次完整的脉冲传输。

但是，如果增加正确块的质量，情况将变得更加有趣。如果重100公斤，则每次碰撞只会将其动量的一小部分传递到较小的方块，而不是碰撞次数会从3增加到31。


质量比为10,000比1，将在314次碰撞后解决。


通过将质量乘以100来增加差值，您将能够观察到一个令人震惊的趋势：碰撞数将开始越来越接近π数。


东伊利诺伊大学的数学家格里高利·加珀林（Gregory Galperin）最早注意到这一现象[于1993年]。在2003年，他通过可视化块在一个移动点上的运动来对其进行解释，该点的x坐标表示一个块的位置，第二个块的y坐标。平面上一点的轨迹与一个半圆相连，因此出现π。

即使这些理想条件使它看起来毫无用处，但效果仍非凡。但是，如果您忽略了数学的真实世界，您会发现纯粹的规律性揭示了与其他科学领域的意想不到的联系。

在2019年，我发布了一组三个视频解释了哈珀林的结果，并且在观察结果的人中有亚当·布朗（Adam Brown），他是Google的研究员，也是斯坦福大学的物理学家。在会议上待了几个月后，他带我出去分享他的观察。令他高兴的是，他发现从某些角度描述这些块动力学的数学与描述最著名的量子算法之一的数学相同。

量子方法


这将我们带到了难题的第二部分：量子搜索是如何工作的。

假设您有一长串的名称没有排序（例如，一百万），并且您需要找到一个特定的名称。除了检查一个名字，直到找到正确的名字，您别无选择。平均而言，将需要您进行一百万次迭代。有时更多，有时更少，但是在任何情况下都需要花费一些时间。

计算机可以为您执行此搜索，但是大型列表的问题在于处理它们所需的时间将与它们的大小成比例地增加。至少在使用经典计算机时。但是在1996年，在贝尔实验室工作的Love Grover 说量子计算机如何以不超过1000步的速度更快地执行此类搜索。通常情况下，量子计算机将以π/ 4√N步长处理长度为N的列表。请注意，随着数量N的增加，量子计算机的步数增长速度将比经典计算机慢。

这样的搜索效率是可能的，因为量子计算机会同时处理列表的所有元素。但是，他不仅在同一时间做经典计算机会做的事情。

一台经典的计算机回答了这个问题：“列表中的第21个元素是我需要的名称吗？”并针对列表的每个位置（从0到999,999）重复此操作，直接执行，但效果不佳。

但是格罗弗（Grover）的算法与列表方法配合使用，乍一看似乎很奇怪，但最后却更有用。经典计算机可以简单地从内存中读取位。量子计算中存在的不确定性导致您无法直接提取正在使用的向量的分量的事实。列表中的每个位置都有一个附加的概率结构。您无需查看此位置中的名称，而是可以测量整个列表，并根据概率获得一个随机位置-索引。由于具有基本的量子力学，因此我们不使用概率值，而是使用其平方对应于获得与您要查找的名称对应的索引的概率的数字。



如何读取随机索引会派上用场？量子计算的技巧是操纵一系列概率，这些概率为您带来优势。在我们的示例中，这意味着发明一种方法（这是格罗弗的算法所做的），以获取与您要查找的名称的索引相关联的数字，并使其接近于1，从而使所有其他数字均接近于零。然后，阅读此列表并接收索引作为响应，您可能会知道它与您要查找的名称相对应。

量子计算工具由研究人员可以应用于此概率列表的操作组成。在数学中，这样的列表称为向量。将向量想象成坐标系中的一个点，或者想象成一个从原点到该点的箭头，通常很方便。



可以在二维空间中将两个分量的矢量表示为箭头。具有1,000,000个成分的向量生活在1,000,000维的惊人空间中。量子计算机执行的操作类似于此箭头的旋转和翻转。在数值上，每个操作都由一个矩阵表示。



量子计算特别快，因为每个操作都是使用整个概率矢量执行的，并且不会逐项传递。Grover发现了一种通过一对间歇操作来操纵给定向量的棘手方法，从而得到了具有我们所需概率的向量。重要的是，所需的操作总数要远远小于列表的大小。

如果您很难想象这是如何工作的，那么您不是唯一的人。因此，亚当·布朗非常高兴地发现一种方法，以一种更易于理解的难题来想象这些抽象的向量操作。

隐藏链接


原来，当我观看有关使用碰撞块计算π的视频时，Brown只是想到了Grover的算法，因此他立即注意到了它们的联系。布朗说：“如果一整天都在考虑量子搜索，那么一切都会开始看起来像量子搜索。偶然地，这种情况最终与量子搜索有关。”

而且，如果加尔珀林（Galperin）在区块碰撞方面的工作使用了编码每个区块位置的空间，那么与格罗弗（Grover）量子搜索的联系就从一个向量开始，该向量的x和y分量编码了每个区块的速度。每次块冲突都会转换为对该向量的特定操作，从而更改其分量。例如，当左侧块与墙碰撞时，将方向更改为相反方向，这意味着向量的分量乘以-1，而分量x保持不变。从几何角度看，这看起来像是向量围绕x轴的反射。

同样，当两个块碰撞时，它们的速度变化类似于此向量的另一次翻转，仅偏离中心。当模拟继续时，左侧的块将再次与墙碰撞，这将导致x轴再次旋转。方块的另一次碰撞意味着另一次革命。结果，在发生足够多的碰撞时，矢量将填充熟悉的曲线：圆。


Brown指出，如果正确描述了这种情况，则这两个在一个方向或另一个方向上发生变化的操作与Grover在其量子搜索算法中使用的两个操作相同。

要了解这种情况是如何发生的，请想象一个大的右区块，以许多公斤的形式粘在一起。然后，代替描述每个速度的二维向量，我们得到一个N维向量，其中N是小块的总数，包括左侧的孤立块。每个小方块对应于未排序列表中的名称，左侧的单独方块对应于目标名称。

布朗在他的工作中证明，这些块碰撞改变描述它们的向量的方式与格罗弗算法改变表示未排序名称列表的量子向量的方式完全相同。碰撞块系统中的时刻，即大块将要转弯，并且系统的几乎所有能量都在小块中，对应于Grover算法中的时刻，此时几乎所有概率都以您需要查找的名义出现。

计数碰撞时出现π的事实反映在Grover算法中：π/ 4√N步。表达式中的平方根还反映了将大块的质量乘以10后π的数字计数（以10度为单位）的距离。

“到目前为止，这只是一个mm头，”布朗说。“但是在物理学中，我们了解到，我们对问题进行思考的方式越多，可以看到的想法就越多-因此我希望这一事实有一天能派上用场。” 我们几乎没有其他好的方法可以可视化Grover算法。

这些联系强调了数学通用语言的功能。使用矢量对物理系统的状态进行编码既可用于块的大规模碰撞，也可用于量子态的微尺度。乍一看似乎与现实相去甚远的许多数学基本概念，却被证明是功能强大的工具，因为如果您忽略某个区域的物理细节，就会发现它与另一区域的隐藏联系。

More articles:


All Articles