量子计算机有多神？它能解决哪些历史无解的难题？| 袁岚峰_风闻

导读

　　量子计算的重要性，在于它可能解决传统无法解决的问题，而不是以另一种方式去解决那些已经解决的问题。如果你理解到这一层，你的知识水平就超过了99%的人。

　　视频链接：

　　西瓜视频：

　　https://www.ixigua.com/6943853959555580419

　　本视频发布于2021年3月26****日，播放量近80万

　　精彩呈现：

　　关于中国的量子计算机“九章”，我已经讲过几次了（量子计算机不是计算机？键盘侠们会对美国这样说吗？| 袁岚峰）。最近我发现需要再讲一次，因为这个问题在某种程度上把院士都搞糊涂了。

　　事情是这样的：北京大学地球与空间科学学院涂传诒院士在微信公众号上发了两篇文章（杂谈｜是量子计算，还是光学实验？和对“九章-光量子计算机” 的理解），认为九章只是个物理实验，不是个计算机，跟量子计算无关。2021年3月17日，九章论文的作者陆朝阳和潘建伟发了一个《“九章”作者对涂传诒先生等若干网络评论文章的回复 | 墨子沙龙》。

　　这事最基本的图景是：我们非常尊敬涂院士在自己的专业领域即“空间物理学、太阳风湍流、太阳风动力学与日球层物理”的贡献，同时对于老爷子81岁高龄还在关心前沿科技、认真查文献、找资料的精神，也十分敬佩。不过隔行如隔山，术业有专攻，老爷子对量子计算确实远不是内行，在两篇文章中出现了不少误解。

　　中国科学院网站上对涂传诒的介绍http://casad.cas.cn/sourcedb_ad_cas/zw2/ysxx/dxb/200906/t20090624_1804290.html

　　下面，我们从根源上来介绍量子计算。当你懂得了正确的是什么，自然就获得了剖析错误的能力。

　　最基本的，当你的计算机不够用时，该怎么办？显而易见的回答是，换更快的计算机。

　　但重点在于，有些问题是换更快的计算机解决不了的，因为这些问题的计算量是指数增长的。把指数函数和多项式函数的图像对比一下就会发现，指数比多项式增长得快得多。

　　指数增长与多项式增长

　　如果一个问题的计算量是2的n次方，这里的n是问题的规模，比如分解因数时待分解的数字的位数，那么即使你换了一个速度是原来两倍的计算机，你也只能比原来多算一位。即使你换了一个速度是原来1024倍的计算机，你也只能比原来多算10位。大自然或者出题人稍微增加一下问题的规模，就会把你甩得连尾灯都看不见。

　　这样的问题，我们就称为不可解决的，或者不可有效解决的，或者不可快速解决的，或者困难的。诸如此类的说法，实际的意思都是：这个问题的计算量是指数增长的。与之相对，计算量多项式增长的问题就称为可以解决的，或者可以有效解决的，或者可以快速解决的，或者容易的，诸如此类。

　　因此，基本的区分就是：多项式增长 = 容易，指数增长 = 灾难。如果你理解到这一层，你的知识水平就超越了90%的人。

　　多项式增长 = 容易

　　指数增长 = 灾难

　　这个分类叫做计算复杂性（computational complexity），或者计算复杂度。计算复杂性的分类有个妙处，就是它非常稳定。比如说把计算量减缩1000倍，不可解决的问题仍然是不可解决。

　　了解了这些背景之后，核心问题来了：有没有可能通过改变计算机的物理体系，把不可解决的问题变成可以解决？

　　这是个非常有趣的问题。大家都知道，计算机可以用不同的物理体系来实现。从古代的算筹、算盘到近代的机械式计算机，再到现代的电子管计算机与晶体管计算机，硬件在不断演化。但是，这种进步能不能改变计算复杂性呢？

　　回答是不能，因为这些进步的效果只是让计算的每一步变得更快，但原来需要多少步现在还是需要多少步。所以不可解决的问题仍然是不可解决，不会因为你从算盘进步到超级计算机就改变这个定性。这个命题非常重要，它有个正式名称“扩展的丘奇-图灵论题”（extended Church-Turing thesis），丘奇和图灵是两位伟大的数学家。

