MIP * = RE：引起物理学和数学上的多米诺效应的计算机科学领域的划时代证据

计算机科学家在通过计算方法验证问题的解决方案方面已经达到了新的领域。同时，他们找到了有关量子力学和纯数学最重要的开放性问题的答案。

1935年，爱因斯坦与鲍里斯·波多尔斯基（Boris Podolsky）和内森·罗森（Nathan Rosen）合作，研究了新的量子物理学定律带来的可能性：两个粒子即使在很远的距离都不会违反它们的互连关系时也可能处于纠缠状态。 次年，艾伦·图灵（Alan Turing）制定了第一个通用计算理论，并证明存在计算机无法解决的问题。  这两个思想彻底改变了它们所涉及的科学领域。此外，似乎他们彼此之间没有任何关系。但是现在证明





MIP * = RE将它们结合起来，从而解决了计算机科学，物理学和数学领域的许多问题。

量子计算机使用纠缠的量子位（qubit）而不是经典的零和一执行计算。新证据表明，从理论上讲，这种计算机可用于测试众多问题的解决方案。量子纠缠与传统计算之间的联系对于许多研究人员来说是一个很大的惊喜。

MiguelNavascués是维也纳量子光学与量子信息研究所量子物理学的学生。他在评论证据时说：“这真是令人惊讶。”

证据的共同作者设定了定义验证计算问题解决方案方法边界的目标。这种方法涉及量子纠缠。发现了这些边界之后，研究人员开始解决另外两个问题，这几乎是他们工作的副产品。我们正在谈论有关量子纠缠的数学建模的物理学的Zirelson假设以及纯数学中的相关问题-冯·诺依曼代数理论中的Conn问题（Conn的嵌入问题）。

结果，在数学和物理学中应用证据的结果导致了类似多米诺效应。

“所有想法都属于同一时期。很高兴看到他们在这样一种壮观的方式再次走到一起，说：“ 袁子春），来自多伦多大学-证据的共同作者之一。除了他在这工作参加Chzhenfen姬（姬正丰）从悉尼科技，约翰·赖特（大学的约翰·赖特从得克萨斯大学奥斯汀分校），阿南德纳塔拉（阿南德纳塔拉）和托马斯·维迪奇（由托马斯Vidick来自加利福尼亚技术研究所）。所有五位科学家都在计算机科学领域工作。

无法解决的问题

图灵，甚至在计算机问世之前，就为计算的思考奠定了基础。他同时表明存在一个无法证明的计算机无法解决的问题。这就是所谓的关机问题。

通常，计算机程序会在输入处接收某些内容并生成输出。但是有时它们会陷入无休止的循环中，这意味着它们永远不会停止。发生这种情况时，只有一种方法可以摆脱这种情况。根据Henry Yuen的说法，您需要手动停止该程序。您只需要结束她的工作即可。

图灵证明，没有通用的算法能够确定程序是否将被停止。为了找出答案，您需要运行该程序。

袁子春，托马斯Widick，正风纪，阿南德纳塔拉，约翰赖特

“你等了一万年，但该计划并没有停止。也许您只需要等待200万年？滑铁卢大学的数学家威廉·斯洛夫斯特拉（ William Slofstra）说。

从技术角度来看，图灵证明了关闭问题是无法解决的。即使您能想象到的最强大的计算机也无法处理它。

图灵之后，计算机科学家开始根据其复杂性对其他任务进行分类。更复杂的任务需要更大的处理能力-更多的处理器时间和内存。这是对算法计算复杂度的研究。

结果，任何问题都会给研究人员带来两个大问题：“解决起来有多难？验证最终解决方案正确的困难是什么？”

通过审讯来审问决定

如果任务相对简单，则可以独立检查其解决方案。但是，当任务变得更加复杂时，甚至检查其解决方案的结果也将变得异常困难。尽管如此，1985年，计算机科学家决定，即使无法独自确认答案，也有可能建立对答案正确性的信心。

验证方法遵循警察审讯的逻辑。

