作者伊塔·维斯，《对话》 量子计算机可能更值得信赖
信用:Yurchanka Siarhei/Shutterstock MIP* = RE不是错别字
这是一个突破性的发现，也是量子复杂性理论领域最近一篇论文的吸引人的标题
复杂性理论是一个“复杂性类”的动物园——计算问题的集合——其中最大似然和最大似然只是两个
这篇165页的论文表明这两个班是一样的
在一个没有任何实际应用的抽象理论中，这似乎是一个微不足道的细节
但是物理学家和数学家们正成群结队地去参观动物园，尽管他们可能并不完全了解
因为这一发现对他们自己的学科产生了惊人的影响
1936年，艾伦·图灵证明停止问题——用算法决定计算机程序是永远停止还是循环——是无法解决的
现代计算机科学诞生了
它的成功给人的印象是，很快所有的实际问题都会屈服于计算机的巨大力量
但很快就变得很明显，虽然有些问题可以通过算法解决，但实际的计算将在我们的太阳吞噬了执行计算的计算机之后持续很长时间
找出如何通过算法解决问题是不够的
根据效率对解决方案进行分类至关重要
复杂性理论根据解决问题的难易程度对问题进行分类
问题的难度是根据计算持续的时间来衡量的
RE代表可以用电脑解决的问题
这是动物园
让我们看看一些子类
类别P由已知算法可以快速解决的问题组成(技术上，在多项式时间内)
例如，两个数相乘属于P，因为长乘法是解决这个问题的有效算法
求一个数的素因子的问题不知道在P；这个问题当然可以用计算机来解决，但是没有一种已知的算法能如此有效地解决这个问题
一个相关的问题，决定一个给定的数是否是素数，在2004年之前一直处于类似的边缘，当时一个有效的算法显示这个问题是在P
另一个复杂性类别是NP
想象一个迷宫
“这个迷宫有出路吗？”是/不是问题
如果答案是肯定的，那么有一个简单的方法来说服我们:简单地给我们方向，我们会跟着他们，我们会找到出口
然而，如果答案是否定的，我们将不得不穿越整个迷宫，却永远找不到一条出路来被说服
这种是/否问题，如果答案是肯定的，我们可以有效地证明，属于NP
任何一个问题的解决方案都是为了让我们相信答案，所以P包含在NP中
令人惊讶的是，一百万美元的问题是P是否=NP
没有人知道
信任机器 到目前为止描述的类代表了普通计算机面临的问题
但是计算机正在发生根本性的变化——量子计算机正在被开发
但是如果一种新型计算机出现并声称解决了我们的一个问题，我们怎么能相信它是正确的呢？ 想象两个实体之间的互动，一个询问者和一个证明者
在警方审讯中，证人可能是试图证明自己清白的嫌疑人
审讯者必须决定证明者是否有足够的说服力
存在着不平衡；就知识而言，审讯者处于劣势
在复杂性理论中，审讯者是试图解决问题的人，但计算能力有限
证明者是新的计算机，它被认为具有巨大的计算能力
交互式证明系统是一种协议，询问者可以使用它来至少以高概率确定证明者是否应该被相信
以此类推，这些是警方可能无法解决的犯罪，但至少无辜者可以让警方相信他们是无辜的
这是IP类
如果可以询问多个证明人，并且不允许证明人协调他们的答案(当警察询问多个嫌疑人时通常是这种情况)，那么我们进入到MIP类
这样的询问，通过交叉检查证明者的反应，为询问者提供了更大的权力，所以最大利益点包含知识产权
量子通信是用量子比特进行通信的一种新形式
纠缠——量子比特被神秘地纠缠在一起的一种量子特征，即使是分离的——使得量子通信与普通通信有着根本的不同
允许分子印迹聚合物的证明者共享一个纠缠的量子位导致了分子印迹聚合物*
显然，证明者之间的交流只能帮助证明者协调谎言，而不能帮助审讯者发现真相
出于这个原因，没有人期望允许更多的通信会使计算问题更加可靠和可解决
令人惊讶的是，我们现在知道MIP* = RE
这意味着量子通信的行为与正常通信大相径庭
深远的影响 20世纪70年代，阿兰·康奈斯提出了后来被称为“康奈斯嵌入问题”的问题
非常简单，这是问无限矩阵是否可以用有限矩阵来近似
这篇新论文现在证明了这是不可能的——这对纯数学家来说是一个重要的发现
与此同时，1993年，鲍里斯·齐勒尔森指出了一个现在被称为齐勒尔森问题的物理学问题
这是关于量子力学中单一情况的两种不同的数学形式——迄今为止解释亚原子世界的一个非常成功的理论
作为对同一现象的两种不同描述，可以预期这两种形式在数学上是等价的
但是新的论文现在表明他们不是
它们究竟如何仍然能够产生相同的结果，并且都描述了相同的物理现实还不得而知，但是这就是为什么物理学家也突然产生了兴趣
时间会告诉我们，对于复杂性的研究，还有什么其他未解的科学问题
毫无疑问，MIP* = RE是一个巨大的飞跃
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