　　阿隆佐·丘奇（Alonzo Church，1903 - 1955）

　　阿兰·图灵（Alan Mathison Turing，1912 - 1954）

　　但近40年来，出现了一个石破天惊的新回答：有一种新的物理体系有可能把不可解决的问题变成可以解决，它就是——量子计算机！

　　对于完全没有基础的同学，我来稍微解释一下。量子这个词来自量子力学，量子力学是一种基础物理学理论。跟量子相对的传统方法，叫做“经典”。量子之所以有可能做到经典做不到的事情，是因为量子力学有三个违反日常直觉的性质（让中央集体学习的量子科技究竟是啥？这个科普我已经做了五年（二）量子力学三大奥义 | 袁岚峰）：叠加、测量和纠缠（让中央集体学习的量子科技究竟是啥？这个科普我已经做了五年（三）量子纠缠 | 袁岚峰）。

　　量子计算机的逆天之处在于，它有可能通过执行某种快速的量子物理过程，获得跟这个过程对应的数学难题的解。用经典计算机计算这个数学问题的时间是指数时间，用物理过程获得结果的时间却是多项式时间。这种“抄捷径”，就是量子计算机的优势。

　　所以量子计算的重要性，在于它可能解决传统无法解决的问题，而不是以另一种方式去解决那些已经解决的问题。如果你理解到这一层，你的知识水平就超过了99%的人。

　　人们已经提出了若干种量子算法，每个算法其实就是对某个问题设计出的捷径。例如用经典算法分解因数是困难的，但用量子算法分解因数是容易的（让中央集体学习的量子科技究竟是啥？这个科普我已经做了五年（四）量子因数分解与破解密码 | 袁岚峰）。所以在理论层面，量子计算的形势大好。

　　不过真正的困难在实验层面：我们真的能实现这种优势吗？我们能不能造出一台量子计算机，它在至少一个问题上超越经典计算机？

　　对此的回答，绝不是显而易见的。在真正造出一台这样的量子计算机之前，不能排除这样的可能：这件事在理论上似乎可行，但在实践中总是因为各种各样的障碍而无法实现。

　　如果各种技术方案总是功败垂成，那么人们就会想：有没有可能，在这背后有某种深刻的原理在阻止我们超越经典计算机？这些都是需要实际去做才能知道的。

　　了解了这些背景，终于可以解释九章做的是什么了：它是目前最明确的超越经典计算机的量子计算机。用术语来说，这叫做实现“量子优越性”（quantum advantage）或者“量子霸权”（quantum supremacy）。

　　九章实现量子优越性之后，合理的推断就是：既然有一个问题可以实现量子优越性，当然就可以有更多。验证了这个存在性之后，我们的天地就无限广阔了。如果你理解到这一层，你的知识水平就超越了99.9%的人。

　　回想一下前面说的扩展丘奇-图灵论题，九章就是推翻这个论题的最强有力的证据。换句话说，九章让整个量子计算学术界建立了信心。

　　下面，我们来介绍九章具体执行的任务。它叫做“玻色子取样”（boson sampling），即发出若干个光子，经过复杂的光路后，探测每一个出口有多少个光子出去。一个流行的比喻是，它好比光子的“高尔顿钉板”（Galton’s board）。

　　阿伦森与阿尔希波夫论文图1，高尔顿钉板

　　提出玻色子取样的，是一篇2013年的论文《线性光学的计算复杂性》（The Computational Complexity of Linear Optics），作者是斯科特·阿伦森（Scott Aaronson）和他的学生亚历克斯·阿尔希波夫（Alex Arkhipov）。阿伦森当时是MIT电子工程与计算机科学系的教授，现在是德州奥斯汀大学计算机科学系的教授。这篇文章的图1，就是高尔顿钉板。

　　斯科特·阿伦森（https://www.cs.utexas.edu/people/faculty-researchers/scott-aaronson）

　　然而玻色子取样真正的威力，是它跟高尔顿钉板的区别。高尔顿钉板的球是经典粒子，各个球之间是独立的。但玻色子取样的光子是量子粒子，它们之间是会干涉的。

　　平时常见的光的干涉现象，是单个光子自己跟自己干涉。但玻色子取样实验中的多个光子之间会发生多光子干涉，导致更奇妙的效应。

