🍴 🧑🏼‍🤝‍🧑🏼 🍙 计算机科学定理的重要证明用数学捕捉了物理学 🐩 👲🏾 🚶🏾

计算机科学专家已经确定了通过计算验证的知识的新领域。同时，他们解决了量子力学和纯数学方面的重大问题。

1935年，阿尔伯特·爱因斯坦（Albert Einstein）与鲍里斯·波多尔斯基（Boris Podolsky）和内森·罗森（Nathan Rosen）一起试图应对开辟新的量子物理学定律的机会：两个粒子的“纠缠”，在这种情况下可以很远的距离分开。

次年，艾伦·图灵（Alan Turing）提出了第一个广义计算理论，并证明了原则上不受计算机约束的问题的存在。

这两个想法彻底改变了它们各自的领域。此外，似乎他们彼此之间没有任何关系。但是，现在有一个重要的证明将它们结合在一起，同时解决了计算机科学，物理学和数学中的许多问题。

新证据表明，使用量子比特或“量子比特”而不是经典的零和一进行计算的量子计算机在理论上可以用于确认各种问题的解决方案。量子纠缠与计算机技术之间的联系令许多研究人员震惊。

“这完全出乎意料，” 米格尔·纳瓦兹克斯（Miguel Navazquez）说在维也纳量子光学与量子信息研究所攻读量子物理学。

证明的共同作者决定确定确认计算问题解决方案可能性的界限。他们的方法使用混乱。在发现了这些边界之后，研究人员几乎同时还回答了另外两个问题：关于纠缠的数学建模的物理Zirelson问题，以及有关纯数学的相关问题，即Conn的嵌套假设。

结果最终像多米诺骨牌一样下降。

“所有最初的想法都是在大约同一时间诞生的。亨利·伊万（Henry Ewan）说，他们以如此惊人的方式汇聚在一起很方便来自多伦多大学的证据作者之一。其他作者：悉尼科技大学的Ji Zhengfeng Ji，加州理工学院的Anand Natarajan和Thomas Widick，以及德克萨斯大学奥斯汀分校的John Wright。这五位都是计算机科学家。

不可解决的任务

图灵甚至在计算机本身问世之前就确定了用于研究计算的主要平台。实际上，他立即证明了计算机原则上不能解决某些问题-并且可以证明这一点。问题是解决特定问题的程序是否结束了工作。

通常，计算机程序会接收输入数据，并在一段时间后产生输出数据。但是有时它们会陷入无休止的循环中，从而使齿轮永远旋转。发生这种情况时，您只剩下一个选择。

“我必须手动确定程序。阻止她，” Ewan说。

图灵证明，没有通用的算法可以确定程序将完成执行还是永远运行。为了找到答案，您必须运行程序本身。

Ewan，Vidik，Ji，Nataarajan和Wright

“您等了一百万年，该程序仍未完成。您还需要再等一百万年吗？滑铁卢大学的数学家威廉·斯洛夫斯特拉（William Slofstra）说，这个问题没有答案。

从技术上讲，停止程序的任务是无法解决的-即使您能想象到的功能最强大的计算机也无法解决该问题。

图灵之后，计算机科学家开始根据其复杂性对其他任务进行分类。更复杂的任务需要更多的计算资源来解决-更多的工作时间，更多的内存。因此，研究任务的计算复杂性。

结果，您可以针对每个任务问两个问题：“解决它有多困难？” 和“验证正确答案有多难？”

讯问确认

对于简单任务，可以独立检查答案。但是随着它们变得越来越复杂，即使检查答案也可能成为不可能的任务。但是，在1985年，计算机科学家意识到，即使您自己无法确认答案，也有可能验证答案的正确性。

此方法遵循警察调查的逻辑。如果嫌疑人讲了一个令人困惑的故事，则您可能无法检查该故事的每个细节。但是，通过提出正确的问题，您可以撒谎欺骗犯罪嫌疑人，或者可以确保故事的真实性。

就信息学而言，审讯包含一台功能强大的计算机（称为“证明人”），该计算机为问题提供解决方案；而一台功能较弱的计算机则要求问题的证明者确定答案的正确性，称为“测试”。

一个简单的例子：假设您不区分颜色，另一个人（证明者）声称某些球中的两个具有不同的颜色。您不能自己验证此声明，但是通过巧妙的询问，您仍然可以验证它是正确的。

