---- 公告栏 ----

宁夏睿智教育培训学校
宁夏最好的中小学文化课补习辅导学校

教学中心

量子物理+复杂性科学+可计算性理论=?

发布时间:2020-02-10 12:30 作者:宁夏睿智培训学校 次数:
先,挨个解释一下基本名词。

量子纠缠 两个或多个粒子纠缠在一起,各个粒子所拥有的特性已综合成为整体性质,无法单独描述各个粒子的性质,只能描述整体系统的性质。纠缠的粒子不受空间的限制。当我们尝试测量其中一个粒子的物理量——更不用说其它致使其物理量改变的操作——时,会即刻破坏掉它们的纠缠态,使原本纠缠在一起的粒子变成独立的粒子。但是,这一特性不能用来传递信息!实际上,假如光子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不再成立(如果论文最终通过审核),两个用以刻画量子纠缠的数学系统失去了等价性。