crvdgc
crvdgc

九章:真的是快一百亿倍的量子计算机吗

本文首发于: https://crvdgc.github.io/2020/12/07/jiuzhang/

新华网报道,中科大潘建伟团队制作的新量子计算机九章,比谷歌量子计算机快一百亿倍。本文将从计算理论的角度来说明,该如何理解这一结论。

首先一个重要的问题是,九章是量子计算机吗?九章的确有电子元件,并且使用了量子效应,可以执行一个量子算法,为何不能称为量子计算机呢?

要回答这个问题,首先可以考虑一下,耳机是计算机吗?毕竟耳机内部也包含电子元件,并且完成了将电流信号转化成声音信号的算法,但我们通常不将耳机称为电子计算机,而只是电子机器。是什么将耳机和电脑区别开来呢?

我们知道,不同的机器可以执行不同的功能。我们的生活中有很多专用机器,比如收银机、汽车的刹车辅助系统、导弹的制导系统等等。它们都有不同的结构,完成各自的专用任务。如果没有一项发现的话,也许人们直到现在也得为每一项不同的任务设计一个新的专用机器。1933年前后,英国数学家阿兰·图灵以及其他数学家意识到,在不同的计算任务背后,隐藏着一个相同的抽象结构[1]。对这种抽象结构的各种表述中,以图灵的图灵机最广为人知。

简单来说,图灵机就是一个概念上的机器,根据自身的结构,在一个无限长的纸带上完成读写信息的任务。一个最简单的图灵机例子就是计算生成1/3的小数表示,只需按下面两个步骤执行即可:

  1. 在纸带上打印「0」和小数点。
  2. 不断在纸带上打印「3」。

运行这个机器,就可以在纸带上得到结果「0.3333……」。当然,图灵所使用的模型更加抽象,只包含一些基本操作,并且使用二进制编码,但这些都不影响原理上的讨论。图灵在论文中还给出了一个计算圆周率π的图灵机。每一个的图灵机就如同现实中的专用机器一样,它们都有自己的专门任务。正如一个收银机无法完成导弹的制导一样,一个计算1/3的图灵机,无法完成计算π的任务。

但图灵接下来的结论让人十分震惊:通过对图灵机的操作也进行编码,图灵将每个专用的图灵机都转化成了一系列指令。接着,他证明了存在一个通用图灵机(Universal Turing Machine),只要把某个专用图灵机对应的指令放进去,它就能表现得像那个专用图灵机一样。换句话说,通用图灵机可以模拟任何的专用图灵机,因此才被称为是通用的(universal)。

这个结果其实十分有趣。通用图灵机可以用很少的部件制作而成(事实上,图灵在论文中给出了一个完整构造,从而证明了通用图灵机的存在),但却能「模仿」无穷无尽的专用图灵机。现在的每个人对这些概念其实十分熟悉:因为每一个电脑、手机都是通用图灵机,而不同的软件就是不同专用图灵机的指令。电脑不仅可以计算1/3和π,还能通过执行音乐播放器软件,做到原来一台专门的MP3机器才能做到的事情。对此,人们已经习以为常,并不觉得奇怪。但如果仔细考虑一下的话,电脑的灵活性的确很令人惊讶。

这也就回答了上面,耳机和电脑之间的区别。只有当一台机器能执行通用计算任务的时候,我们才将它称为计算机。耳机虽然能高效地完成一项特定的计算任务,但因为不具有通用性,我们并不将其称为计算机。一个更贴近生活的例子是,印章可以快速地复制一个图案,但如果想要复制任意图案的话,还是需要一台通用性更强的复印机。

类似的,九章其实是一个量子机器,而不是一个量子计算机。为何这么说呢?

对应于经典算法,计算机科学家为量子计算任务设计了一套「编程语言」,称为量子电路(quantum circuit)。令人们感兴趣的量子计算任务,都可以使用一个量子电路来描述。当然,我们可以将每一个量子电路都实际用器件搭出来,形成一个专门的物理量子电路,但这样就太麻烦了。

在制作经典电路时,计算机科学家为了简化器件的种类,发现了任何逻辑电路都可以使用与、或、非三种逻辑门来实现。换句话说,只需要做出三种器件,再用一定的方式将它们组合到一起,就可以完成任意逻辑电路的功能。有了任意的逻辑电路,就可以很轻松地做出物理上的通用图灵机了。接下来,如果想让这台机器解决什么问题,我们只需要为它编程就好。

类似的,计算机科学家发现,任意的量子电路都可以转化为由单量子比特门和 CNOT 门构成的电路[2]。也就是说,只需要做出能实现这两个门的器件,再通过一定方式将它们组合到一起,就可以实现通用的量子计算(现实中因为噪音会更复杂一些)。这就是开头那篇新闻报道中所说的,谷歌的量子计算机实现的「随机线路取样」。实际上,任何其他的量子计算机,指的都是可以做到执行任意量子电路的计算系统。很少有人将不能进行通用量子计算的系统,称为「量子计算机」。

那么九章用来展示「量子优越性」(quantum supremacy)的「高斯玻色取样」是什么呢?简单来说,就是预测一个光量子系统演化的结果[3]。用经典计算机模拟量子系统十分复杂,因此量子计算机概念最早提出者之一的物理学家理查德·费曼就设想,量子计算机的一大应用就是模拟量子系统本身。但问题的关键在于,拥有一台通用的量子计算机,可以模拟任意专门的量子系统(只不过速度可能很慢),但拥有一台专门的模拟一种量子系统的机器,并不等于能完成其他的量子计算。

就我个人理解,并非任意量子电路都可以转化为「高斯玻色取样」。因此,「悬铃木」以及其他所有量子计算机的通用性,都严格高于九章。事实上,我不知道任何有意思的问题(比如密码学、机器学习)可以编码成为「高斯玻色取样」问题,而它们全都能编码成为通用的量子电路,并可以在量子计算机上运行。因此,很可能九章只是再次证明了这样一个事实:用经典计算机模拟量子系统很困难。这一事实虽然广为人知,但这次使用实验证明了这一点。九章选取了一个困难、但可能没有应用价值的问题,证明了它的确很困难。

举例来说就是,对于下面的弹球机,请预测不同力度弹出的小球最终的结果如何?

弹球机(来源:wikimedia)

如果使用计算机模拟的话,可能需要仔细建模小球、弹杆、还有机器内部的状态等等,十分复杂。另一个更「高效」的计算方法是,直接拿一台这样的机器,用给定的力度弹出,最后汇报结果。后一种方法可能的确比前面的快很多,但这个问题本身只是说明了物理系统模拟的困难性。并不是任意问题都可以编码成弹球机的小球结果。

报道中称,「无论是谷歌的『悬铃木』处理『随机线路取样』,还是『九章』求解『高斯玻色取样』,都只能用来解决某一个特定问题」,但我们可以看到,两个问题的重要性不可同日而语。毕竟我们也可以说,电脑和耳机都只能用来解决某一个特定问题:耳机只能将电信号转化为声音信号,电脑不过是可以通过重新编程模拟任何计算系统而已。

而报道中的另一个引人注目的数字是,「『九章』比『悬铃木』快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.

CC BY-NC-ND 2.0

Like my work?
Don't forget to support or like, so I know you are with me..

Loading...
1

Want to read more ?

Login with one click and join the most diverse creator community.