将球放在后面并混合。要求证明者告诉您哪种颜色。如果它们确实是不同的颜色，则证明者必须不断正确地回答问题。如果它们的颜色相同-即它们看起来相同-一半情况下的证明者将表达错误的猜测。

Vidik说：“如果我看到您取得的成功超过一半，那么我将几乎确定它们不是同一颜色。”

通过询问证明者问题，您可以确认解决方案的正确性，而不是解决自己的问题。

1988年，计算机科学家考虑了如果两个证明者提出对同一问题的解决方案，将会发生什么情况。毕竟，如果您有机会讯问两名犯罪嫌疑人，那么您解决犯罪或确认决定的正确性将更加容易-可以将它们相互比较。

对于那些检查它的人，它提供了更大的压力空间。维迪克说：“你审问，询问与案件有关的问题，再核对答案。”如果嫌疑人说的是实话，他们的答案在大多数情况下应该是一致的。如果他们撒谎，将会有更多的矛盾。

类似地，研究人员表明，与仅由一个证明者解决的问题相比，通过分别询问两个证明者的答案，您可以快速确定解决更广泛问题类别的正确性。

在您看来，计算复杂性可能纯粹是理论上的想法，但它与现实世界密切相关。计算机解决问题和确认决策所需的资源-时间和内存-本质上是物理的。因此，物理学上的新发现可以改变计算的复杂性。

纳塔拉延说：“如果选择不同的物理定律集，例如量子世界而不是经典的定律，则可以从中推导出另一种复杂性理论。”

新证据是21世纪计算机科学家与20世纪物理学中最奇怪的思想之一：纠缠之间对抗的最终结果。

康恩的嵌套假设

当两个粒子纠缠在一起时，它们不会互相影响-它们之间没有因果关系。爱因斯坦等人在1935年的一篇论文中揭示了这个想法。此后，物理学家和数学家试图提出一种数学方法来描述混淆的实际含义。

但是，有些混乱。科学家们提出了两种不同的纠缠数学模型-它们相互等效是完全不明显的。

这种潜在的不和谐间接地影响了纯数学领域（康恩关于嵌套的假设）中一个重要问题的出现。最后，它还充当了分裂，五位计算机科学家在他们的新证据中加以利用。

对纠缠进行建模的第一种方法是想象空间上孤立的粒子。例如，其中一个在地球上，另一个在火星上。它们之间的距离排除了因果关系。这称为张量积模型。

但是在某些情况下，尚不清楚两个对象是否真正因果相互隔离。因此，数学家提出了一种更一般的描述因果独立性的方法。

如果对对象的操作顺序无关紧要，则将操作视为已切换：3 x 2将等于2 x3。在第二个模型中，粒子的属性相关时会纠缠在一起，但测量顺序无关紧要。测量粒子A以预测粒子B的动量，反之亦然。无论如何，答案都是一样的。这称为交换算子纠缠模型。

两种对纠缠的描述都使用以矩阵和列组织的数字数组。张量积模型使用的列和行数有限的矩阵。换向算子纠缠模型使用一个更通用的对象，该对象的作用类似于矩阵，但具有无限数量的行和列。

随着时间的流逝，数学家开始独立研究这些矩阵，而与物理学无关。在这项工作的框架中，数学家阿兰·康恩（Alain Conn）在1976年提出假设，可以用有限维矩阵近似许多无穷维矩阵。这是康恩关于嵌套的假说的结论之一。

