如果MIP*=RE成立...[color=rgba(0, 0, 0, 0.298)]
[color=rgba(0, 0, 0, 0.298)]Original [color=rgba(0, 0, 0, 0.298)]Ryan
原理 [color=rgba(0, 0, 0, 0.298)]1 week ago
[color=rgba(0, 0, 0, 0.298)]
[color=rgba(0, 0, 0, 0.298)]
“MIP*=RE”
这是一篇前几天刚上传到arXiv上的论文的标题。在这个简短有力的标题背后是一篇长达165页的证明，它所涉及到的是极为深奥的计算复杂性问题。自发表以来，就引起了极大的关注度。如果这个等式最终被检验是成立的，它就证明了量子物理、计算和数学之间存在着一种深刻的联系。
为了理解这个等式背后的意义，让我们首先试想如下画面：
你进入了一个黑暗的空间，在空间的深处你看到了两个封闭的房间，在房间内，各有一个无所不知的圣人。预言里说，有了圣人的帮助，你可以获知任何无法回答的问题的答案。但有一个问题是，圣人所说的并不总是实情。虽然他们互相不能交流，但他们给出的看似随机的回答实际上是联系在一起的。所以，若要得到你所寻求的答案，你就必须先想出问题。
这个正被热议的新证明提出了一个与上述场景有些类似的量子纠缠系统。这个证明似乎推翻了一个已有44年历史的猜想，并详细描述了一台能够解决著名的停机问题的理论机器。停机问题说的是一台计算机无法确定它是否能够解决它目前正在尝试解决的问题。
1.
在标题中，等号左边代表的是理论计算类MIP*。自20世纪80年代以来，计算机科学家就开始分析一类被称为IP（交互多项式时间）的问题，这是一系列可以通过交互式证明系统得到解决的问题。交互证明由验证者和证明者构成，验证者是一种通过抛掷硬币（如比特）来解决问题的普通计算机，以检查答案是否正确；要做到这一点，它可以向一个无所不知但不一定诚实的观察者，也就是“证明者”提问。
如果你熟悉复杂性类，那么你肯定听过P问题，这是一类可以在多项式时间内解决的问题；然后还有NP问题，这是一类不清楚需要多长时间才能解决，但如果给出一个可能的解决方案，就可以在多项式时间来验证这个解决方案的问题。图着色问题就是NP问题中的一个典型例子，它要求用三种颜色给一系列由直线连接的点着色，使相连的两点是不同颜色。20世纪80年代和90年代初的研究表明，这些交互证明可以验证所有NP问题，以及可以验证至少与能在多项式内解决的问题一样复杂的问题集合。
○ 在三色图中，两个相邻的点都具有不同的颜色。
1988年，四名计算机科学家进一步将可通过交互证明解决的问题扩展到MIP类：如果验证者能够向两个无所不知但未必诚实的证明者提问，就像对着两个被分别隔离在两个审讯室的犯罪嫌疑人提问一样，情况又会怎样？这样的证明系统可以有效地验证更困难的问题，比如验证所需的时间随着输入的大小呈指数增长，就像一个三色图呈指数变大一样。 现在，研究人员正在探索一类更强大的问题，即为MIP*类。在这个场景中，我们同样可以想象两个坐在不同房间的一对无所不知的圣人，他们之间是通过量子力学的规则而纠缠在一起的（量子纠缠告诉我们，两个相距遥远的物体能够瞬时相互影响）。两个纠缠的证明者意味着，虽然他们二人是分开的，与你说话的也只是其中一个证明者，但那些看似随机的事情实际上是相互关联的。
2.
回顾一下：MIP是一种假设的证明系统，一台普通的计算机向一对无所不知但不一定诚实的“圣人”提出问题，而这些“圣人”彼此之间无法交流。这种证明系统可以有效地检验极其复杂的问题的答案。现在，科学家试图理解的是当他们将MIP扩展到MIP*时，这种证明方法将会强大到何种程度。对于MIP*类问题来说，两个圣人仍然无法交流，但他们之间存在量子纠缠，因此他们给出的答案比其他情况下更具有相关性。
去年，这篇论文的其中两名作者John Wright和Anand Natarajan起草了一份证明，证明了MIP*类问题中的那种鬼魅般的连接，使验证者能够询问纠缠的证明者，从而能够对更困难的问题（那些复杂性随输入的大小呈双倍指数增长的问题）进行检验。额外的纠缠使验证者能获得更多信息，以便向证明者（圣人）提出更好的问题。同时，根据量子力学中的不确定性原理，当验证者每次询问两个互补性质中的一个时，都会打乱验证者的测量，使他们很难误导验证者。
在新的论文中，论文的第一作者季铮锋（Zhengfeng Ji）与其他几位作者一起作出的证明使去年的证明相形见绌：他们提出，MIP*类可以有效地验证“递归可枚举类”（RE）问题中的每一个问题，基本上每一个如果答案是“是”的问题，都可以在有限的时间内计算；每一个答案是“否”的问题，需要无限长的时间来计算。
MIP* = RE！
这是一个了不起的结果，这一理论上的MIP*设备可以解决很多非常复杂的问题。一直以来，科学家们都想知道从最广义的意义上讲，纠缠的量子系统之间的相关性到底有多强，但现在我们知道，这个问题是不可计算的。这是一个基本声明，它说的是，对于某些特定的问题来说，我们是真的无法知道答案。
作为这种不可计算性的副产品，这个证明还驳斥了科纳嵌入猜想（Connes‘ embedding conjecture，由法国数学家、菲尔兹奖得主Alain Connes提出），这是一个在抽象代数中已存在了44年之久的猜想。很多人都希望希望科纳的猜想是正确的，因为如果是那样的话，就可以证明这个领域中的许多其他有用的事实和数学工具也是正确的。而且，这个问题对物理学家来说也尤为重要，因为如果科纳嵌入猜想是错误的，那就意味着两个曾被认为是等价的独立数学对象在解释测量纠缠系统时，实际上是不等价的，某些从无限到有限的近似也将不再像物理学家曾经设想的那样奏效。
当然，这不是一个真正的设备，因为我们既不能将无所不知的圣人连在一起，也不存在这样一个无所不知的圣人。但研究人员利用这种抽象的场景来理解计算机所能做到的和不能做到的真正极限。
参考来源：
https://gizmodo.com/remarkable-mathematical-proof-describes-how-to-solve-se-1841003769
https://www.quantamagazine.org/computer-scientists-expand-the-frontier-of-verifiable-knowledge-20190523/ https://www.nature.com/articles/d41586-020-00120-6
| 
发表于 2020-1-28 02:24
收藏
分享