你进入一个洞穴，在黑暗的走廊的尽头，你会遇到一对密封的密室。每个密室内都有一个无所不知的神使。预言说，在这些神使的帮助下，你可以学习解决无法解决的问题的答案。但有一个问题：神使并不总是说实话。虽然他们无法相互沟通，但他们对你们问题看似随机的回答，实际上是由宇宙的结构联系在一起的。要得到你所寻求的答案，你必须首先设计……问题。
计算机科学家正在忙着新的数学证明量子纠缠系统有点像上面的描述。它似乎反驳了一个44前的猜想，并详细说明了一个理论机器能够解决著名的停顿问题，即计算机无法确定它是否能解决它目前正在试图解决的问题。
这份长达150页的证明，标题为"MIP*=RE"，涉及计算复杂性的深奥主题。如果它通过审查，它证明了量子物理学、计算和数学之间的深刻联系。它表明，一个理论类的计算设备——一个验证者——询问量子纠缠的神使——可以检查一些最复杂的计算机问题，这对量子物理学家有着重要的意义。
等号左侧是理论计算类 MIP*。自20世纪80年代以来，研究人员分析了一类称为IP（或称交互式多息时间）的问题，这是一系列可以通过交互式证据解决的问题。这是一种证明，验证器（一种常规计算机，基本上通过翻转硬币解决问题，即使用位）试图检查答案是否正确。为此，它可以向一个无所不知但不一定是诚实的观察者提问，称为证明者。
如果您熟悉复杂性类，您可能听说过 P，这是一类可在多项式时间中解决的问题，这意味着时间量等于引发到常量指数（任意数字）的输入大小。然后是 NP 问题，这些问题不清楚解决问题需要多长时间，但给定一个潜在的解决方案，只需多息时间来验证该解决方案。
NP问题的一个著名例子是图形着色问题：给定一系列由线连接的点（数学家称之为图形），如何使用三种颜色来绘制点，这样两种颜色不会接触？20世纪80年代和90年代初的研究人员表明，这些交互式证据可以验证所有的NP问题，以及一套至少复杂的问题，这些问题可以通过多式内存量来解决。
其他研究人员进一步扩展了可以通过交互式证据解决的 MIP 类问题：如果验证者能够向一对无所不知但不一定是诚实的证明者（如一对犯罪嫌疑人）提问，该怎么办？分成隔音房？这样的证明系统可以有效地验证更棘手的问题，例如验证所需的时间会随着输入的大小呈指数级增长，就像三色图形呈指数级增长一样。
现在，研究人员正在探索一种更强大的类，称为MIP*。在这种情况下，想象一下，同一对无所不知神灵坐在单独的房间里，但它们被量子力学的规则纠缠在一起。量子力学是描述亚原子粒子相互作用方式的数学系统，但其数学看起来像一个更复杂的概率版本。纠缠证明说，虽然他们分开，事情可能看起来随机，当你只与一个证明人交谈，实际上两者之间是相关的。
量子纠缠
因此，回顾一下：MIP是一种假设的证明系统，一个普通的计算机向一对无所不知神使但不一定是诚实的、无法相互通信的"神使"提出问题。这种证明系统可以有效地检查极其复杂的问题的答案。科学家们现在试图理解，当MIP扩展到MIP*时，这种证明方法会有多强大——神使仍然无法通信，但它们现在被量子纠缠在一起，所以它们给出的答案比它们本来更相关。
现在加州理工学院的研究员阿南德·纳塔拉詹（ Anand Natarajan），曾经听过计算机科学家斯科特·亚伦森（Scott Aaronson）在MIP*上演讲，并意识到人们对这个演讲知之甚少。"研究报告的作者之一纳塔拉詹（Natarajan）对我们说："在复杂性理论中，这是一种罕见的情况，在那里，你拥有大量关于真相实际存在的可能性。”麻省理工学院研究员约翰·赖特（John Wright）向我们解释说，IP和MIP已经有了定义，现在由他们来决定MIP*。
图注：德国物理学家海森堡首次提出量子不确定原理去年，赖特 和 纳塔拉詹起草了一份证据，证明MIP*类中的幽灵式连接，使询问纠缠的证明者能够检查更棘手的问题（其复杂性随输入的大小呈双倍增长）。增加的纠缠为验证者提供了更多的知识，以询问证明者（神使）得更好问题。同时，量子力学的另一个原理，不确定性原理，每次验证器询问两个互补特性之一时，都会扰乱验证者的测量互补性，使得它们很难误导验证者。
这一作品来自赖特、纳塔拉詹、悉尼科技大学的吉正峰、加州理工学院的托马斯·维迪克和多伦多大学的亨利·袁，已经证明MIP*类的能力与去年的证明相形见绌。他们认为MIP*可以有效地验证"递归枚举类"或RE中的每一个问题，基本上，每个问题，如果答案为"是"，需要有限的时间来计算；如果回答"否"，那么"否"答案可能需要无限时间才能计算。MIP*=RE。
赖特说，基本上，这个理论上的MIP*设备可以解决很多非常复杂的问题，包括著名的停顿问题，即计算机被问到当前运行的程序是否会终止。MIP*=RE证明在数学和物理中具有重要影响。
"简而言之，我认为这是一个了不起的结果，"没有参与这项研究的芝加哥大学计算机科学助理教授比尔·费弗曼在一封电子邮件中告诉我们。“这一结果是量子信息社会工具如何在广泛的科学领域发挥作用，并在看似完全独立的领域找到解决方案的一个很好的例子。这就是为什么我对这个结果特别兴奋的原因。”
代尔夫特科技大学量子信息学教授斯蒂芬妮·韦纳告诉我们，只有证据才能证明了你对量子力学的了解程度。科学家们想知道纠缠的量子系统之间的相关性在最普遍意义上到底有多强。但是，作为证据机制的副作用，以及神使与验证者之间的关系，事实证明，这个问题是无法估量的。
"这是一个基本声明，事实上，我们真的不知道某些事情的答案，"韦纳告诉我们。"我觉得这个证据很有趣。”
作为这种不可估量的副产品，众多的证明驳斥了44年前的抽象代数猜想，叫做Connes嵌入猜想，这是一种深奥的数学陈述，在逻辑上等同于其他数学和物理主题中的陈述是等价的。麻省理工学院物理学家阿拉姆·哈罗告诉我们，许多人希望Connes猜想是真的，因为这将证明这个领域数学家的一些有用的事实和工具是真实的。
具体来说，对于物理学家来说，证明Connes嵌入猜想是错误的意味着，两个独立的数学对象曾经被认为，在如何解释测量纠缠系统方面是等价的，事实上，它们并不是等价的。从无限到有限系统的某些近似不再起作用，正如物理学家曾经认为的那样。
这不是一个永远存在的真正设备——你不能把无所不知的神使的预言联系在一起，一个无所不知的神使的预言也根本不存在。但是研究人员使用这些抽象场景来理解，计算机能做什么和不能做什么的真正极限。也许，这些神使预言的缩减版本，就像依靠量子力学数学来进行计算的纠缠计算机一样，其威力可能超出了物理学家先前的预期。