如果犯罪嫌疑人讲出一个经过深思熟虑的故事，那么调查人员可能将无法简单地获取并确认其每个细节。但是，通过提出正确的问题，您既可以撒谎，也可以证实其故事的真实性。

在计算机科学方面，审讯的两个方面由两台计算机代表。第一个是功能强大的计算系统，可以为问题提供解决方案。他被称为证人。第二个不再是一种功能强大的设备，它会询问测试人员问题以确定他提供的答案是否正确。这台计算机称为验证程序。

考虑一个简单的例子。假设某人（验证者）患有色盲症。另一个人（目击者）声称这两个球被涂上了不同的颜色，并且彼此没有区别。验证者无法验证此语句本身。但是，在巧妙地进行了审讯之后，他仍然可以找出是否确实如此。

为此，您可以将球隐藏在背后并混合。然后-向证明者询问哪只球在哪只手中。如果它们确实不同，那么证明者应该始终正确回答这样的问题。但是，如果它们具有相同的颜色，即它们看起来完全相同，那么证明者的一半答案将被证明是错误的。

托马斯·维迪克（Thomas Widick）说，如果证明者的答案中有一半以上是正确的，那么您可以确信这些球具有不同的颜色。

通过向证明者提出问题，您可以验证比自己更广泛的问题的解决方案。

1988年，计算机科学家研究了一种情况，其中有两种证明可以为同一问题提供解决方案。最后，如果有两个犯罪嫌疑人可以接受讯问，这将简化对犯罪的披露，或者-对决定的核实，因为他们可能被迫相互竞争。

根据Thomas Widick的说法，这给验证者带来了更大的影响力。他审讯，询问相关问题，交叉核对答案。如果嫌疑人说的是实话，他们的答案在大多数情况下应该相互匹配。如果他们撒谎，他们的答案往往会有所不同。

同样，研究人员表明，通过分别询问两名证人，向他们询问所找到的解决方案的问题，与与一个证明人一起工作时，可以更快地验证甚至更大范围的问题的解决方案。

对算法的计算复杂性的研究似乎纯粹是理论上的，但它们与现实世界密切相关。计算机解决问题和验证解决方案所需的资源（时间和内存）是物理资源。因此，物理学中的新发现可能会改变计算复杂性研究的方法。

阿南德·纳塔拉让（Anand Natarajan）说，如果我们脱离经典的计算物理基础，选择完全不同的事物，例如量子机制，我们还将获得一种新的计算复杂性理论。

新证据是21世纪计算机科学家与上个世纪最奇怪的物理学思想之一-量子纠缠的碰撞的最终结果。

康恩的问题

实际上，当两个粒子纠缠在一起时，它们不会互相影响。他们的行动之间没有因果关系。爱因斯坦和他的合著者在1935年的一篇文章中致力于这一想法。随后，物理学家和数学家试图找到一种数学方法来描述量子纠缠的实际含义。

但是，这些努力导致了不同的结果。科学家们提出了两种不同的纠缠数学模型。但是，尚不清楚这些模型是否彼此等效。

这种潜在的不和谐以回旋的方式出现，导致出现了纯数学领域中的一个重要问题。这是冯·诺依曼代数理论中的康恩问题。最后，它起到了某种“线索”的作用，五位计算机科学家在得出证据时利用了这些线索。

量子纠缠建模的第一种方法是将粒子感知为空间上相互隔离的对象。假设其中一个粒子在地球上，另一个在火星上。它们之间的距离排除了它们之间的因果关系（因果关系是分开的）。这就是所谓的张量积模型。

但是在某些情况下，实体的因果分离并不完全明显。结果，数学家得出了描述因果独立性的第二种更通用的方法。

当执行两个操作的顺序不影响结果时，该操作称为可交换的：3x2与2x3相同。在第二个模型中，当粒子的属性相关时，它们会纠缠在一起，但是测量的顺序无关紧要。可以对粒子A进行测量，以预测粒子B的动量，反之亦然。无论如何，结果都是一样的。这被称为换向算子纠缠模型。

