我们离真正的量子霸权还有多远？不能只看硬件

在量子计算领域，存在一个流行的误区：认为量子计算的潜力和局限性一定来自于硬件。

在数字时代，我们已经习惯于用时钟频率和存储器来标记进步的幅度。因而，英特尔和IBM推出的50位量子计算机就引发了我们已经接近所谓“量子霸权”的猜测——即量子计算机开始做经典计算机做不到的事情。

△ 50量子位的IBM量子计算机

其实，“量子霸权”的建立并非是一场决战、一蹴而就的过程，它更像是一片星星之火，需要通过量子算法和传统算法之间不断竞争，逐个地在不同问题上实现。

“有了量子计算机后，进步就不能单单用‘速度’来衡量。”悉尼科技大学的量子理论学家Michael Bremner说，“更多时候，我们要看其执行算法的复杂性。”

讽刺的是，媒体对于量子计算机的大肆吹捧，反而令它更难取得什么优势。

“多数时候人们谈到量子计算时，经典计算就被鄙视，仿佛已经日薄西山。“来自奥克兰大学的数学家、计算机科学家Cristian Calude说，“可事情不是那样的。这是一场仍在进行的较量。”

既是较量，它就并非只关乎量子计算的进步速度。“要讨论量子霸权的门槛在哪，首先要看传统算法的上限。”来自加州理工学院的理论物理学家John Preskill说，“随着传统算法变得越来越好，我们也要跟着调整二者间的界限。”

“看上去就不简单”

上世纪80年代量子计算机的梦想成型前，计算机科学家们普遍认为，经典计算就是最终解决方案。领域内的先驱们都认为，由图灵机概念具现化成的经典计算机应该能完成物理宇宙中存在的任何可计算问题，从基本的算术，到股票交易，再到黑洞爆炸。

然而，经典计算机并不能高效地完成所有类似的计算。比如，你想去理解一个分子的化学行为，而这个行为取决于分子内电子的行为，电子又以多种状态叠加的形式而存在。更乱的是，因为量子纠缠，每个电子的量子态都取决于所有其他电子的量子态。在经典计算中，即使是在非常简单的分子中的纠缠态，也可能变成一场复杂度成指数增加的噩梦。

相反，一台量子计算机则可以通过叠加和缠绕自己的量子比特来解决这些问题，这也让计算机有能力去处理更为巨大的信息量。每增加一个量子比特，都会令系统能够同时存储的状态加倍：两个量子比特可以存储四种状态，三个量子比特则可以存储八种状态，以此类推。

因此，你可能只需要50个纠缠态的量子比特，就能建立量子态的模型；作为对比，经典计算机需要完成1.125千的五次方次经典比特的编码才能完成相同的计算。

一台量子计算机，可以解决对于经典计算机而言不可解的大型量子力学系统模拟问题，这也成为了量子计算机出现的理由。

△ 费曼

“自然可不是经典的，大爷的，你要是想模拟自然，你最好把它模拟成量子力学的。”物理学家理查德·费曼曾在1981年打趣道，“天啊这真是个精妙绝伦的问题，但它看上去可没那么容易。”

△ David Deutsch

在人们绞尽脑汁去开发量子硬件之前，理论学家就开始拼命研究合适的软件了。早期，费曼和牛津大学物理学家David Deutsch曾发现，他们可以通过由线性代数借鉴来的数学运算来控制量子信息，他们将这一过程称之为“门”。

如同从模拟到经典逻辑门，量子门以各种各样的方式来操控量子比特——引导他们进入连续的叠加态和纠缠态，然后测量它们的输出。通过“门”之间的混合与匹配形成线路，物理学家可以容易地集合量子算法。

事实证明，开发这类算法要更为困难。在21世纪初期，数学家们仅仅想出了有限的几种算法。最著名的故事，是1994年，贝尔实验室一位名叫彼得·肖的年轻人提出了一种以指数量级快于所有已知算法的分解整数的量子算法，这可以让它轻易破解诸多流行的加密方案。

两年后，肖在贝尔实验室的同事格鲁弗设计出了一种算法，能够对传统计算中对于未分类数据库的冗长搜索过程进行加速。

