九章：真的是快一百亿倍的量子计算机吗
本文首发于： https://crvdgc.github.io/2020/12/07/jiuzhang/
据新华网报道，中科大潘建伟团队制作的新量子计算机九章，比谷歌量子计算机快一百亿倍。本文将从计算理论的角度来说明，该如何理解这一结论。
首先一个重要的问题是，九章是量子计算机吗？九章的确有电子元件，并且使用了量子效应，可以执行一个量子算法，为何不能称为量子计算机呢？
要回答这个问题，首先可以考虑一下，耳机是计算机吗？毕竟耳机内部也包含电子元件，并且完成了将电流信号转化成声音信号的算法，但我们通常不将耳机称为电子计算机，而只是电子机器。是什么将耳机和电脑区别开来呢？
我们知道，不同的机器可以执行不同的功能。我们的生活中有很多专用机器，比如收银机、汽车的刹车辅助系统、导弹的制导系统等等。它们都有不同的结构，完成各自的专用任务。如果没有一项发现的话，也许人们直到现在也得为每一项不同的任务设计一个新的专用机器。1933年前后，英国数学家阿兰·图灵以及其他数学家意识到，在不同的计算任务背后，隐藏着一个相同的抽象结构[1]。对这种抽象结构的各种表述中，以图灵的图灵机最广为人知。
简单来说，图灵机就是一个概念上的机器，根据自身的结构，在一个无限长的纸带上完成读写信息的任务。一个最简单的图灵机例子就是计算生成1/3的小数表示，只需按下面两个步骤执行即可：
- 在纸带上打印「0」和小数点。
- 不断在纸带上打印「3」。
运行这个机器，就可以在纸带上得到结果「0.3333……」。当然，图灵所使用的模型更加抽象，只包含一些基本操作，并且使用二进制编码，但这些都不影响原理上的讨论。图灵在论文中还给出了一个计算圆周率π的图灵机。每一个的图灵机就如同现实中的专用机器一样，它们都有自己的专门任务。正如一个收银机无法完成导弹的制导一样，一个计算1/3的图灵机，无法完成计算π的任务。
但图灵接下来的结论让人十分震惊：通过对图灵机的操作也进行编码，图灵将每个专用的图灵机都转化成了一系列指令。接着，他证明了存在一个通用图灵机（Universal Turing Machine），只要把某个专用图灵机对应的指令放进去，它就能表现得像那个专用图灵机一样。换句话说，通用图灵机可以模拟任何的专用图灵机，因此才被称为是通用的（universal）。
这个结果其实十分有趣。通用图灵机可以用很少的部件制作而成（事实上，图灵在论文中给出了一个完整构造，从而证明了通用图灵机的存在），但却能「模仿」无穷无尽的专用图灵机。现在的每个人对这些概念其实十分熟悉：因为每一个电脑、手机都是通用图灵机，而不同的软件就是不同专用图灵机的指令。电脑不仅可以计算1/3和π，还能通过执行音乐播放器软件，做到原来一台专门的MP3机器才能做到的事情。对此，人们已经习以为常，并不觉得奇怪。但如果仔细考虑一下的话，电脑的灵活性的确很令人惊讶。
这也就回答了上面，耳机和电脑之间的区别。只有当一台机器能执行通用计算任务的时候，我们才将它称为计算机。耳机虽然能高效地完成一项特定的计算任务，但因为不具有通用性，我们并不将其称为计算机。一个更贴近生活的例子是，印章可以快速地复制一个图案，但如果想要复制任意图案的话，还是需要一台通用性更强的复印机。
类似的，九章其实是一个量子机器，而不是一个量子计算机。为何这么说呢？
对应于经典算法，计算机科学家为量子计算任务设计了一套「编程语言」，称为量子电路（quantum circuit）。令人们感兴趣的量子计算任务，都可以使用一个量子电路来描述。当然，我们可以将每一个量子电路都实际用器件搭出来，形成一个专门的物理量子电路，但这样就太麻烦了。
在制作经典电路时，计算机科学家为了简化器件的种类，发现了任何逻辑电路都可以使用与、或、非三种逻辑门来实现。换句话说，只需要做出三种器件，再用一定的方式将它们组合到一起，就可以完成任意逻辑电路的功能。有了任意的逻辑电路，就可以很轻松地做出物理上的通用图灵机了。接下来，如果想让这台机器解决什么问题，我们只需要为它编程就好。
类似的，计算机科学家发现，任意的量子电路都可以转化为由单量子比特门和 CNOT 门构成的电路[2]。也就是说，只需要做出能实现这两个门的器件，再通过一定方式将它们组合到一起，就可以实现通用的量子计算（现实中因为噪音会更复杂一些）。这就是开头那篇新闻报道中所说的，谷歌的量子计算机实现的「随机线路取样」。实际上，任何其他的量子计算机，指的都是可以做到执行任意量子电路的计算系统。很少有人将不能进行通用量子计算的系统，称为「量子计算机」。
那么九章用来展示「量子优越性」（quantum supremacy）的「高斯玻色取样」是什么呢？简单来说，就是预测一个光量子系统演化的结果[3]。用经典计算机模拟量子系统十分复杂，因此量子计算机概念最早提出者之一的物理学家理查德·费曼就设想，量子计算机的一大应用就是模拟量子系统本身。但问题的关键在于，拥有一台通用的量子计算机，可以模拟任意专门的量子系统（只不过速度可能很慢），但拥有一台专门的模拟一种量子系统的机器，并不等于能完成其他的量子计算。
就我个人理解，并非任意量子电路都可以转化为「高斯玻色取样」。因此，「悬铃木」以及其他所有量子计算机的通用性，都严格高于九章。事实上，我不知道任何有意思的问题（比如密码学、机器学习）可以编码成为「高斯玻色取样」问题，而它们全都能编码成为通用的量子电路，并可以在量子计算机上运行。因此，很可能九章只是再次证明了这样一个事实：用经典计算机模拟量子系统很困难。这一事实虽然广为人知，但这次使用实验证明了这一点。九章选取了一个困难、但可能没有应用价值的问题，证明了它的确很困难。
举例来说就是，对于下面的弹球机，请预测不同力度弹出的小球最终的结果如何？
如果使用计算机模拟的话，可能需要仔细建模小球、弹杆、还有机器内部的状态等等，十分复杂。另一个更「高效」的计算方法是，直接拿一台这样的机器，用给定的力度弹出，最后汇报结果。后一种方法可能的确比前面的快很多，但这个问题本身只是说明了物理系统模拟的困难性。并不是任意问题都可以编码成弹球机的小球结果。
报道中称，「无论是谷歌的『悬铃木』处理『随机线路取样』，还是『九章』求解『高斯玻色取样』，都只能用来解决某一个特定问题」，但我们可以看到，两个问题的重要性不可同日而语。毕竟我们也可以说，电脑和耳机都只能用来解决某一个特定问题：耳机只能将电信号转化为声音信号，电脑不过是可以通过重新编程模拟任何计算系统而已。
而报道中的另一个引人注目的数字是，「『九章』比『悬铃木』快100亿倍」。那么这个数字是怎么算出来的呢？报道中说，是与「最快的超算等效比较」而得出的。也就是说，如果「悬铃木」比某一个超算快N倍的话，九章则快100亿N倍。但上面的分析已经指出，二者并没有从事相同的计算任务，因此这样的比较很难有什么实际意义。比如，我们可以选取一个无法被编码为「高斯玻色取样」的量子计算问题，比如 Shor 算法[4]，它可以在「悬铃木」上经过一段时间得出结果。但因为九章并非通用量子计算机，它根本无法解决这个问题，此时讨论速度意义不大。
总而言之，「『九章』比『悬铃木』快100亿倍」，就好像在说，印章的速度比复印机快十倍一样。对于复制印章上的图案而言，的确如此。但后者的通用性远高于前者，而且前者的印章印出来的还很可能是一个没人需要的图案。
参考资料：
[1]: Turing, Alan Mathison. "On computable numbers, with an application to the Entscheidungsproblem." Proceedings of the London mathematical society 2.1 (1937): 230-265.
[2]: Nielsen, Michael A., and Isaac Chuang. "Quantum computation and quantum information." (2002).
[3]: https://www.sciencenews.org/article/new-light-based-quantum-computer-jiuzhang-supremacy
[4]: Shor, Peter W. "Algorithms for quantum computation: discrete logarithms and factoring." Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.