两种对纠缠的描述都使用称为矩阵的数字数组。矩阵由行和列组成。张量积模型使用行数和列数有限的矩阵。换流算子模型使用更多的通用对象，它们充当具有无限数量的行和列的矩阵。

随着时间的流逝，数学家开始将这些矩阵作为独立兴趣的对象进行研究，而不与物理世界有任何联系。根据这项工作，数学家Alain Connes在1976年提出，应该可以使用有限维矩阵来近似许多无限维矩阵。这是冯·诺依曼代数理论中Conn问题的后果之一。

在接下来的十年中，物理学家鲍里斯·齐雷尔森（Boris Tsirelson）提出了这个问题的新版本，并将其重新回到物理学领域。Zirelson建议张量积和通勤算子的模型彼此近似相等。这种说法是有道理的，因为从理论上讲，这两个模型都是描述同一物理现象的两种不同方式。随后的工作表明，由于矩阵和使用它们的物理模型之间的联系，所以Conn和Zirelson的问题是间接相关的：如果解决了一个问题，那么另一个将被解决。

但是，这两个问题的解决方案都出自一个完全出乎意料的地方。

游戏物理

在1960年代，物理学家约翰·贝尔（John Bell）进行了一项测试，以确定量子纠缠是否是真正的物理现象，而不是理论概念。该测试使用了类似游戏的东西，其结果使得有可能找出与普通物理学无关的某些机制在游戏中是否起作用。

后来，计算机科学家意识到与量子纠缠有关的测试也可以用作验证非常复杂问题的解决方案的工具。

但是在继续之前，让我们谈谈游戏。想象有两个球员：爱丽丝和鲍勃，还有一个3x3的比赛场地。演示者向Alice分配一行，并提示她在每个单元格中输入0或1，这样它们的总和将给出一个奇数。鲍勃（Bob）得到一列，需要用零和一填充，以使它们的和为偶数。如果将相同的数字放在行和列相交的位置，它们将获胜。与他沟通是不可能的。

通常情况下，他们能做的最好的就是赢得89％的时间。但是，如果考虑到量子纠缠的因素，那么它们的机会就会增加。

想象一下爱丽丝和鲍勃纠缠了量子粒子。他们对粒子进行测量，并使用测量结果指示每个单元中要写入的内容-0或1。由于粒子纠缠在一起，因此测量结果将相互关联。这也意味着参与者的行为将相互联系。结果，事实证明他们将始终能够赢得比赛。

如果行和列相交的单元格中存在不同的数字，则游戏将失败。如果他们是相同的-赢了，

那么，如果事实证明有两个玩家在玩此游戏时出奇的成功，那么我们可以得出结论，他们使用的东西与经典物理学所提供的东西有所不同。今天，这些“贝尔”实验被称为“非本地”游戏，指的是玩家分离。实际上，物理学家在实验室进行类似的游戏。

阮元亨说，多年来，科学家们进行了实验，以证明这些可怕现象的真实性。

与对任何游戏的分析一样，您可能需要找出玩家在非本地游戏中获胜的频率，前提是他们玩得尽善尽美。例如，对于单人纸牌游戏，您可以计算出表现出色的一位玩家可能获胜的频率。

但是在2016年，威廉·斯洛夫斯特拉（William Slofstra）证明了没有通用算法可以计算所有非本地游戏获胜的确切最大概率。结果，研究人员提出了一个问题：是否可以至少大致计算出最大的赢钱百分比？

计算机科学家已经使用上述两种量子纠缠模型得出了答案。使用张量积模型的算法为所有非本地游戏的获胜最大概率的近似计算设置了最小值。使用切换运算符的模型的另一种算法设置最大值。

这些算法的实现给出的答案越精确，程序运行的时间就越长。如果Zirelson假设是正确的，并且这两个模型是等效的，则上下限应彼此接近，并成为代表近似最大获胜概率的单个值。