“有很多类似的例子表明，量子计算的能量应该比经典计算更大。”剑桥大学的量子信息科学家Richard Jozsa说。

然而Jozsa和一些其他研究者同样发现了针对这一观点的诸多反例。

“许多美丽的量子进程看上去就非常复杂”，因此经典计算机难以对其进行模拟。Jozsa说，“但其实用上一些巧妙、细微的数学技术，你就能弄明白它们要干什么。”

Jozsa和其同事发现，他们可以使用这些技术来有效率地模拟——或者说将非常多的量子线路“去量子化”。比如，那些省略了量子纠缠态、只纠缠了有限的量子比特或是只使用了特定集中纠缠门的线路都可以被这种方法解决。

那到底是什么使得像肖开发出的这类算法如此强大呢？

“这是个非常开放的问题。”Jozsa说，“我们从没真正弄清楚过，为什么一些算法模拟起来很容易而另一些不是。显然，纠缠态非常重要，但故事到这还没讲完。”

专家们开始怀疑，他们之前推崇的许多量子算法是否真的“先进”，又或许和一般的算法无甚差别。

采样挣扎

直到最近，对于量子计算的追寻依然是个有些虚无缥缈的问题。

“对于执行自己的算法，其实我们并没有真的十分担忧，因为没人真的相信，在可见的未来我们就会拥有量子计算机。”Jozsa说。

举个例子，在一个足够大的整数上运行肖的算法，来破解一个标准的128位密钥，就需要数千个量子比特——还可能要再加上数千个来修正错误。

2011年秋天，在布鲁塞尔举行的一个论坛上，Preskill预计，我们离“可控的量子系统能够执行超越经典算法的那天”可能已经不远了。他说最近的实验室结果，不久之内就会推动100位量子计算机的出现，而让这些计算机去解决一些“超经典”问题并非完全不可能（尽管D-Wave系统的商用量子处理器在那之前就可能达到128个量子比特，但它只能处理特定的优化问题，甚至有许多专家怀疑它是否真正超越了经典计算机。）。

“我只是在强调我们正在离得越来越近。我们很可能最终实现这个里程碑——量子技术成为人类历史上最强大的信息技术。”Preskill说。他将这个里程碑称为“量子霸权”。他说：“它已经发展到了一个我并不怀疑的程度。”

这些关于量子霸权的碎碎念，反映了领域内掩藏不住的兴奋。这一切或许都源于2004年，IBM的物理学家Barbara Terhal和David DiVincenzo发表的一篇论文后的一系列理论突破：在两人试图理解量子世界的努力中，两人将目光转向了一个最基本的量子谜题——采样问题。

采样问题力图挖掘量子信息的深奥性质。比如，你将一系列的门应用到了100个量子比特上。这条线路可能会驱使量子比特变成一团在数学上等价于2的100次方个经典比特的怪物。可一旦你对系统进行测量，它的复杂度会坍塌成一条仅仅100比特的字符串。系统会输出一条特定的字符串，或是一个样本，其概率则由你的线路决定。

一个采样问题的目标是制造一系列看上去像是来自线路的样本，这就像是不断地掷一枚硬币，来证明它最终会平均出现50%的正面和50%的反面的结果。只不过在采样问题中，每次“投掷”的结果不是一个简单的“正”或“反”。而是一串数值，每个数值都可能被其他部分（或全部）数值所影响。

对于一台顺畅的量子计算机而言，这一过程是非常容易的事情，因为它本来就是如此工作的。但对于经典计算机而言，这就非常艰难了。在最糟糕的情况中，它们必须对可能输出字符串的全部结果（2的100次方种）进行计算，然后从它们的分布中随机选择样本。

Terhal和DiVincenzo证明了，即便对于一部分很简单的量子线路，用经典方法来采样依然非常困难。于是这就成为了一个门槛：如果有实验者能让一个量子系统输出这些样本，他们就有足够理由相信，他们已经做出了一些传统方法无法匹敌的事情。

