量子计算的重大突破正在撼动物理和数学

MIP*=RE不是打字错误。这是一项开创性的发现，也是量子复杂性理论领域最近一篇论文的朗朗上口的标题。复杂性理论是“复杂性类”(计算问题的集合)的动物园，MIP*和RE只是其中的两个。

165页的论文显示，这两个班级是一样的。在没有任何现实应用的抽象理论中，这可能看起来是微不足道的细节。但物理学家和数学家们蜂拥而至参观动物园，尽管他们可能并不了解全部情况。因为事实证明，这一发现对他们自己的学科产生了令人震惊的后果。

1936年，艾伦·图灵(Alan Turing)证明了停止问题--用算法决定一个计算机程序是永远停止还是永远循环--是无法解决的。现代计算机科学诞生了。它的成功给人的印象是，很快所有的实际问题都将屈服于计算机的巨大功能。

但很快就变得明显起来，虽然有些问题可以通过算法解决，但实际的计算将在我们的太阳吞没执行计算的计算机之后很长一段时间内继续进行。光靠算法解决问题是不够的。根据效率对解决方案进行分类至关重要。复杂性理论根据解决问题的难易程度对问题进行分类。问题的难易程度是根据计算持续的时间来衡量的。

RE代表可以用计算机解决的问题。这是动物园。让我们来看看一些子类。

类P由已知算法可以快速解决的问题组成(技术上讲，在多项式时间内)。例如，将两个数字相乘属于P，因为长乘是解决该问题的有效算法。求一个数的素因数的问题在P中是未知的；这个问题当然可以用计算机来解决，但是没有一个已知的算法可以有效地这样做。一个相关的问题，即判断一个给定的数字是否是质数，一直处于类似的悬而未决的状态，直到2004年，一个有效的算法表明这个问题在P。

另一个复杂性类是NP。想象一下迷宫。“有没有办法走出这个迷宫？”是一个是/否的问题。如果答案是肯定的，那么有一个简单的方法可以说服我们：只要给我们指路，我们就会跟着他们走，我们就会找到出口。然而，如果答案是否定的，我们将不得不穿越整个迷宫，而从来没有找到一条可以说服我们的出路。

这样的是/否问题，如果答案是肯定的，我们可以有效地证明它属于NP。任何问题的解决方案都能使我们相信答案，因此P包含在NP中。令人惊讶的是，一个百万美元的问题是P=NP。没人知道。

到目前为止所描述的类代表了普通计算机所面临的问题。但是计算机正在发生根本性的变化--量子计算机正在开发中。但是，如果出现了一种新型计算机，并声称可以解决我们的一个问题，我们怎么能相信它是正确的呢？

想象一下两个实体(审讯者和证明者)之间的交互。在警方审讯中，证明者可能是一名试图证明自己清白的嫌疑人。审讯员必须决定证明人是否有足够的说服力。这是一种不平衡；从知识上讲，审讯者处于劣势。

在复杂性理论中，审讯者是具有有限计算能力，试图解决问题的人。证明者是新的计算机，它被认为具有巨大的计算能力。交互式证明系统是询问者可以使用的协议，以便至少以高概率确定证明者是否应该被信任。以此类推，这些都是警方可能无法破获的罪行，但至少无辜的人可以让警方相信他们是清白的。这是班级IP。

如果可以审问多个证明人，而证明人不被允许协调他们的答案(这是警方审问多个嫌疑人时的典型情况)，那么我们就到了MIP类。这样的审讯，通过交叉检查证明者的回答，为审讯者提供了更大的权力，因此MIP包含IP。

量子通信是利用量子比特实现的一种新的通信形式。纠缠-一种量子特性，其中量子比特即使分离也会令人毛骨悚然地纠缠-使量子通信从根本上不同于普通通信。允许MIP的证明者共享一个纠缠的量子比特，就产生了MIP*类。

很明显，证明者之间的交流只能帮助证明者协调谎言，而不能帮助审讯者发现真相。出于这个原因，没有人预料到允许更多的通信会使计算问题更可靠和更可解决。令人惊讶的是，我们现在知道MIP*=RE。这意味着量子通信的行为与正常通信截然不同。

20世纪70年代，阿兰·康尼斯(Alain Connes)提出了后来广为人知的康尼斯嵌入问题。粗略地简化，这就提出了无限矩阵是否可以用有限矩阵近似的问题。这篇新论文现在证明了这是不可能的--这对纯数学家来说是一个重要的发现。

与此同时，1993年，鲍里斯·齐雷森(Boris Tsirelson)精确地指出了物理学中的一个问题，即现在所知的齐雷森问题。这是关于量子力学中同一种情况的两种不同的数学形式-到目前为止，这是一个解释亚原子世界的令人难以置信的成功理论。作为对同一现象的两种不同描述，可以预料到这两种形式主义在数学上是等价的。

但这篇新论文现在表明，事实并非如此。目前尚不清楚它们究竟如何仍然能产生相同的结果，并描述相同的物理现实，但这就是为什么物理学家也突然对此感兴趣的原因。

时间会告诉我们，复杂性研究还会有哪些其他悬而未决的科学问题。毫无疑问，MIP*=RE是一个巨大的飞跃。