但是，如果Zirelson假设不成立，并且两个模型不相等，那么根据Henry Henry的说法，上限和下限将始终分开。而且甚至无法计算非本地游戏获胜的大致百分比。

五名研究人员在他们的新工作中利用了关于上下界是否收敛以及Zirelson假设是对还是错的争论。他们这样做是为了找到问题的答案，即在哪种情况下可以验证计算问题的解决方案。

复杂的帮助

在第二千名计算机科学家开始之初，他们就开始想知道任务范围将如何变化，可以通过“询问”两个拥有复杂粒子的证明者来验证其解决方案。

大多数科学家认为混淆会损害验证。最后，如果两个“嫌疑人”有任何协调回应的方式，他们将更容易调和虚假的证词。

但是在接下来的几年中，很明显相反的说法是正确的：通过“询问”具有复杂粒子的证明者，可以比与没有此类粒子的证明者一起工作验证更大范围的问题。

托马斯·维迪克（Thomas Widick）说，纠缠是建立相互关系的一种方式，似乎可以帮助证人说谎。但是，实际上，这种现象可以发挥其优势。

为了了解如何使用它，您首先需要处理几乎超自然的任务规模，这要归功于此交互式过程，因此可以验证其解决方案。

想象一个图形-由线（面）连接的一组点（顶点）。您需要确定是否可以使用三种颜色绘制顶点，以使图形没有两个通过面连接并且以相同颜色着色的顶点。如果可能的话，这样的图表是“三色”的。

如果您给一对证据一个非常大的图，而他们说它是“三色”的，那么您可能想知道是否有一种方法可以验证他们的答案。

对于非常大的图形，将不可能直接检查答案。相反，您可以询问每个测试器两个相连的顶点之一是什么颜色。如果他们每个人报告不同的颜色，并且每次询问时他们都会给出相似的答案，那么我们将有信心该图确实是“三种颜色”。

但是，即使这种查询策略也无法在面和顶点比宇宙中的原子更多的巨大图形上工作。对于试图验证问题的解决方案的人来说，甚至问一个特定的问题（“告诉我XYZ顶点的颜色”）也成为一个难以忍受的问题。仅指定特定顶点名称所需的数据量大于验证者可以存储在其可用内存中的数量。

但是量子纠缠使工作方案成为可能，测试人员自己在应用中提出了问题。

“验证者不需要提出问题。验证者会强迫支持者独立提出这些问题并回答这些问题，” John Wright说。

验证者需要证明者报告所连接顶点的颜色。如果未连接顶点，则问题的答案将不会说明图形是否为“三色”。换句话说，验证者需要测试人员提出相关问题。证明者之一询问ABC的顶部，第二问关于XYZ的顶部。尽管两个证据中没有一个知道另一“思考”的事实，但仍假定这两个峰是相连的。 （这类似于爱丽丝和鲍勃希望在同一单元格中写入相同数字的方式，尽管事实上他们都不知道另一方可以使用该表的哪一行或哪一列。）

如果两个证明者将完全独立地提出这样的问题，那么就不会有任何机制来迫使他们选择连接的（相关的）顶点，从而允许验证者验证其答案。但是，这种关联正是量子纠缠可以实现的。

托马斯·维迪克（Thomas Widick）表示，他们将运用复杂性将几乎所有案件转交给证人。科学家让测试人员选择自己的问题。

在此过程结束时，每个证明都报告一个顶点颜色。验证者检查这些颜色是否不同。如果图形确实是“三色”的，则测试人员永远不要报告相同的颜色。

根据Henry Yuen的说法，如果图形是“三色”，那么测试人员将能够说服研究人员确实如此。

事实证明，此验证过程是非本地游戏的另一个示例。如果证明者说服研究人员他们的决定是正确的，那么它们将“获胜”。

2012年，托马斯·维迪克和伊藤刚）证明了可以使用复杂的证明者来测试解决方案的人玩各种各样的非本地游戏。这至少适用于可以通过询问两台经典计算机来验证的相同数量的任务。因此，使用混乱的证据不会损害验证。去年，Anand Natarajan和John Wright证明了与错综复杂的证人进行交流实际上扩展了可以验证其解决方案的问题类别。