理论学家们迅速将这种想法拓展到了其他类型的采样问题上。其中最光明的一条假说来自当时麻省理工学院的计算机科学家Scott Aaronson和他的博士生Alex Arkhipov。在他们于2010年在Arxiv上预发表的论文中，他们描述了一种通过光学线路来发送光子的量子计算机，它通过量子力学的方式对光进行转换和分离，然后生成具备特定概率的输出模式。

复制这些模式的过程被成为玻色子采样。Aaronson和Arkhipov推论经典计算机可以用大约30个光子来模拟玻色子采样问题，这似乎也是一个合理的实验目标。

同样吸引人的，还有被称之为IQP（instantaneous quantum polynomial）的线路。一条IQP线路内的门全部“对易”（commute），即可以以任意顺序排列而不更改输出结果，就像是5+2=2+5，这种对等是合乎数学原理的。

“因为它们分析起来非常方便，因此我们开展了研究。”Bremner说。但他发现，这样的方法还有其他优点。在一项开始于2010年，并在2016年Montanaro和Dan Shepherd发表的一篇论文中达到顶峰的工作中，Bremner解释了为何IQP线路可以非常强大：即便是对于拥有数百个量子比特的、可实现的系统而言，用经典方式来解决采样问题也会变得十分棘手。

在2016年前，玻色子采样还没能扩展到6个光子以外。然而，谷歌和IBM的团队已经接近开发出50个量子比特的芯片了。当年八月，谷歌悄悄地发布了一篇草稿，上面展示了量子霸权在这些“近期”设备上出现的路线图。

谷歌的团队确实考虑了通过IQP线路来进行采样。但Bremner和其同事在更进一步的研究中发现，这一线路可能需要一些错误修正——而这需要额外的门，以及两百个额外的量子比特，才能毫无疑问地彻底击败最好的经典算法。

因此，这支团队使用了同Aaronson和Bremner类似的论据，证明：虽然更加难以构建和分析，但一条由非对易门组成的线路对于经典设备而言也更加难以模拟。

为了给经典计算设置更大的障碍，团队提出了随机选择一条线路进行采样的想法。而在这种方式下，经典方法将难以发现线路结构的任何近似特征，也不能更好地猜测它的行为。

△ IBM的量子计算中心

然而，传统算法吸引更多资源的趋势依旧不可阻挡。事实上，2017年10月，一支IBM的团队展示了在一般深度的线路（没有太多层的门）下，只需用上一点传统的技巧，一台超算就能模拟56个量子比特下随机线路上的采样。与之类似，最近出现的一个算法将用经典方法进行玻色子采样的极限推动到了约50个光子。

然而，这些努力依然是低效的。例如，IBM的模拟就花了足足两天，做的是一台量子计算机预计在十分之一毫秒内就能完成的工作。再增加几个量子比特，或是多几层门，量子霸权的时代可能就要到来了。

“一般而言，如果是对高纠缠度的系统进行仿真，还没有能真正改变局势的经典突破出现。”Preskill说，“我们只是在边界上一点一点地挣扎，而没有真正去拓宽它。”

当然，这也并不是说胜利就近在眼前了。

“边界在哪里，这是个人们会一直争论下去的问题。”Bremner说。试想这样的场景：研究者们从一条有一定深度、含50个量子比特的线路上完成了采样，然后声称建立了量子霸权。但线路可能充满了噪声，量子比特可能在错误地运行，或是门可能工作状况不佳——然后，一些经典理论学家中的佼佼者就能毫不费力地模拟出这条量子线路……

“存在噪音时，你认为困难的东西从经典方法的角度看其实并非那么困难。”Bremner解释道，“这种情况可能会发生。”

我们更加能够确定的是，一旦第一代“霸权”量子计算机出现，它们将不会被用于破解密码或是模拟药物分子。

“这就是关于霸权有趣的地方。” Montanaro说，“我们解决的第一波问题，会是我们不曾真正在乎答案的那些。”

不论如何，量子计算领域正在取得的胜利，不管多么不起眼，都令科学家们更加确信他们正走在正确的道路上——计算领域全新霸主的出现是完全可能的。而下一次的浪潮，谁也不知道会何时到来。