“九章”问世：量子计算机究竟有多快（一）

　　出品：新浪科技《科学大家》、墨子沙龙

　　撰文：彼得·秀尔（Peter Shor），美国麻省理工学院数学系教授

　　日前，中国科学技术大学潘建伟、陆朝阳等学者组成的研究团队与中国科学院上海微系统所与信息技术研究所、国家并行计算机工程技术研究中心合作，构建了76个光子的量子计算原型机“九章”。计算玻色采样问题，“九章”处理5000万个样本只需200秒，而目前世界最快的超级计算机需要6亿年。

　　在新闻报道中，都会将“九章”和超算的计算速度作对比，但实际上，量子计算机和超算存在实质性的不同，远不止计算能力上的差别。

　　量子计算机的“计算”有何不同？

　　计算机和物理实验有什么不同呢？有很多可能的答案，其中一个就是：电脑能回答数学问题， 而物理实验回答物理问题。比如说，如果要分解一个很大的数字， 一个好办法是用计算机来计算；而如果想要测试所有物体是否以相同的速率下降， 这时不会用电脑， 而是像图中的伽利略那样，用两台不同的计算机测试它们是否会以相同的速度下落。

　　另一个答案是：物理实验是一个非常大的定制仪器，也许会占据整间屋子， 而计算机就是一个小盒子，可以放在桌子上或公文包里。

　　不过时间若是回到上世纪五六十年代，计算机刚刚问世的时候，你能分辨出图中哪个是计算机，哪个是加速器吗？

　　其实图片中左边这个是粒子加速器，位于上世纪60年代的劳伦斯伯克利实验室，而右边这个是神奇的ENIAC，它是上世纪五十年代发明的世界上第一台计算机，位于宾夕法尼亚大学。这两台仪器都体积巨大，但之后计算机的体积越来越小，而粒子加速器却越来越大。为什么会这样呢？这是因为人们不需要针对每个数学问题都建造一台新的计算机。这意味着建造计算机的人可以进行大规模生产，使它们可以越来越高效，越来越便宜，越来越小。而做物理实验的人每当遇到以前的实验结果无法回答的问题时，就只能设法突破物理实验的极限，就比如越来越大的加速器。

　　计算理论始于20世纪30年代，那时候计算机还没有发明。上世纪三十年代，在数学逻辑方面，哥德尔证明了著名的不完备性定理，即并非所有的数学命题都能证明是真或是假，所以有些数学问题是无法得到答案的。计算数学与计算机科学密切相关，在哥德尔证明了这个定理六年之后， 四位科学家区分了可计算函数和不可计算函数的定义， 这些研究都源于哥德尔的理论。如果阅读这些论文就会发现，它们包含三种对可计算函数的不同定义。而可计算函数的这三种定义都给出了可计算函数是完全相同的事实，这就引出了邱奇图灵论题。

　　论文作者认为 “丘奇-图灵论题”是对的。这个图灵机可以执行任何设备上的任何计算，这也是计算机的原始模型，它可以很很轻松的处理数学问题。

　　那么，任何设备是什么意思呢？图灵和邱奇并没有想到的一点是：这是一个我们可以在真实世界中建造和运行的机器。 这样它就是一个物理问题，而不是数学问题了。随着实用计算机的发展， 不可计算函数和可计算函数的定义界限变得越来越不清晰。因为有的函数理论上是可以计算的，但需要非常长的时间来进行计算而且价值也不高，因此一个有效的程序必须要在合理的时间内完成计算。

　　所以什么是合理的时间呢？你也许会问在一个超级计算机上用一年时间进行计算合理吗？但是从数学的角度来说这是非常糟糕的， 所以一些理论计算机学家认为， 要在理论和实际中进行妥协。他们认为一个有效的算法应该满足以下条件：它的运行时间必须是在多项式时间以内， 比如N，N的平方，N的立方，N的一万次方等等， 而不是2的N次方这种指数级时间。

　　所以把能在多项式时间内求解的一类问题称为P。一个需要说明的事实是，大多数的函数属于P类问题，这说明大部分算法都是有效的。为了使定义更加有意义， P不应该依赖于何种计算机类型。

　　这就使得一些计算机科学家提出了量化丘奇论题。当然它也有许多其他叫法，但都指的是：图灵机可以有效的执行任何计算任务。量化丘奇论题首先是由Alan Cobham在1965年提出的。因数分解算法对计算机科学家的重要影响在于，它将显示这个“民间论题”（量化丘奇论题）是错误的。