| 编者按 |
12月7日，谷歌D-Wave研究组在arXiv.org上传了一篇文章，声称其在2013年购买的D-Wave机器在解决某类特定问题的速度是经典计算机的10^8倍。
这究竟是炒作还是货真价实的大新闻？D-Wave是量子计算机吗？而所谓的“一亿倍”的加速又是怎么回事？
D-Wave是加拿大的一家公司。2010年，D-Wave宣布开始生产世界上第一台商用量子计算机。量子计算机被认为有希望比经典计算机更快解决地解决一些问题，对于一些问题，例如大整数的因子分解，它与已知的经典算法相比有指数级的速度提升。
事实上，D-Wave问世至今，针对它的讨论此起彼伏，从未停止过。一些意见认为，D-Wave机器是否真的利用量子现象实现计算还不确定，它是否比经典计算机更有优势也不确定。
Scott Aaronson，美国麻省理工学院电子工程与计算机科学副教授，曾一度担任“D-Wave首席怀疑官”（Chief D-Wave Skeptic）。两年前，他在其博客上发表了一篇《D-wave: 最终，真相开始浮出水面》（D-Wave: Truth finallystarts to emerge），对相关的讨论进行了总结，并号召人们用科学理性的态度认识D-Wave所达到的成就。
因此，在经历两年的“风平浪静”之后，关于D-Wave的新闻一经出现，很多业内人士的目光便都转向了Scott。让我们来看看这位曾经的“D-Wave首席怀疑官”对此会有怎样的反应吧。
撰文 | Scott Aaronson
翻译 | 张林峰
校译 | 林梅、刘丁、陈明城
编者注：由于文章本身的专业性，我们首先解释其中的核心概念和观点如下：
（1）模拟退火：模拟退火是一种通用的经典概率算法，用来在固定时间内在一个搜索空间内找到最优解。其原理与金属退火的原理类似，遂得此名。其解依概率收敛到全局最优解。
（2）量子退火：模拟退火的“量子”版本。不同的是，经典模拟退火依赖的是逻辑运算，量子退火需要依赖量子力学特有的“隧道效应”，更像是让“大自然”自己去运算。
（3）量子蒙特卡罗（QMC，Quantum Monte Carlo）：是一种用来寻求量子体系基态的经典算法。蒙特卡罗方法本身是指使用随机数（或者更常见的伪随机数）来解决很多计算问题的方法。
（4）时间复杂度：是指算法在编写成可执行程序后，运行时所需要的时间资源。时间复杂度在数学上有更为严格的定义。一般人们关心的时间复杂度是指运行时间随问题规模增加的渐近行为。因为“非渐近”的行为会随问题规模的增大而显得不重要。特别的，如果该渐进行为是多项式（Polynomial，P）的，那么人们认为这一算法是有效的。对于一些问题，经典算法尚未发现有多项式的，而有人提出了多项式的量子算法（例如针对大整数因子分解的Shor算法）。
（5）最新D-Wave文章中展示的两个1亿倍加速：第一个1亿倍是“量子退火”与“模拟退火”相比的1亿倍渐进的加速，对此，该文章同样也指出与“量子蒙特卡罗“这一经典算法相比，”量子加速“并不明显。第二个1亿倍是在D-Wave上运行“量子退火”算法与在单核经典计算机上运行“量子蒙特卡罗”算法相比的1亿倍常数的加速。这种常数加速可能会受问题规模和计算机性能本身的变化而改变，因此一般不是人们所关心的。
回想起来，我一直很奇怪，一年多过去了，怎么就没有什么关于D-Wave的大新闻，也没有人让我迅速做出反应。这场辩论真的已经结束了吗？或者是还没有“结束”，不过就像一直以来本应该的样子，掌握在那些可能不是激烈反对，但至少在声称有多少加速时还蛮谨慎的科学家手中？反正至少能让我这位前D-Wave首席怀疑官腾出点手来干些更“来钱”的项目，就像在互联网上对社会正义无休止的辩论中画一条中间道路出来，对吗？
不，当然不是。
大家现在已经看到，这周一（编者注：2015年12月7日）谷歌的一个研究小组把一篇重要的研究论文挂在了网上【1】，展示了他们在D-Wave 2X上做的最新的实验结果。对此可以参见Hartmut Neven（编者注：Google 工程负责人，量子人工智能实验室主任）的博客【2】。意料之中的是，大众媒体对这一结果的解读【3】为，D-Wave 2X 在某些方面已经比标准经典芯片快1亿倍，因此剩下的问题就是这一设备是否为“真正的量子计算机”。
在这种情况下，我做的第一件事就是向Matthias Troyer（编者注：瑞士苏黎世联邦理工学院教授）求助。他可以算得上是世界上量子退火实验领域最为博学、公正而又值得信任的人了。令我高兴的是，Matthias简直是慷慨大方，他跟Ilia Zintchenko和Ethan Brown合作，针对新的结果写了一篇长达3页文章【4】，解释这一结果的来龙去脉，并允许我与大家分享。纯粹从科学的角度来讲，我的帖子到此已经可以结束了，只需要给出他们这篇文章的链接。
不过，依旧是从纯科学的角度来看，这个帖子可能应该更早地结束，把谷歌文章的链接放上来就是了，因为这篇文章并没有隐藏一些关键信息，让它的怀疑者仔细挖掘才能发现。相反，文章的作者中有这一领域中最为谨慎的人物，把人们可能问到的问题都解释清楚了。所以，在某种意义上，我或者Matthias可以做的，仅仅是告诉你，如果读这些文章，你会学到些什么。
那么，D-Wave 2X 是否加速1亿倍呢？这是我认为能做到不误导人、最为简短的答案：
是的，确实存有明显渐进行为的1亿倍加速，并且与量子蒙特卡罗（Quantum Monte Carlo, QMC）算法相比，也存在1亿倍的加速。但是，渐进的加速仅仅是在与模拟退火（simulated annealing）比较时得到的，而超过QMC的1亿倍加速则是一个常数因子，不是渐进的。而且，在一般情况下，如果与其他经典算法比较，两种加速都会消失。另外，常数因子的加速与其说和量子力学相关，倒不如说可能和D-Wave极度专业化的硬件本身更为相关，而后在模拟此专业化硬件这一问题上再与经典芯片做比较（即在D-Wave的Chimera graph架构上进行Ising自旋最小化）。因此，虽然确实是有货真价实而又有趣的进展，但是与已知最知名的经典算法相比，目前尚不清楚D-Wave的方法速度是否会提高，更别说那些还满足渐近的或者具有重要实际意义的最知名的经典算法。事实上，所有这些问题对于整个量子退火领域来说也都还是个谜。
展开来说，谷歌这篇文章实际上有三个独立的结果：
1. 作者通过Chimera graph中扮演核心角色的8量子比特“集群”，利用高而窄的能垒挡住了前往全局最小的路，从而构造了Chimera 实例。然后他们发现，正如2002年Farhi、Goldstone和Gutmann理论预言【5】的那样（这个预言我们此前经常在这个博客上讨论），对于这些特殊的实例，量子退火达到全局极小的速度要指数级快于经典模拟退火，而D-Wave利用了这一优势。就我而言，由此可以确定，在D-Wave中，或者至少在8量子比特集群中，发生了与计算有关的集体量子隧穿。另一方面，作者指出，还有其他经典算法，像Selby（在Hamze 以及 de Freitas的基础上）所构造的【6】，可以将这一8量子比特集群打包成可有256种取值的大变量，从而摆脱阻碍模拟退火的能垒。他们还通过经验得出，这些经典算法的表现要胜过D-Wave。作者利用量子蒙特卡罗方法也得到了与D-Wave相仿的渐近复杂度性能（虽然没有那个起主要作用的常数）。量子蒙特卡罗（尽管名字里有量子二字）是一种经典的算法，经常被用来寻找量子力学系统的基态。
2. 作者提出：可以隧穿高而窄能垒的这种能力——量子退火目前已经展现出来的相较于经典退火的核心优势——可能至少跟某些现实世界中的优化问题相关。他们试图通过研究一个经典的NP完全问题——数字划分（Number Partitioning），来说明这一点。在这个问题中，给定一个含N个正整数的集合，你的目标是把它们划分成2个子集，使得二者各自总和的差别尽可能小。通过在经典计算机上的数值研究，他们发现，对于随机的数字划分问题，量子退火（在理想情况下）和量子蒙特卡罗的速度应该都超过了模拟退火，超过的程度也差不多。请注意，本文的这一部分不涉及对D-Wave本身的任何实验，所以我们不知道误差校准、编码丢失等问题是否会抹杀其在理论上所具有的优势。不过即使没有抹杀，这仍然不能产生一个“真正的量子加速”，因为（再说一遍），量子蒙特卡罗是一种近乎完美的经典算法，其在这些问题上的渐近复杂度与量子退火相当。
3. 最后，对于这些能垒高而窄的特殊Chimera实例，作者发现，比起在单核计算机上运行的量子蒙特卡罗算法，D-Wave 2X达到全局最优的速度要快约1亿倍。但是，非常有趣的是，他们还发现，这种加速不会随问题规模的增长而增长，而是在大约1亿倍的时候就饱和了。换句话说，这是一个常数因子的加速，而不是渐进的。是的，显然，用“仅有”1亿倍加速（而不是渐进加速）的算法解决一个问题仍然具有实用价值！但重要的是，要知道，这个常数因子加速仅仅是在解决此类Chimera graph实例所对应的问题时才有的——或者本质上来讲，是在解决“模拟D-Wave本身”这一问题时才有的！如果你想解决实际的问题，你首先需要将它嵌入到Chimera graph，而目前还不清楚的是，这些常数因子的加速能力是否还存在。尽管这篇文章中没有明确说明，我依然相信，在任何情况下，当我们将其跟（比方说）Selby 算法相比时，常数因子加速会消失，更别说跟量子蒙特卡罗相比！
这篇新的谷歌文章给出了关于D-Wave能力到目前为止最为清晰的展示。但我要提醒的是，关于D-Wave的整个方案，量子计算研究者们从一开始便担心的问题是：纠错能力的缺失、有限温度量子退火的限制，我们缺乏明确的证据表明它能给出量子加速，以及急着搞出来更多的而不是更好的量子比特。我还会说，所有这些担忧不仅依然存在，而且还因为很多枝节问题也开始被人们处理，从而更加清楚明白地显现了出来。D-Wave 2X是一个伟大的工程。但是如果仍然不能在最广为人知的经典算法上展现出渐进加速的性能——这篇新的谷歌文章很清楚地表明它没有——那么这些担忧就不是无关痛痒的。更何况，这些原因似乎和十多年D-Wave 所做出的根本的设计选择是相关的。
现在明显的问题是：是否能通过改进D-Wave的设计，来得到一个渐进的加速，并且对所有的经典算法（包括QMC和Selby算法）都成立，还可以克服将“真实世界”的问题编码为Chimera graph所带来的时间代价？也许能，也许不能吧。谷歌这篇文章一遍又一遍地回到D-Wave的未来改进计划这一主题，并探讨它们可能如何清除那些障碍，达到“真正的”量子加速。粗略地说，如果我们排除推翻重来的办法，那么主要有四件事情可以试试看是否有效：
1. 更低的温度（因此有更长的量子比特生命期，以及在不发生跃迁到激发态的情况下获得更小的安全能隙）。
2. 对量子比特及其耦合更好的校准（因此能以更高的精度来编码感兴趣的问题，例如之前提到的数字划分问题）。
3. 能够运用“非量子随机”哈密顿量的能力。（D-Wave现有的机器都受限于量子随机的哈密顿量，后者被定义为所有非对角项均为非正实数的哈密顿量。从工程的角度来看量子随机的哈密顿量是更容易的，对于经典算法，例如QMC来说，它们也是最容易被模拟的——如此容易，以至于人们还在争论非量子随机量子退火是否在理论上可以有真正的量子加速）
4. 量子比特之间更好的连通性（从而减少将实际感兴趣的问题编码到Chimera graph中所付出的巨大代价）。
（注意，“更多的量子比特”不在这个名单上：如果利用D-Wave真能实现“真正的量子加速”，那么它们拥有的1000多个量子比特早够让人们看出个究竟了。）
不管怎样，这些当然都是D–Wave 的设计者们知道而且在不久的将来会做的事情。但是，即便D-Wave在这四个方面都做出了改进，我们仍然不知道是否会出现一个真实的、渐近的、胜过Selby算法的、克服编码代价的量子加速。我们只是不能肯定地说出那个否定的答案。
与此同时，在博客上讨论很容易被遗忘的是，D-Wave只是实验量子计算领域的一个真子集，而在过去的一两年里，许多其他方面取得了更为令人兴奋的成就。特别是，谷歌的John Martinis组（编者注：John Martinis是加州大学圣芭芭拉分校物理学教授，2014年加入谷歌，也是谷歌关于D-Wave文章的共同作者之一）现在有相干时间比D-Wave高几个数量级的超导量子比特，并对其中的9个初步展示了量子纠错。他们现在在讨论的是将其扩展到大约40个质量超高的、耦合可控的量子比特——不是在遥远的未来，而是在最近几年里。如果他们做到了这一点，我将非常乐观地认为，他们将能够就某件事情展示出明显的量子优势（例如，一些像玻色抽样那样的抽样任务）——如果不一定是有实际意义的事情的话。我上周刚访问过的IBM Yorktown Heights同样也在致力于合成相干时间达很多微秒的超导量子比特。与此同时，一些顶级的离子阱研究组，例如马里兰大学的Chris Monroe组，也正在讨论类似的他们希望能够尽快做到的大新闻。对于量子计算研究的“学术方法”——不妨概括为“理解量子比特、控制它们、保持其量子力学特性，最终在此基础上将其扩展”——终会结出多汁的果实。
我依旧不知道什么时候甚至是否我们会得到一个实用的、通用的、能容错的量子计算机，能够对10000位的数字进行质因子分解等。但是现在看起来，让Gil Kalai（编者注：Kalai为以色列希伯来大学数学系教授）和其他量子计算怀疑者们承认错误只是几年时间的问题——这不管怎样，都是一直以来我所关心的主要用途！
对于量子计算来说，这是一个令人兴奋的时代。很多事情接踵而至，比我预想的都更快。当我们朝着这个计算新世界勇敢地、相干地、希望非量子随机地、可能容错地蹒跚前进时，我对于我这个博客的目标永远跟过去的十年一样：不胡乱预言，不挑选赢家，而仅仅是试着去理解和解释那些已经被证实的和还未被证实的事情。
参考文章相关链接：
【1】谷歌论文“What is theComputational Value of Finite Range Tunneling?”，链接：http://arxiv.org/abs/1512.02206
【2】Hartmut Neven关于D-Wave机器最新进展的博文，http://googleresearch.blogspot.ca/2015/12/when-can-quantum-annealing-win.html
【3】美国科技媒体对D -Wave的解读：http://www.techtimes.com/articles/114614/20151209/googles-d-wave-2x-quantum-computer-100-million-times-faster-than-regular-computer-chip.htm
http://www.theregister.co.uk/2015/12/09/googles_quantum_computer/
【4】Matthias Troyer文章链接：http://www.scottaaronson.com/troyer.pdf
【5】Edward H. Farhi，Jeffrey Goldstone和SamGutmann，三人均为麻省理工学院理论物理学教授，文章链接：http://arxiv.org/abs/quant-ph/0201031
【6】Alex Selby,剑桥大学数学博士，Selby算法发明人，文章链接：http://arxiv.org/abs/1409.3934
本文经Scott Aaronson授权翻译，发表时有部分删节，更多更新及讨论请点击Google, D-Wave, and the case of the factor-10^8 speedup for WHAT?
知识分子，为更好的智趣生活。
《知识分子》由饶毅、鲁白、谢宇三位学者创办并担任主编。
投稿、授权事宜请联系：zizaifenxiang@163.com。
