【学术】量子算法与计算机对抗，胜者究竟是谁？

我们对“量子霸权（quantum supremacy）”的追求证明了量子计算机比普通计算机能够更快地做一些事情，但是，却自相矛盾地导致了准量子典型算法的繁荣。

假设你有一个神秘的盒子，它接受了两种可能的输入——你可以按下红色的按钮或蓝色的按钮——然后得到两种可能的输出一——红球或蓝球。不管你按哪个颜色的按钮，如果盒子从头至尾总是归还一种颜色的球，那么它都是常数; 如果球的颜色随着按钮的颜色而变化，那么它是平衡的。你的任务是通过让盒子是只执行一次操作，就判断出你能得到哪一种类型的盒子。

乍一看，这项任务似乎毫无希望解决。事实上，当物理学家David Deutsch在1985年描述了这一思想实验时，计算机科学家们相信，任何由经典物理学规则操作的机器都可以用少于两种查询的方法来学习盒子的标识:每一种方法对应每一个输出。

然而，Deutsch发现，通过将问题转化为量子力学，实际上可以实现一个单一的查询解决方案。他提出了一种简单的五步算法，可以在只有两个量子位的量子计算机上运行，这两个量子位是量子信息的基本单位。

Cristian Calude是奥克兰大学的一名数学家和计算机科学家，他设计出了模仿某些量子算法的经典算法。

尽管它没有实际的用途，但Deutsch的算法：第一种量子算法——成为了量子计算的独特力量的一个无处不在的例子，它可能有一天会改变诸如密码学、药物发现和材料工程等领域。“如果你在过去10年左右的时间里打开一本量子计算的教科书，它就会从这个例子开始，”新西兰奥克兰大学的数学家和计算机科学家Calude说道。

但有些事情困扰着他。如果Deutsch的算法真的很好，就像早期的教科书所宣称的那样，没有一种经典的算法可以存在。这是真的吗? Calude说:“当我看到这样的说法时，我就开始思考:我如何证明它?”

然而，他无法证明出来，这就意味Deutsch的算法是错误的。在2007年的一篇论文中，他将Deutsch的算法分解为其组成的量子部分(例如，将两种经典的二进制位表示为两种“叠加”)，并将这些指令与经典操作结合在一起：一种称为“量子化”的过程。通过这种方式，他为Deutsch的黑箱之谜构建了一个经典的解决方案。事实证明，量子解决方案并不总是更好的。

• 论文地址：http://www.worldscientific.com/doi/abs/10.1142/S021974990700292X

一个普遍的误解是量子计算的潜在和限制必须来自硬件。在数字时代，我们已经习惯了在时钟速度〔计算机中央处理器处理指令速度的计算单位〕和记忆方面取得进步。同样，来自英特尔和IBM等公司的50个量子位量子计算机也激发了我们的预言，即我们正接近“量子霸权”——量子计算机的能力开始超越传统机器。

但是量子的霸主地位并不是一个单一的、彻底的胜利。它将由问题，量子算法与经典算法建立起来。“在量子计算机中，进步的不仅仅是速度，”说悉尼科技大学的量子理论学家Michael Bremner说道。“这更多的是关于算法在游戏中的复杂性。”

换句话说，Calude的故事并不是唯一的。矛盾的是，关于强大量子计算的报告正在推动对经典理论的改进，这使得量子计算机更难获得优势。Calude说:“大多数时候，当人们谈论量子计算时，经典计算就会被忽视，就像过去的黄金时代一样。”但事实并非如此。这是一场持续的竞争。”

而规则也在改变。加州理工学院的理论物理学家John Preskill说:“当谈到它的极限在哪里的时候，这取决于最好的经典算法到底有多好。随着它们变得越来越好，我们不得不绕过这一界限。”

在20世纪80年代量子计算机的梦想成形之前，大多数计算机科学家都想当然地认为经典计算是存在的。该领域的先驱们令人信服地指出，经典计算机应该能够计算出物理领域中所有可计算的东西，从基本运算到股票交易，再到黑洞碰撞。

