提示：本文共有 5862 个字，阅读大概需要 12 分钟。
本文参加百家号 #科学了不起# 系列征文赛。
计算机科学中的一项新证明对量子力学和纯数学的研究人员也有意义1935年，阿尔伯特·爱因斯坦与鲍里斯·波多尔斯基和内森·罗森合作，试图解决量子物理学新定律揭示的一种可能性：两个粒子可以相互纠缠，或相互关联，甚至跨越遥远的距离。就在第二年，艾伦·图灵提出了第一个计算通论，并证明了存在一个计算机永远无法解决的问题。
这两种思想革新了各自的学科。他们之间似乎也没有任何关系。但现在，一个里程碑式的证明将它们结合在一起，解决了计算机科学、物理和数学领域的一系列开放问题。
新的证明建立了量子计算机，通过纠缠量子比特或量子位来计算，而不是经典的1和0，理论上可以用来验证大量问题的答案。纠缠和计算之间的对应关系让许多研究人员感到震惊。
“这完全是一个惊喜，”维也纳量子光学和量子信息研究所研究量子物理学的米格尔·纳瓦斯克说。该证明的共同作者开始确定一种验证计算问题答案的方法的极限。这种方法涉及到纠缠。通过发现这个极限，研究人员最终解决了另外两个几乎是“副产品”的问题：Tsirelson的物理问题，关于如何建立数学模型的纠缠，以及一个与之相关的纯数学问题，叫做康涅狄格州嵌入猜想。
最后，结果就像多米诺骨牌一样连锁反应了。
不可判定的问题
在计算机真正出现之前，图灵定义了一个计算的基本框架。与此同时，他还指出了一个计算机无法解决的问题。它与一个程序是否停止有关。
通常，计算机程序接收输入并产生输出。但有时他们会陷入无限的循环中。当这种情况发生在家里时，就只剩下一件事要做了。手动关闭程序。把它剪了吧。”袁说
图灵证明了没有通用的算法可以决定一个计算机程序是停止还是永远运行。必须运行程序才能找到答案。
计算机科学家最终解决了数学和量子物理中的主要问题。从技术上讲，图灵证明了这个停机问题是无法确定的——即使是最强大的计算机也无法解决它。图灵之后，计算机科学家开始根据其他问题的难度来分类。更难的问题需要更多的计算资源来解决——更多的运行时间，更多的内存。这是计算复杂度的研究。最终，每个问题都会引出两个大问题:“解决起来有多难?”以及“验证答案是否正确有多难?”
当问题相对简单时，你可以自己检查答案。但当问题变得更复杂时，即使是检查答案也可能是一项艰巨的任务。然而，在1985年，计算机科学家们意识到，即使你自己不能确认一个答案是否正确，也可以培养信心。
该方法遵循警方讯问的逻辑。
如果一个嫌疑犯讲了一个精心设计的故事，也许你不能到外面去证实每一个细节。但是通过问正确的问题，你可以在谎言中抓住漏洞，或者建立起故事被证实的信心。
在计算机科学术语中，审讯中的双方是一台强大的计算机，它为一个问题提出一个解决方案和一台不太强大的计算机，它想向验证者提问，以确定答案是否正确。这第二台计算机称为验证器。
举个简单的例子，假设你是色盲，而另一个人——证明者——声称两颗弹珠是不同的颜色。你不能自己去核实这个说法，但通过巧妙的询问，你仍然可以确定它是否正确。
然后让验证者告诉你哪个是哪个。如果它们真的是不同的颜色，验证者每次都应该正确地回答这个问题。如果弹珠实际上是同一种颜色，也就是说它们看起来是一样的，验证者有一半的几率猜错。通过提出验证性问题，您可以验证比您自己更广泛的问题的解决方案。
1988年，计算机科学家们考虑了两个验证者对同一个问题提出解决方案时会发生什么。毕竟，如果你有两个嫌疑人要审问，那么破案或验证解决方案就更容易了，因为你可以让他们互相竞争。
“这给了验证者更多的筹码。你相关的问题，反复核对答案。”如果嫌疑人说的是真话，他们的反应大部分时间应该一致。如果他们在撒谎，答案会更经常地发生冲突。
类似地，研究人员表明，通过分别询问两个验证者关于他们的答案，你可以很快地验证一个更大的问题的解决方案，这比你只有一个验证者要问的问题要大得多。
计算复杂性似乎完全是理论上的，但它也与现实世界紧密相连。计算机解决和验证问题所需的资源——时间和内存——基本上是物理的。因此，物理学的新发现可以改变计算复杂度。
如果你选择一套不同的物理，比如量子而不是经典，你就会得到一个不同的复杂性理论。新的证明是21世纪计算机科学家面对20世纪物理学中最奇怪的概念之一：纠缠的最终结果。
连接嵌入猜想
当两个粒子纠缠在一起时，它们实际上并不相互影响——它们之间没有因果关系。爱因斯坦和他的合著者在1935年的论文中详细阐述了这一观点。之后，物理学家和数学家试图用数学方法来描述纠缠的真正含义。
然而，结果却有点混乱。科学家们提出了两种不同的纠缠数学模型，但并不清楚它们是否相等。
以一种迂回的方式，这种潜在的不协调最终产生了一个重要的纯数学问题，叫做“内嵌猜想”。最终，它也成为了五个计算机科学家在他们的新证据中利用的漏洞。
第一种建模缠结的方法是把粒子看作是在空间上彼此隔离的。一个在地球上，另一个在火星上，他们之间的距离阻碍了因果关系。这叫做张量积模型。
但在某些情况下，当两种物质因果分离时，就不那么明显了。所以数学家们想出了第二种，更一般的方法来描述因果独立。
当您执行两个操作的顺序不影响结果时，操作“交换”:3×2与2×3相同。在第二个模型中，当粒子的属性相互关联，但测量的顺序并不重要时，粒子就会被纠缠：测量粒子A来预测粒子B的动量，反之亦然。不管怎样，你得到的答案都是一样的。这被称为纠缠的交换算子模型。
这两种对纠缠的描述都使用了被称为矩阵的行和列组成的数字数组。张量积模型使用具有有限行数和列数的矩阵。交换运算符模型使用一个更一般的对象，它的功能类似于具有无限行和列的矩阵。
随着时间的推移，数学家们开始把这些矩阵作为他们自己感兴趣的对象来研究，完全与物理世界无关。作为这项工作的一部分，一位名叫阿兰·康尼斯的数学家在1976年推测，用有限维矩阵来近似许多无限维矩阵是可能的。这是嵌入推测的一个推论。
在接下来的十年里，一位名叫鲍里斯·齐瑞森的物理学家提出了这个问题的另一个版本，再次将其建立在物理学的基础上。Tsirelson推测，张量积和交换算符的纠缠态模型大致相等。这是有道理的，因为从理论上讲，它们是描述同一物理现象的两种不同方式。
然而，这两个问题的解决方案最终完全来自第三位。
20世纪60年代，一位名叫约翰·贝尔的物理学家提出了一项测试，以确定纠缠态是否是一种真实的物理现象，而不仅仅是一种理论概念。测试涉及一种游戏，其结果揭示了是否有比普通的非量子物理更重要的东西在起作用。
计算机科学家后来意识到，这种关于纠缠的测试也可以用来验证非常复杂问题的答案。
但是首先，为了了解游戏是如何工作的，让我们想象两个玩家，爱丽丝和鲍勃，和一个3×3的网格。裁判给爱丽丝分配一行，并告诉她在每个方框中输入0或1，以便数字和为奇数。鲍勃得到一列，必须把它填满，这样它的和就是偶数。如果他们把相同的数字放在她的行和他的列重叠的地方，他们就赢了。他们不允许交流。
在正常情况下，他们最多能赢得89%的机会。但在量子环境下，它们可以做得更好。
想象一下，爱丽丝和鲍勃分开了一对纠缠的粒子。他们对各自的粒子进行测量，并使用结果来决定在每个方框中写1还是0。因为这些粒子被缠结在一起，它们的测量结果将会相互关联，这意味着它们的答案也会相互关联——这意味着它们可以100%地赢得比赛。
因此，如果你看到两个玩家以出乎意料的高概率赢得游戏，你就可以得出结论，他们利用的不是经典物理学的优势。这种钟型实验现在被称为“非局部”游戏，指的是玩家之间的分离。物理学家实际上是在实验室里进行的。
在分析任何游戏时，你可能想要知道玩家在非本地游戏中获胜的频率，前提是他们尽其所能。例如，使用单人纸牌游戏，你可以计算出一个玩得很好的人获胜的几率。
但在2016年，威廉·斯洛夫斯特拉证明，没有通用的算法来计算所有非本地游戏的准确最大获胜概率。因此，研究人员想知道，你能接近最大胜率吗？
计算机科学家利用描述纠缠态的两个模型找到了答案。一个使用张量积模型的算法在所有非局部博弈的近似最大获胜概率上建立一个下限或最小值。另一种算法使用交换运算符模型，建立一个上限。
这些算法运行时间越长，得到的答案就越精确。如果Tsirelson的预测是正确的，而且这两个模型确实是等价的，那么下限和上限就应该不断地挤压在一起，缩小到一个单一的数值上，以获得近似的最大胜率。
但如果Tsirelson的预测是错误的，而且这两个模型并不等价，“天花板和地板将永远是分开的。在他们的新工作中，五名研究人员使用这个问题——关于天花板和地板是否收敛，Tsirelson的问题是对的还是错的——来解决一个单独的问题，即什么时候可以验证一个计算问题的答案。
纠缠的援助
在21世纪初，计算机科学家们开始思考：如果你询问两个共享纠缠粒子的验证者，它如何改变你可以验证的问题范围？大多数人认为，纠缠是不利于验证的。毕竟，如果两名嫌疑人有某种方法来协调他们的答案，他们就更容易说出一个连贯的谎言。
但在过去的几年里，计算机科学家们意识到事实正好相反:通过询问共享纠缠粒子的验证者，你可以验证比没有纠缠时更大范围的问题。“纠缠是一种产生关联的方式，你认为这种关联可能有助于他们撒谎或欺骗，”维迪克说。“但事实上，你可以利用这一点。”
要了解如何解决这些问题，您首先需要掌握这些问题的几乎超凡脱俗的规模，您可以通过这个交互过程验证这些问题的解决方案。想象一个图形——一个由线(边)连接的点(顶点)的集合。你可能想知道是否可以用三种颜色来给顶点上色，这样通过边连接的顶点就不会有相同的颜色。如果可以，这个图是“三色的”。
如果你给一对纠缠的验证者一个非常大的图形，他们报告说它可以是三色的，你会想:有办法验证他们的答案吗?
对于非常大的图形，不可能直接检查工作。相反，你可以让每个验证者告诉你两个相连顶点中的一个的颜色。如果他们每个人报告的颜色都不一样，而且每次你问他们的时候他们都是这么做的，你就会相信三种颜色真的有用。
但是，当图形变得非常大时，即使是这种询问策略也会失败——图上的边和顶点比宇宙中原子的数量还多。即使是陈述一个特定问题的任务(“告诉我XYZ顶点的颜色”)也超出了你这个验证者的能力:命名一个特定顶点所需的数据量超出了你的工作记忆。
但是纠缠使证明者自己提出问题成为可能验证者不需要计算问题。验证者迫使验证者为他们计算问题。验证者希望验证者报告连接顶点的颜色。如果顶点没有连接，那么问题的答案将不会说明图是否有三种颜色。
换句话说，验证者希望验证者问相关的问题:一个验证者问关于顶点ABC，另一个验证者问关于顶点XYZ。希望这两个顶点是相互连接的，即使验证者不知道另一个在考虑哪个顶点。(就像爱丽丝和鲍勃希望在同一个正方形中填入相同的数字一样，尽管他们都不知道对方被问到的是哪一行或哪一列。)
这些想法都来自同一时间。他们以这种戏剧性的方式重新走到一起，这很奇妙。如果两个验证者完全独立地提出这些问题，那么就没有办法强迫他们选择连接的或相关的顶点，从而允许验证者验证他们的答案。但这种相关性正是缠结所能实现的。
“我们将使用‘纠缠’来把几乎所有的东西都转移到‘证明者’身上。我们让他们自己选择问题。”在这个过程的最后，验证者报告一个颜色。验证者检查它们是否相同。如果图表真的是三色的，验证者不应该报告相同的颜色。
事实证明，这个验证过程是另一个非本地游戏的例子。如果他们让你相信他们的解决方案是正确的，他们就“赢了”。
在2012年，Vidick和Tsuyoshi Ito证明了使用纠缠验证器来验证至少相同数量问题的答案是可能的，你可以通过询问两台经典计算机来验证。也就是说，使用纠缠的验证器并不会妨碍验证。去年，Natarajan和Wright证明了与纠缠的验证者交互实际上扩展了可以验证的问题的类别。但是计算机科学家并不知道可以用这种方法验证的所有问题。直到现在。
一连串的后果
在他们的新论文中，五名计算机科学家证明，通过询问纠缠验证器，可以验证无法解决的问题的答案，包括停机问题。但停机问题是无法解决的。而这一事实正是最终证明的火花。
想象你把一个程序交给一对纠缠不清的验证者。你让他们告诉你它是否会停止。您准备通过一种非本地的游戏来验证他们的答案:验证者生成问题并基于他们的答案之间的协调来“赢”。
如果程序实际上停止了，验证者应该能够在100%的时间内赢得这个游戏——类似于如果一个图形实际上是三色的，纠缠的验证者不应该报告两个连接的顶点的相同颜色。如果它不停止，验证者应该只在50%的情况下偶然获胜。
这意味着，如果有人要求您为这个非本地游戏的特定实例确定近似的最大获胜概率，您首先需要解决停机问题。而解决停机问题是不可能的。这意味着计算非本地游戏的近似最大获胜概率是不可决定的，就像暂停问题一样。
这就意味着Tsirelson的问题的答案是否定的——这两种纠缠模型是不相等的。因为如果它们是，你可以同时捏住地板和天花板来计算一个近似的最大获胜概率。
马德里孔普卢腾斯大学的戴维佩雷斯-加西亚表示:“不可能有这样一个算法，因此这两个(模型)必须不同。”
新论文证明了类的问题可以通过与纠缠的量子相互作用来验证验证,一个类称为MIP *,正好等于类的问题没有比停止的问题,一个类称为再保险。论文的标题简洁地陈述它:“MIP * =再保险”。
在证明这两个复杂度等级相等的过程中，计算机科学家证明了Tsirelson的问题是错误的，由于之前的工作，这意味着Connes嵌入猜想也是错误的。
对于这些领域的研究人员来说，这些大问题的答案竟然来自于计算机科学中一个看似毫不相关的证明，这令人震惊。
量子物理学家和数学家才刚刚开始消化这个证明。在这项新工作之前，数学家们想知道他们是否可以用大的有限维矩阵来代替无限维矩阵的近似。现在，因为嵌入推测是假的，他们知道他们不能。
计算机科学家本身并没有打算回答Connes embedded猜想，因此，他们并不能很好地解释他们最终解决的一个问题的含义。
他和他的合著者预计数学家们将把这个新结果翻译成他们自己领域的语言。在一篇宣布证明的博文中，维迪克写道:我不怀疑最终将不需要复杂性理论来获得纯粹的数学结果。
然而，就在其他研究人员拿着证据进行研究的时候，导致这一研究停滞不前。三十多年来，计算机科学家们一直在试图弄清楚交互验证能让他们走多远。他们现在面对的是答案，是一篇很长的论文，标题很简单，图灵的回音。
看到此处说明本文对你还是有帮助的，关于“一个里程碑式的证明 解决了计算机 物理和数学领域的一系列问题”留言是大家的经验之谈相信也会对你有益，推荐继续阅读下面的相关内容，与本文相关度极高！