但是计算机科学家并不知道可以使用这种方法验证其解决方案的全部任务。现在他们知道了。

多米诺骨牌效应

在他们的新工作中，五位科学家证明了对困惑的证人的“审讯”使得有可能验证解决不了的问题的解决方案，包括关闭问题的解决方案。

Henry Yuen说这种类型的模型具有不可思议的验证功能。

但是停止任务是无法解决的。而事实就是最终证明的推动力。

想象一下，您将程序移交给了几个困惑的见证人。您问他们该程序是否会停止。您准备通过某种非本地游戏来验证他们的答案。校对者根据其回答的协调性产生问题并“获胜”。

如果程序实际上停止了，那么支持者应该能够在100％的情况下赢得比赛。这类似于图的示例-如果它确实是“三色”，则卷积证明不应该为连接的顶点报告相同的颜色。如果程序永不停止，则测试人员应仅在偶然的情况下获胜-在50％的情况下。

这意味着，如果有人要求您确定特定的非本地游戏获胜的大概最大概率，那么您首先必须解决停止问题。但是解决这个问题是不可能的。这意味着不可能找到非本地游戏以及停止问题的获胜概率的近似最大水平。

反过来，这意味着Tsirelson的假设是错误的：这两个量子纠缠模型并不相等。如果它们相等，则可以将下限和上限减小到相同的值，并计算出大约最大的获胜概率。

大卫· 佩雷斯·加西亚马德里孔普卢顿大学的说，这样的算法可以不存在的，因此这两个[模型]必须是不同的。

这项新工作证明了可以通过复杂的量子证明者来验证其解决方案的一类问题，称为MIP *，与不比停止问题复杂得多的一类问题与RE完全相同。本文的标题对此进行了简要说明：“ MIP * = RE”。

在证明两个复杂度类别相等的过程中，科学家证明了Tsirelson假设是错误的，这要归功于先前的工作，这意味着Conn假设也是错误的。

得益于计算机科学领域的证据而获得了解决此类大规模问题的解决方案这一事实，令在各自领域工作的研究人员感到震惊，这似乎与数学和物理学无关。

Miguel Navazquez说，如果他看到标题为MIP * = RE的文章，他将不会认为她的作品与他有共同之处。他是将Zirelson和Conn的假设联系起来的早期工作的合著者。对于他来说，这是一个完全的惊喜。

量子物理学家和数学家才刚刚开始掌握新的证明。在此之前，数学家对以下问题感兴趣：他们是否可以使用大尺寸的有限维矩阵来近似无限维的矩阵。现在，由于Conn的假设已被证明是错误的事实，他们知道无法做到这一点。

“他们的结果表明这是不可能的，”威廉·斯洛夫斯特拉说。

计算机科学家并未试图分析Conn的假设。结果，他们不能最好地解释解决此问题的可能后果。

“就我个人而言，我不是数学家。 “我对Conn假设的最初表述不太了解，” Anand Natarajan说。

他和他的合著者希望数学家将新的结果翻译成他们自己的语言。托马斯·维迪克（Thomas Widick）在一份有关证明的报告中写道：“毫无疑问，最后，将不需要计算复杂性理论来获得纯粹的数学结果。”

但是，当其他研究人员熟悉该证明时，由于可以实现该证明，所以研究之路就此终结。在过去的三十多年中，计算机科学家一直只是简单地尝试找出问题解决方案的交互式验证能使他们走多远。现在，答案摆在他们面前，是长篇文章的形式，标题很简单，并与图灵的思想相呼应。

“许多作品的作者只是想知道使用两个复杂的量子证明进行验证程序的可能性。现在我们知道此过程的功能。这个故事已经结束，” Anand Natarajan说。

亲爱的读者们！MIP * = RE的证明对您工作的区域意味着什么？