不过，经典的机器不一定能有效地完成所有这些计算。假设你想要理解分子的化学行为。这种行为依赖于分子中的电子的行为，而分子中的电子在许多经典态的叠加态中存在。让事情变得更复杂的是，每个电子的量子态都依赖于所有其他电子的状态——这是由于被称为“纠缠”的量子力学现象。经典地计算这些纠缠态，即使是非常简单的分子，也会成为指数级增加复杂性的噩梦。

相比之下，量子计算机可以通过叠加和纠缠自己的量子位来处理电子的纠缠态。这使计算机能够处理大量的信息。你添加的每一个量子位都可以使系统同时存储的状态加倍:两个量子位可以存储4个状态，3个量子位可以存储8个状态，以此类推。因此，你可能需要50个纠缠的量子位来模拟量子态，这些量子态需要指数级的许多经典位——1.125千万亿个量子位来编码。

因此，量子机器可能会制造出一个经典的难以解决的问题，即模拟大型量子力学系统的可追踪性。“自然不是经典的，该死的，如果你想要做一个自然的模拟，你最好把它变成量子力学，”物理学家Richard Feynman在1981年的名言中说道。“这是一个非常棒的问题，因为它看起来不那么容易。”

当然,它不是。

甚至在有人开始摆弄量子硬件之前，理论学家们就一直在努力想出合适的软件。早些时候，Feynman和Deutsch了解到，他们可以用从线性代数中借来的数学运算来控制量子信息，他们将它称之为“gates”。与经典的逻辑门（logic gates）类似，量子门（quantum gates）以各种方式操纵量子位——引导它们进入一连串的叠加和纠缠，然后测量它们的输出。通过混合和匹配gates来形成电路，理论学家们可以很容易地组装出量子算法。

20世纪80年代，物理学家Richard Feynman提出了量子计算机的想法，他打趣说:“这是一个很好的问题，因为它看起来不那么容易。”

而构想出的运算法则，保证了清晰的计算收益，这是比较困难的。到21世纪初，数学家们只提出了几个优秀的候选。最著名的是，在1994年，贝尔实验室的一名年轻的工作人员Peter Shor命名了一种量子算法，它的指数比任何已知的经典算法都要快得多，这一效率可以让它破解许多流行的加密方案。两年后，Shor的同事Lov Grover也设计出了一种算法，通过未分类的数据库加快了传统数据库的搜索过程。“有各种各样的例子表明量子计算能力大于传统的计算能力。”剑桥大学量子信息科学家Richard Jozsa说道。在1992年,Jozsa帮助Deutsch扩展他的有许多可能的输入的黑箱问题,他们的量子解决方案仍然是无可比拟的。

但Jozsa和Calude和其他人一样，也会发现各种各样的例子，就像Deutsch的原始算法一样，表明了相反的情况。Jozsa说:“事实证明，许多量子过程很难在经典计算机上模拟。但是，用巧妙的、微妙的数学技巧，你就能知道它们会怎么做。”Jozsa和他的同事们发现，他们可以利用这些技术来有效地模拟或去量化数量惊人的量子电路。例如，忽略纠缠的电路会落入这个陷阱，就像那些只纠缠有限数量的量子位或者只使用特定种类的纠缠门的电路一样。

那么，怎样保证像Shor这样的算法是独一无二的呢? Jozsa说:“这是一个非常开放的问题。我们从来没有真正地理解为什么有些算法是很容易模拟的，而另一些则不是。很明显，纠缠很重要，但这并不是故事的结局。”专家们开始怀疑，他们所相信的许多量子算法是否都看上去优越，但结果可能很普通。

直到最近，对量子能的追求在很大程度上是一个抽象的概念。Jozsa说:“我们并没有真正关心算法能否实施，因为没人相信在未来会有一台量子计算机可以去做这件事。”例如，运行Shor的整数算法，以解锁一个标准的128位加密密钥，需要成千上万的量子位——可能还需要数千个量子位来纠正错误。

