新算法关闭量子霸权窗口

在哪些具体情况下量子计算机超越了经典计算机？这是一个很难回答的问题，部分原因是当今的量子计算机是挑剔的东西，充满了可能堆积并破坏计算的错误。

从某种意义上说，当然，他们已经做到了。 2019 年，谷歌的物理学家宣布他们使用 53 量子比特的机器实现了量子霸权，这是一个象征性的里程碑，标志着量子计算机可以做任何实际经典算法无法企及的事情。中国科学技术大学的物理学家也很快进行了类似的演示。

但是，计算机科学家不是专注于一台特定机器的实验结果，而是想知道经典算法是否能够随着量子计算机变得越来越大而跟上。 “希望最终量子方面完全退出，直到不再有竞争，”德克萨斯大学奥斯汀分校的计算机科学家Scott Aaronson说。

这个一般性问题仍然很难回答，部分原因还是因为那些讨厌的错误。 （未来的量子机器将使用一种称为 量子纠错的技术来弥补它们的缺陷，但这种能力还有很长的路要走。）即使有未纠正的错误，是否有可能获得希望的失控量子优势？

大多数研究人员怀疑答案是否定的，但他们无法在所有情况下证明这一点。现在，在预印本服务器 arxiv.org 上发布的一篇论文中，一组计算机科学家朝着综合证明迈出了重要一步，即纠错对于随机电路抽样中的持久量子优势是必要的——这是谷歌过去常常解决的定制问题显示量子霸权。他们通过开发一种经典算法来做到这一点，该算法可以在存在错误时模拟随机电路采样实验。

“这是一个漂亮的理论结果，”Aaronson 说，同时强调新算法对于模拟像谷歌这样的真实实验实际上没有用。

在随机电路采样实验中，研究人员从一组量子位或量子位开始。然后他们通过称为量子门的操作随机操纵这些量子位。一些门导致成对的量子位纠缠在一起，这意味着它们共享一个量子态并且不能单独描述。重复的门控层使量子比特进入更复杂的纠缠状态。

为了了解该量子态，研究人员随后测量了阵列中的所有量子位。这导致它们的集体量子态坍缩为随机的普通位串——0 和 1。可能结果的数量随着阵列中量子比特的数量而迅速增长：在 53 个量子比特的情况下，在谷歌的实验中，它接近 10 千万亿。并非所有字符串的可能性都相同。从随机电路中采样意味着多次重复此类测量，以构建结果背后的概率分布图。

量子优势的问题很简单：很难用不使用任何纠缠的经典算法来模拟概率分布吗？

2019 年，研究人员证明了无错误量子电路的答案是肯定的：在没有错误的情况下，经典地模拟随机电路采样实验确实很难。研究人员在计算复杂性理论的框架内工作，该理论对不同问题的相对难度进行了分类。在这个领域，研究人员不会将量子比特的数量视为一个固定数字，例如 53。 . “然后你想问：我们做的事情是在n 中呈指数形式还是在 n中呈多项式形式？”这是对算法的运行时间进行分类的首选方法 – 当n增长到足够大时， n 的指数算法远远落后于 n的多项式算法。当理论家谈到一个对经典计算机来说很难但对量子计算机来说很容易的问题时，他们指的是这种区别：最好的经典算法需要指数时间，而量子计算机可以在多项式时间内解决问题。

然而，那篇 2019 年的论文忽略了由不完美的门引起的错误的影响。这为没有纠错的随机电路采样的量子优势留下了悬而未决的情况。

如果你想象像复杂性理论家那样不断增加量子比特的数量，并且你还想考虑错误，你需要决定是否还要继续添加更多的门层——如研究人员所说，增加电路深度。假设随着量子比特数的增加，您将电路深度保持在相对较浅的三层。你不会有太多的纠缠，输出仍然适用于经典模拟。另一方面，如果增加电路深度以跟上不断增长的量子比特数，门错误的累积效应将消除纠缠，输出将再次变得易于经典模拟。

但在两者之间是一个金发姑娘区。在新论文发表之前，即使量子位的数量增加，量子优势仍然有可能在这里生存。在这种中等深度的情况下，随着量子比特数量的增加，电路深度的增加非常缓慢：即使输出会因错误而稳步下降，但可能仍然很难在每一步进行经典模拟。

新论文填补了这个漏洞。作者推导出了一种模拟随机电路采样的经典算法，并证明其运行时间是运行相应量子实验所需时间的多项式函数。结果在经典和量子随机电路采样方法的速度之间建立了紧密的理论联系。

新算法适用于主要类别的中等深度电路，但它的基本假设对于某些较浅的电路来说是错误的，留下了一个小的差距，其中有效的经典模拟方法是未知的。但很少有研究人员抱有希望，即随机电路采样将难以在剩下的狭小窗口中进行经典模拟。 “我认为它的可能性很小，”芝加哥大学计算机科学家、2019 年理论论文的作者之一比尔·费弗曼 ( Bill Fefferman ) 说。

结果表明，根据计算复杂性理论的严格标准，随机电路采样不会产生量子优势。同时，它说明了一个事实，复杂性理论家不加区别地称之为高效的多项式算法在实践中不一定很快。随着错误率的降低，新的经典算法变得越来越慢，并且在量子霸权实验中达到的低错误率下，它太慢而不实用。如果没有错误，它就会完全崩溃，所以这个结果与研究人员所知道的在理想、无错误的情况下经典地模拟随机电路采样有多么困难并不矛盾。领导谷歌量子霸权研究的物理学家Sergio Boixo表示，他认为这篇论文“更像是对随机电路采样的一个很好的证实，而不是其他任何东西。”

有一点，所有研究人员都同意：新算法强调了量子纠错对量子计算的长期成功至关重要。 “归根结底，这就是解决方案，”费弗曼说。

编者按：Scott Aaronson 是 Quanta Magazine 顾问委员会的成员。