399718奇闻趣事网majer 【奇闻趣事网】399718.com01.24 , 10:00
量子物理+复杂性科学+可计算性理论=？
首先，挨个解释一下基本名词。
量子纠缠 两个或多个粒子纠缠在一起，各个粒子所拥有的特性已综合成为整体性质，无法单独描述各个粒子的性质，只能描述整体系统的性质。纠缠的粒子不受空间的限制。当我们尝试测量其中一个粒子的物理量——更不用说其它致使其物理量改变的操作——时，会即刻破坏掉它们的纠缠态，使原本纠缠在一起的粒子变成独立的粒子。但是，这一特性不能用来传递信息！实际上，假如光子A，B相互纠缠，现在把光子A带上月球，然后测量。虽然此时，在地球上的B脱离了纠缠态，但是这一事实在信息传输方面毫无意义。因为你不去测量就无法知道B的状态，但是一旦你去测量，那么纠缠态就会被破坏，而要想利用“月球上有人测量了A，破坏了纠缠态”这一信息，就必须存在某种监控B状态的手段——这手段本身就是对B的测量，所以不等有人测量A，它们就已经不是纠缠态了。尽管如此，量子纠缠的特性可用于量子通信的加密、量子计算机中内存数据纠错等。
复杂性科学 是理论计算机科学和数学的一个分支。当我们把算法实现成可执行的程序时，输入参数的大小和数目，将影响到程序运行的时间。我们发现，有些问题，随着规模提升，运算时间是呈指数级增长；还有些问题，运算时间可@以参数规模为变量的多项式刻画。著名的问题类，如P类(多项式时间复杂度)，NP类(需要多项式时间验证某个可能答案)……
可计算性理论 数理逻辑分支。研究分析，我们是否能够在图灵机上计算某些函数。因为，我们可以将某些数学命题转化为可被函数输出的数字，所以，实际上用图灵机计算函数的结果，相当于证明或审核数学证明。可计算性理论关注图灵机，通用算法之类的对象。其中最广为人知的结论就是，停机问题。
停机问题 不存在解决停机问题的通用算法，相当于说，不存在某个程序P，可以仅仅通过阅读其它程序C的语句，就能判断出，程序C运行后，是否能够在有限时间内结束或进入死循环。之前提过，图灵机上的程序和数学证明，乃至公理体系存在某种对应关系，所以，对停机问题的否定回答，相当于说不存在通用的算法，可以预先判断任意命题的可证明性——这就和一阶命题演算的不完备性，乃至哥德尔不完备定理产生了关联。
了解了上面的预备知识，就来看看令学术圈激动不已的最新发现。几位学者刚刚用165页论文，证明了量子物理，数理逻辑中的可计算性理论和计算复杂性之间存在深刻的联系：MIP*=RE。
看……看不懂
量子交互式证明 是量子物理，数理逻辑和计算复杂性的交叉学科。也就是说，相关领域的研究人员，需要预先完成量子力学，数理逻辑和计算复杂性的课程，然后再学习如何将它们编织在一起。其中量子交互式证明中的“证明”，或许称之为“验证”，更加合适。
设想一下，现在某个人突然在网上自称是来自未来的时间穿越者。那么我们会有什么反应？或许有些人直接当他是骗子，不予理睬。但也有些人，出于揭穿他的目的，向他提出关于未来的问题；经过事后验证，就可以暴露其骗子的本质(或者证实，真的有时间旅行)。
例如，可以问他下个月彩票大奖的结果。但是，问题来了，未来人或许当初并未关注此类信息，所以无法回答。同时，他为了保护自己不被现代人抓入研究所，也会在可能暴露身份的信息上撒谎。
但是，无论如何，如果他真的是未来旅行者，只要他回答了足够多的可被验证的问题——如地缘政治变革，未来几年里出现的重大事件、全球性的重大灾害等——我们终究可以以相当高的概率验证这一点。
这种通过问答对话的验证方式就是所谓的话疗交互式证明。可以与之对话的不一定是人，我们还能够借助特殊的语法与机器、机制、算法程序、理论体系、解决方案之类的对象“对话”。借此验证其可靠性。
我们发现，交互式证明系统远比我们以为的要强大，甚至可以仅通过几轮“问答”就能以极大几率判断出算法或程序的有效性。系统缩写为MIP。
那么量子又是怎么参合进来的呢？
再设想一下，威能无穷的外星人卡多突然降临地球，愿意和各国领导人交流，实现互惠共赢——前提是我们能够赢得卡多的信任。我们人类一方面和神明版的外星人保持交流，同时又需要提防其它国家抢先和外星人达成协议，获得外星黑科技！
所以，我们建立一套量子通信机制，用量子纠缠把各国的信息编制成整体信息发给卡多。各国之间的信息是彼此保密的，因为涉及国家机密。卡多回答后，整体信息又经过反编译，分发给各国。整套机制，就是为了防止某个国家通过损人利己的方式骗取卡多的信任。
现在问题来了。
经过计算后发现，如果不用量子通信机制，每个国家挨个提问，则需要更多的问题，才能最终通过卡多的“测试”。借助量子机制，把各国信息的编制到一起，哪怕不知道彼此具体的通信内容，也可以提升单次提问的验证效率——用更少的问题，就可以给出准确性更高的判断。
随后，数学家证明，1对1的量子通信本身并未提升效率。所以，有意义的是量子纠缠。最开始说过，量子纠缠本身不能传递信息，现在，我们却意外地发现，它变相提高了计算能力。
所以，为了利用量子纠缠这一神奇特性，我们构建了量子交互式证明系统，缩写是MIP*。而结果也确实令人满意。数学家证明了，我们可以用MIP*来验证一个问题是否具备停机特性——就是属于前面提到的停机问题构成的类。图灵停机问题被递归可枚举集完全编码，后者缩写就是RE。
现在，就可以大概看懂公式MIP*=RE了……吧。这种表达式就像是N=NP一样，只不过等号两边所涵盖的范围更广。这一结果又推翻了算子代数中的 Connes’ embedding conjecture，意义深远。如果猜想成立，则立刻就能知道，很多其它重要命题也成立。很多数学工具可以移植到其它领域。甚至在物理上，因为Connes’ embedding conjecture不再成立(如果论文最终通过审核)，两个用以刻画量子纠缠的数学系统失去了等价性。
这个东西太可怕了，最初的信息来自这篇博客https://***.scottaaronson.奇闻异事/blog/?p=4512。
本文版权归原作者，本站只做分享普及使用。若侵犯了你的权益，请提供版权有效证明，核实后下架删除。 (14)
未经允许不得转载：399718奇闻趣事网 » 量子物理+复杂性科学+可计算性理论=？