但到了2011年，情况开始好转。在布鲁塞尔的一次会议上，Preskill推测，“严格控制的量子系统可以超越传统时代”的任务可能不会太遥远。他说，最近的实验结果可能很快就会让量子机器拥有近似100个量子位。让它们去完成一些“超级经典”的壮举也许并不是不可能的。(尽管D-Wave系统的商业化的量子处理器可以在那时与128个量子位对抗，现在已经拥有超过2000个量子位，但他们只处理特定的优化问题;许多专家怀疑他们可能会超越经典的计算机。)

Preskill说:“我只是想强调我们已经接近了我们最终可能会到达人类文明的一个真正的里程碑，在那时，量子技术成为我们拥有的最强大的信息技术。”他称这一里程碑为“量子霸权”。

关于“量子霸权”的讨论反映了人们对这一领域的强烈关注，是的，但也许更多的是在2004年由IBM物理学家Barbara Terhal和David DiVincenzo预言的一篇论文中所提出的一系列理论突破。在他们努力理解量子资产的过程中，他们把注意力转向了被称为采样问题的基本量子谜题。随着时间的推移，这类问题将成为实验主义者最大的希望，证明在早期的量子机器上有一个明确的加速。

David Deutsch是牛津大学的物理学家，他提出的第一个可以通过量子计算机来解决的问题。

采样问题利用了量子信息难以捉摸的特性。假设你将gate的一个序列应用到100个量子位上。这个电路可以将量子位变成一个数学的单元数，相当于2100个经典位元的顺序。但是一旦你测量了这个系统，它的复杂性就会崩溃到只有100个位元。这个系统将会输出一个特定的字符串或样本，其中有一些概率是由你的电路决定的。

在抽样问题中，我们的目标是产生一系列看起来像是来自这个电路的样本。这就像反复扔硬币来表明它会(平均)有50%的正面概率和50%的反面概率。除了这里，每次“投掷”的结果都不是一个单独的值——正面或反面——它有许多值，每一个值都可能受到其他值的一些(甚至全部)的影响。

对于一个运转良好的量子计算机来说，这个练习是显而易见的。它理所当然的。另一方面，经典的计算机在最坏的情况下，它们必须对所有可能的输出字符串（全部的2100个字符串）进行计算概率这样的笨拙工作，然后随机从该分布中选择样本。

Terhal和DiVincenzo展示了即使是一些简单的量子电路仍然很难通过经典的方法来进行采样。因此，如果实验主义者能得到一个量子系统来吐出（spit out）这些样本，他们就有充分的理由相信他们做了一些经典的无法对抗的事情。

理论家们很快将这一思路扩展到其他类型的抽样问题。最有希望的提议之一来自MIT的一名计算机科学家Scott Aaronson和他的博士生学生Alex Arkhipov。在2010年发表的一篇文章中，他们描述了一种量子机器，这种机器通过光路传输光子，通过量子力学的方式来改变和分裂光线，从而产生出特定概率的输出模式。复制这些模式被称为“玻色子取样（boson sampling）”。Aaronson和Aaronson的理由是，玻色子的取样将会应变大约30个光子的经典资源，这是一个可行的实验目标。

• 草案：https://arxiv.org/abs/1608.00263

同样诱人的是被称为“瞬时量子多项式（instantaneous quantum polynomial）”的计算，也就是“IQP”电路。一个“IQP”电路有所有的“gate”，这意味着它们可以在不改变结果的情况下以任何顺序进行操作——就像2+5=5+2一样。Bremner说:“我们开始研究它们，因为它们更容易分析。”

到2016年，玻色子的采样器还没有超过6个光子。然而，谷歌和IBM的团队正在朝着接近50个量子位的芯片上努力;今年8月，谷歌悄悄发布了一份草案，列出了在这些“短期”设备上展示量子霸主地位的路线图。

• 草案：https://arxiv.org/abs/1608.00263