在接下来的十年中，苏联物理学家[在原始物理学家中，但在Wikipedia上被列为数学家/大约。鲍里斯·齐雷尔森（Boris Tsirelson）提出了这个问题的他自己的版本，该版本再次与物理学相关。Zirelson建议张量积和描述纠缠的可交换算子模型大致相等。这是有道理的，因为从理论上讲，这是描述同一物理现象的两种不同方式。随后的工作表明，由于矩阵和使用它们的物理模型之间的联系，康恩关于嵌套的假设和齐勒森问题相互遵循：解决一个问题，然后解决另一个问题。

但是，结果两个问题的解决方案出现了完全不同的方向。

物理与游戏

在1960年代，物理学家约翰·贝尔（John Bell）提出了一项测试，以确定缠结是真正的物理现象还是只是理论上的想法。诸如游戏之类的东西参与了测试，测试的结果报告了除普通非量子物理以外的其他因素是否在实验中起作用。

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

但是首先，要了解这些游戏的工作原理，请想象两个玩家Alice和Bob和一个3x3盒子。法官给了爱丽丝一行，并建议她在每个像元中放置0或1行，这样数字的总和是奇数。鲍勃被分配一列，他需要填写所有单元格，以便数字的总和为偶数。如果将相同的数字放在相同的单元格（选定的行和列相交的位置）中，则它们将获胜。但是同时他们无法交流。

在正常情况下，玩家有能力做到的最好是在89％的情况下获胜。但是在量子世界中，他们可以改善这一结果。

假设爱丽丝和鲍勃共享一对纠缠的粒子。他们每个人都对其粒子进行测量，并使用结果确定每个单元格中写入0还是1。由于粒子纠缠了，它们的测量结果将相互关联，这意味着它们的答案也将相互关联-这意味着，他们将能够在100％的情况下获胜。

因此，如果您发现两个玩家经常意外地赢得比赛，则可以得出结论，他们使用了经典物理学之外的方法。现在，贝尔的实验被称为“非本地”游戏，指的是玩家分离。物理学家实际上是在实验室中进行此类实验的。

Ewan说：“人们已经进行了这样的实验多年，从他们那里可以看出这种可怕的影响确实存在。”

在分析任何游戏时，您可能需要有关如果玩家尝试以最佳方式玩游戏赢得非本地游戏的频率的信息。例如，如果您使用单人纸牌，那么您可以计算出玩得完美的玩家获胜的概率。

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

计算机科学家使用两种描述复杂性的模型来寻找答案。使用张量积模型的算法确定了所有非本地游戏的下限，即获胜的最大概率的最小值。将纠缠模型与拨号运算符一起使用的另一种算法确定了其上限。

这些算法工作的时间越长，它们产生的结果越准确。如果Zirelson的预测是正确的，并且这两个模型确实相等，则上下限应逐渐接近，并收敛到大约最大获胜概率的单个值。

但是，如果Cirelson的预测是错误的，并且两个模型不相等，那么“上下限将永远保持分离”，Ewan说。甚至无法计算出非本地游戏获胜的最大概率的近似值。

在这项新工作中，五名研究人员使用了这个主题（上下边界是否收敛，以及Tsirelson假设是否成立）来解决有关确认计算问题解决方案正确性的另一个问题。

复杂的帮助

在2000年代初期，计算机科学家认为：任务范围将如何改变，可以通过与两个具有复杂粒子的专家进行访谈来确认其解决方案？

大多数人认为纠缠会与确认相抵触。的确，如果两个犯罪嫌疑人有办法协调答案，那么他们会更容易构造一致的谎言。

但是近年来，计算机科学家已经意识到这实际上是相反的：通过询问专家，划分成对的纠缠粒子，可以比无纠缠方式更广泛地解决问题。

Vidik说：“混乱是获得相互联系的一种方式，似乎可以帮助他们说谎和作弊。” “但实际上您可以将其包装在您的手中。”

要了解如何做到这一点，您首先需要评估几乎超自然的任务范围，您可以使用此交互式过程检查其解决方案。

想象一个图形-由线（边）连接的一组点（顶点）。您可能想找出是否可以用三种颜色对顶点进行着色，以使没有相同颜色的成对的顶点通过共同的边缘结合在一起。

如果您让几个人证明一个很大的图，并且他们说它可以按所述的三种颜色上色，您会认为：有没有办法检查这个答案？

很大的图不能直接验证。取而代之的是，您可以要求每个证明者报告通过一条边连接的两个顶点的颜色。如果它们报告不同的颜色，并且每次在调查其他顶点时都给出不同的颜色，则您对使用三种颜色进行绘制的信心会增强。

但是，当图形真正变大时（当边和顶点的数量开始超过宇宙中原子的数量时），这种轮询策略也将停止工作。对于验证者，即使提出特定问题（“告诉我XYZ顶点的颜色”）这样的任务也变得难以忍受-命名特定顶点所需的数据量超过了可用的工作内存。

但是，困惑让证明者自己提出问题。

“审稿人无需弄清楚问题。检查员让检举人自己为他计算问题，”赖特说。

检查员需要证明者告诉他所连接的顶点的颜色。如果未连接顶点，则问题的答案将不会说明以三种颜色为图形着色的可能性。换句话说，检查者希望证明者提出相关问题：一个证明者询问关于顶点ABC的问题，另一个询问关于顶点XYZ的问题。我希望将这两个峰连接起来，尽管没有一位专家知道另一峰在谈论哪个峰。爱丽丝和鲍勃希望以相同的方式将相同的数字放在相同的正方形中，尽管他们俩都不知道其他的行和列。

如果两个证明者中的每一个完全独立地提出问题，那么他们就不会被迫选择相连的或相关的峰，以便审查员可以确认他们的答案。但是，纠缠仅允许您建立关联。

“我们将混乱地将所有工作转交给专家。 Vidik说，我们将让他们选择自己的问题。

在该过程结束时，每个证明者报告一种颜色。审核者检查他们是否匹配。如果图实际上可以用三种颜色着色，则证明者永远不能产生相同的颜色。

埃万说：“如果伯爵可以用三种颜色涂漆，那么专家们就能说服你。”

事实证明，该确认过程是非本地游戏的另一个示例。证明者通过说服他们决策的正确性来“获胜”。

在2012年，Vidik和Tsiyoshi Ito证明，通过玩各种带有混乱证据的非本地游戏，可以确认至少与审问两台经典计算机时任务数量相同的答案。也就是说，使用混乱的证明者不会损害对他们的水獭的确认。去年，Nataarajan和Wright证明了与复杂的证明者进行交互实际上扩展了已验证任务的类别。

但是，到目前为止，计算机科学家尚未猜测出全部任务的规模，可以以类似的方式确认其解决方案。

一系列后果

在这项新工作中，五名计算机科学家证明了对盘旋的证明者的审讯可以确认对未解决问题（包括停止问题）的解决方案。

“该模型的验证功能非常出色，” Ewan说。

但是，停止问题无法解决。这个事实成为完成证明的关键。

假设您将程序提供给一些令人困惑的证明。您要求他们说是否将停止执行。您已经准备好通过各种非本地游戏来测试他们的答案：证明者根据他们的答案的一致性给出问题并获胜。

如果程序真的停止了，证明者应该能够在100％的情况下赢得这场比赛-就像可以用三种颜色着色的图形一样，当卷积证明者不必为两个相连的顶点给出相同的颜色时。如果程序没有停止，那么证明者应该只是偶然赢了-也就是说，在50％的情况下。

这意味着，如果有人要求您确定特定非本地游戏获胜的近似最大概率，则您首先需要解决停止问题。但是这是不可能解决的。这意味着计算近似最大获胜概率的任务以及停止问题都是无法解决的。

反过来，这意味着Zirelson问题的答案是否定的-两种纠缠模型并不相等。如果是这样，则有可能一起降低分数的上限和下限，并计算出大约最大的获胜概率。

马德里Complutense大学的David Perez-Garcia说：“不可能有这样一种算法，因此两个模型必须不同。”

这项新工作证明了可以通过与纠缠的量子证明者MIP *相互作用来确定其解决方案的问题类别完全等同于比停止问题RE更复杂的问题类别。作品的标题简要描述了其本质：“ MIP * = RE”。

在寻找两个复杂度类的相等性的证据的过程中，计算机科学家证明了Tsirelson假设的虚假性，这要归功于先前的工作，这意味着Conn假说关于嵌套的虚假性。

相关领域的研究人员震惊地发现，在计算机科学领域看似无关的证据的过程中找到了解决此类复杂问题的答案。

“当我看到名为MIP * = RE的作品时，我绝对不会认为这与我的作品有任何关系，”先前将Cirelson假设与Conn关于嵌套的假设联系起来的前一本书的合著者Navazquez说。 “这让我感到完全惊讶。”

量子物理学和数学专家刚刚开始消化这些信息。以前，数学家对它们是否可以将大尺寸有限矩阵近似为感兴趣。现在，知道了康恩关于嵌套的假说的虚假性，他们知道自己做不到。

“从他们的结果来看，这是不可能的，” Slofstra说。

计算机科学家自己并没有试图证明Conn关于嵌套的假设，因此其他人应该解释所找到答案的所有后果。

“我本人不是数学家。纳塔拉然说：“我对Conn关于嵌套的假设的最初定义不太了解。”

他们和合著者建议，数学家们自己会将新结果转换成他们所学领域的语言。Vidik在一篇声明证据的文章中写道：“毫无疑问，为了获得纯粹的数学结果，不再需要复杂性理论。”

由此产生的证据打断了导致它的长期研究链。超过三十年来，计算机科学家一直在尝试找出他们的交互式确认将起到多大的作用。现在他们有了一个长期工作的答案，标题很简单，并提到了图灵。

Natarajan说，在确认程序的帮助下，“有很多作品问到了什么机会”，这令人困惑。“现在我们知道哪个。故事结束了。

计算机科学定理的重要证明用数学捕捉了物理学