误解带来的乐观与恐慌

我们用了之前四期的时间从工程，功耗，时空概念及复杂理论讨论了计算机的极限以及面对这些极限科学家们所采取的措施。本期文章是讨论计算机极限的最后一篇，我们将跳出传统计算机的领域，从新兴科技的角度入手，通过对其极限的讨论，打破多年来人们对他们的误解。

基于前四期所说到的传统计算机所面临的极限，当下计算机的研究越来越多地跳出了传统计算机的范畴。其中最热门的莫过于量子计算机。

对量子计算机的热捧让我们觉得量子计算机即将通过强大的计算能力取代传统计算机并解决所有之前传统计算机无法解决的问题。普通用户渐渐地有了拥有一台量子计算机的愿景。而传统计算机架构师们渐渐地对量子计算机心生恐慌，害怕量子计算机的横空出世让自己多年的研究变得不值一提。

然而这项科技的的发展真会如我们所料给这个社会带来翻天覆地的变化吗？用百度高级架构师欧阳剑在2017年计算机体系结构会议ASPLOS上讲的一句话来总结，当下这些科技发展确实快，然而之中有真切的发展，更有舆论的泡沫。那我们就来看看量子计算机到底在多大程度上影响了计算机的发展。（本文仅对量子计算机的极限作讨论，对其原理的解释和当下量子计算机发展的程度，读者可参照往期原理的文章）

量子计算这一概念在1969年被史蒂芬·威斯纳首先提出，并将其列入了他1983年发表的论文中[1]。论文发表的前一年，理查德·费曼在一次公开演讲中也提出了利用量子体系实现通用计算的想法。而这一想法在1985年大卫·杜斯提出的量子图灵机模型中首次得到了验证[2]。当时人们研究量子计算机的初衷是为了模拟量子现象，服务于物理学。当使用计算机模拟量子现象时，由于庞大的希尔伯特空间所带来的庞大数据分析使得一次模拟所需运算时间变得相当长，甚至可能穷科学家一生也看不到一次完整的结果。于是量子计算机的研究应运而生。

量子计算因其叠加和纠缠的特性对传统计算做了极大的扩充。量子计算机对每一个叠加分量实现的变换相当于一种经典计算，所有这些传统计算同时完成，并按一定的概率振幅叠加起来，给出量子计算机的输出结果。这种计算称为量子并行计算[3]。

从80年代的以理论推导为主的研究，到九十年代彼得·秀而提出量子质因式分解算法[4]，到D-Wave公司发布的D-Wave One 量子模拟器，再到如今谷歌，IBM从上层编程语言到底层电路设计的一整套对通用量子计算机研究成果，量子计算机的研究可谓是飞速发展。

然而人们对其技术本身的误解，在媒体的放大下给了人们一种量子计算机将无所不能的印象。经济学人杂志在2007年2月15日的期刊里曾说道：“量子计算机将通过并行处理所有可能性的方式在理论上可以有效解决NPC集合的问题（关于NPC集合问题的讨论请参见《价值百万美金的问题》）”。

D-Wave 公司在2009年时发布制造了128位的量子计算机的大新闻，很快受到了业界的反驳与指责[5][6]。就连2017年中国制造的光量子计算机在发布后也受到了褒贬不一的舆论。那么量子计算机的极限到底在哪儿呢？本文将从有效计算和计算能力两个方面来讨论。

我们先来看量子计算机能够有效（在多项式级时间里）解决怎样的问题。在《一个无法证明的逻辑问题》 一文中我们提到了图灵机的概念。图灵把所有问题分成了可判定（decidable) 和不可判定（undecidable) 两种。而图灵机只考虑可判定的问题集合。上一期中，我们把可判定的问题集合按照其复杂度分成了了P类，NP类和NPC类的问题。这些问题的关系可由图一表示。

△ 图一：复杂度问题的分类。