　　用物理学术语来说，这叫做“Hong-Ou-Mandel凹陷”（Hong-Ou-Mandel dip）。这三位作者都是罗切斯特大学的物理学家，Hong是韩国人洪廷基（Chung Ki Hong），Ou是华人区泽宇。

　　他们在1987年发现，两个相同的光子在同时经过一个分束器之后，会变得纠缠起来。最初这两个光子一个从左边来，一个从右边来。经过分束器之后再去测量它们，就会发现或者两个都在左边，或者两个都在右边，但不可能一个在左一个在右。阿伦森与阿尔希波夫论文的图3，就是这个Hong-Ou-Mandel凹陷。

　　阿伦森与阿尔希波夫论文图3，Hong-Ou-Mandel凹陷

　　这是一种纯粹的量子力学效应，在经典世界里是不可能出现的。玻色子取样，就是把Hong-Ou-Mandel凹陷推广到更多的光子。最终，从各个出口出来的光子会满足一个非常复杂的分布，如下图所示。

　　玻色子取样的概率分布

　　最下面那个公式（3.66），就是玻色子取样的概率分布。这个公式中分子上的Per(As)，是As这个矩阵的“积和式”（permanent）。分母上的s1!直到sm!，是s1直到sm的阶乘（factorial）。

　　如果你不知道积和式和阶乘是什么，请去看我以前的文章和视频（量子计算机不是计算机？键盘侠们会对美国这样说吗？| 袁岚峰）。重点在于，积和式的计算是一个困难的问题，所以这个概率分布对于经典计算机是困难的。如果我们能把光子数推到足够大，超级计算机已经算不动了，而物理装置仍然能够快速取样，那么就实现了量子优越性。

　　这需要达到多少个光子呢？阿伦森和阿尔希波夫的估计是，到20至30个光子就可能超越经典计算机。

　　九章实际做到了多少呢？平均光子数是43，最多达到76，远远超过预期。所以最终的结果是：九章用200秒取样了5千万次，而现在最强的超级计算机取同样多的样需要6亿年，九章超过了它一百万亿倍！

　　我们来总结一下，九章的重要性至少包括三个层面。

　　在原理层面，它是推翻扩展丘奇-图灵论题的现有最强的证据。

　　你也许想问，不扩展的丘奇-图灵论题说的是什么？回答是，原始的丘奇-图灵论题说的是，任何物理体系可计算的数学问题都是一样多的。而扩展的丘奇-图灵论题，说的是任何物理体系可有效计算的数学问题都是一样多的。请注意，可计算和可有效计算是不一样的。前者是指可以在有限的时间内得出结果，无论这个时间是多长，而后者是指这个时间是多项式增长的。

　　现在普遍认为丘奇-图灵论题是正确的，而扩展丘奇-图灵论题是错误的。也就是说，量子计算机和经典计算机可计算的问题是一样的。但在这些可计算的问题中，量子计算机可以把一些不可有效计算的问题变成可以有效计算。

　　在实用层面，玻色子取样目前还没有实用价值，但将来可能会有。例如药物分子筛选对应某种图论问题，而这种图论问题又可能对应玻色子取样问题，因此将来有可能用九章加快药物研发。如果我们真的通过这种方法制造出了新药，难道会有人因为所谓“它不是计算机”而拒绝吃药吗？

　　在技术层面，中国科学家在研发九章的过程中发展了大量的新技术，如最好的量子光源、最好的干涉技术、最好的锁相技术、最好的单光子探测器等等。这些技术会扩展到其他地方，例如量子雷达（高空大气与量子雷达 | 窦贤康）、量子卫星、“隔墙观物”（千米之外，如何实现隔墙观物 | 墨子沙龙）和“雾里看花”（单光子相机：如何实现“雾里看花” | 徐飞虎）。

　　如果以上这些你全都理解了，我相信你的知识水平已经超越了99.99%的人。回头再看各种常见的对量子计算机的误解，你都能够一眼看破。

　　最后，对于一个新科技，我们有两种态度。一种是：我不懂，也不想学！这东西肯定不行！你们肯定是假的！另一种是：我要去认真学习，了解原理，甚至投身其中。你愿意选择哪一种呢？