其中PSPACE类是指传统计算机可以用多项式级复杂度的内存通过非多项式级复杂度的时间解决的问题集合(包括象棋对弈等）。现在能用传统计算机有效解决的仅仅是P类问题，例如测试一个数是否是质数，或冒泡排序等。注意笔者所说的有效解决是指在多项式级时间内解决，并不代表传统计算机只能解决该类问题。实际上作为图灵机，传统计算机可以解决所有的可判定问题（即PSPACE集合内所有的问题），只是所需时间的长短不同罢了。

那么媒体所说的用量子计算机有效解决NPC问题是否可行呢？答案是否定的。其实时至今日，计算机科学家们能找到的通过量子计算的特点将NP类问题转化为P类问题的算法也是寥寥无几，而其中最常见的就是阶层的计算。也就是说，能利用到量子计算特性来有效解决传统计算机无法有效解决的程序其实并不多。在量子计算机只能有效解决少数NP问题的当下，NPC问题并不能靠量子计算机得到有效地解决[5]。

原因很简单，因为该类问题其实是一个黑匣子，而我们只能通过猜答案并验证的方式来得到结果（而非对其进行直接计算）。举个例子，如果一个问题有 s 种可能的答案，s 的大小随着问题输入的大小呈指数增长。我们在运气逆天的情况下能一次猜中答案，而在人品欠佳的时候我们需要试 s 次之后得到答案。也就是说，传统计算机需要平均 s/2 次试错来解决这类问题。

现在我们把这类问题放到量子计算机上来。Lov Grover在1996年的论文中找出了用量子计算通过 √s 步来获得该类问题答案的算法[7]。从 s/2 次到 √s 次的试错在很多情况下确实会带来客观的速度提升。比如在100万可能性中我们可以从之前的平均50万次试错减少到1000次，但即便是 √s 也只是较简单的指数级复杂度，并非是多项式级的复杂度（因为s仍然会随着问题输入的大小呈指数增长）。

而早在在2002年，Scott Aaronson就指出该类问题如果用上述的黑匣子试错的方式解决，即便是量子计算机也无法在多项式级复杂度的时间里解决[8]。正如上期文章中提到的，解决NPC类的算法是否存在到现在仍未得到证实，但可以肯定的是，单用量子计算机的特性是无法有效解决这类问题的。于是Scott Aaronson在现有的复杂度理论上提出了一个新的集合，并命名为BQP类问题（Bounded-error, Quantum, Polynomial）。

△ 图二：量子计算机能解决的BQP类问题。

如图二所示，BQP类问题包含了所有P类问题和少数NP类问题，值得注意的是，BQP类的问题包含了一些非NP类的问题。也就是说有那么一些问题用量子计算机解决所花的时间会比传统计算机验证该类问题所花的时间更少。但无论如何，解决BQP类问题，就是量子计算机所能达到的极限。支持P≠NP结论的计算机科学家们同理抱持着量子计算机无法解决NPC类问题的信念。

1998年Daniel Abrams在论文中提到如果在量子力学的公式中加入一项非线性的特性，量子算计机就能有效地解决NPC类的问题[9]。但如果加入的这一项非线性特征如果成立，那么海森堡的不确定性原理将就此被推翻，信息传输也将突破光速的限制。正如Daniel Abrams在文中提到，这一特性恐怕只能用来理解为什么量子力学无法存在非线性特性了。换言之，这个理论也也从旁佐证了量子计算机解决NPC类问题的不可行性。

当然值得注意的是，虽然BQP类问题包含了所有P类问题，也就是说传统计算机能解决的问题量子计算机都能解决，但这并不代表着量子计算机在所有程序的运行都能快过传统计算机。只有适合用量子算法的问题才能使量子计算机的运行速度超过传统计算机。

再从计算能力来看量子计算机和传统计算机的差别。这里计算能力是指量子计算机是否能超越图灵机，做到传统计算机无法做到的事情。早在八十年代量子计算机理论还处在推到阶段的时候，物理学界曾做过这样一个关于封闭类时曲线（Closed Timelike Curve，CTC）的思想实验。CTC实际可以看做成一个时间闭环，让任何时间发展结果的时间点和其开始的时间点相重合。假设我们有一台计算机，能在无所谓多长但有限时间内完成计算之后将计算结果送回到计算开始的时间，那么一切NPC甚至更复杂的问题都会迎刃而解。

当然这个思想实验存在和“祖父悖论”相同的矛盾，例如如果在计算结果送回之后你关掉了计算机会出现什么等等。虽然物理学家大卫·多伊奇（David Deutsch）在1991年通过对平行宇宙的解释巧妙地避开了这个问题，对CTC的研究仍然停留在假想阶段。然而假想的实验并不能阻止计算机科学家们对量子计算机极限的探讨。2008年Scott Aaronson再次发表论文[10]，在假设CTC存在的情况下得出量子计算机和传统计算机等价的理论。也就是说即便是CTC存在，量子计算机的计算能力也无法解决超出PSPACE类问题。换句话说，量子计算机就其本质来说和图灵机并无差别。

本文从计算的有效性及计算能力两个方面讨论了量子计算机的极限。总结来说，从计算有效性来看，量子计算机能够有效解决一些传统计算机无法有效解决的问题，比如阶层的计算。但目前已知可归纳到这一类的问题并不多。而从计算能力来看，量子计算机的本质和图灵机并无差别，并不能解决不可判定的问题。一切对新兴科技过度的乐观和不必要的恐慌都来自于对其本身的误解。当然量子计算机的极限并没有阻止科学家们对NPC问题的探究，如果计算机理论暂时无法解决这些复杂度的问题，希望物理学界能在未来的某一天对这些问题作出结论。

作者：道法自然（孙鹏，剑桥大学计算机系在读博士）

参考文献：

[1]. Wiesner, S, “Conjugate Coding”, Sigact news, 18: 78–88, 1983.

[2]. David Deutsch, “Quantum theory, the Church-Turing principle and the Universal Quantum Computer”, Proc. R. Soc. Lond.

[3]. https://en.wikipedia.org/wiki/Quantum_computing

[4]. Shor, Peter W.（1997）, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26 (5): 1484–1509

[5]. Scott Aaronson, “The Limit of Quantum,” Scientific Amarican, 2008

[6]. Erico Guizzo, “Loser: D-Wave Does Not Quantum Compute,” IEEE Spectrum, Dec 2009.

[7]. Lov K Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” Quantum Physics, v3, 1996.

[8]. Scott Aaronson, “Forrelation: A Problem that Optimally Separates Quantum from Classical Computing,” STOC’15, June 14–17, 2015, Portland, Oregon, USA.

[9]. Daniel S. Abrams and Seth Lloyd, “Nonlinear Quantum Mechanics Implies Polynomial Solution for NP-complete and #P Problems,” Quantum Physics, Phys.Rev.Lett. 81 (1998) 3992-3995.

[10]. Scott Aaronson and John Watrous, “Closed Timelike Curves Make Quantum and Classical Computing Equivalent,” Quantum Physics, arXiv:08082669. 

欢迎关注《走进计算机文化史》的系列文章：