斯坦福、伯克利新研究推翻谷歌「量子霸权」！理论上很美，实际上没戏

量子霸权，这个词已经诞生了近4年了。

2019年，谷歌的物理学家宣布成功用一台53量子比特的机器实现了量子霸权，这是一个具有重大象征的里程碑。

在Nature上发表的论文中称，该量子系统只用了200秒完成一个计算，而同样的计算用当时最强大的超级计算机Summit执行，需要约10000年。

什么是量子霸权？

所谓「量子霸权」，或者叫「量子优势」（以下称「量子霸权」）是指，量子计算机能完成的任务超出了任何可行经典算法的范围。

这些任务即使放在最先进的传统超级计算机上，计算时间之长（往往是成千上万年）也会让算法失去实用意义。

有趣的是，在2019年谷歌的成果中，只说了实现了量子霸权，没有说明在哪些具体实例下，量子计算机超过了经典计算机。

这是一个很难回答的问题，因为目前量子计算机受到错误频发的困扰，这些错误会累积，破坏量子计算的性能和稳定。

实际上，与量子霸权的实现领域相比，科学家更想知道的是另一个问题：随着量子计算机越来越大，经典算法是否能够跟上脚步。

德克萨斯大学奥斯汀分校的计算机科学家Scott Aaronson说：「我们希望最终量子一方会完全拉开距离，彻底结束这场竞争。」

大多数研究人员推测，答案是否定的。

即经典算法总有一天会彻底跟不上量子计算的脚步，但一直无法准确全面地证明这一点。要确定证明这个推论，一个途径是找到量子计算能够获得相对于传统计算「持久优势」的条件。

现在，这个问题似乎有了初步答案：

省流：量子计算是会产生错误的，如果纠错跟不上，这种错误就 会打破理想状态下的「量子霸权」，让经典算法能够跟得上量子算法的脚步。​

最近，在一篇Arxiv上发表的预印本论文中，由哈佛大学、加州大学伯克利分校、以色列希伯来大学的联合团队朝着证实这个结论迈出了一大步。

他们证明了，目标错误纠正是随机电路采样中持久量子霸权的必要条件，为几年前谷歌的研究结论提供了支撑。在目前的量子纠错水平下，量子霸权实际上是并不存在的。​

再无量子霸权「黄金地带」

研究人员开发了一种经典算法，可以模拟存在错误时的随机电路取样实验来证明这个结论。

从一个量子比特阵列开始，用被称为「量子门」的操作随机操纵这些量子比特。一些量子门会使成对的量子比特处于纠缠态，即意味着彼此共享一个量子态，不能被单独描述。

在多层电路中重复设置这些量子门，可以让量子比特进入更复杂的纠缠态。

左图为理想状态下的随机电路取样，右图为包含干扰的随机电路取样

为了了解这种量子态，研究人员测量了阵列中的所有量子比特。这个行为会导致所有量子比特的集体量子态坍缩为一串随机的普通比特，即0和1。

可能的结果数量随着阵列中的量子比特数量的增加而迅速增长。在谷歌2019年的的实验中，53个量子比特下包含近10万亿个结果。

而且，这种方法需要从随机电路中多次重复测量，建立一个关于结果的概率分布图。

关于量子霸权的问题是，用一个不使用任何纠缠的经典算法，来模仿这种概率分布，是否很难甚至不可能？

2019年，谷歌研究人员就证明，对于无误差、不会产生错误的量子电路来说，这个目标是困难的。在没有错误的情况下，确实很难用经典算法模拟一个随机电路采样实验。

从计算复杂度的角度看，当量子比特数量增加时，传统分类算法的计算复杂度是呈指数增加的，而量子算法是呈多项式增加的。

当n增加到足够大时，一个在n中呈指数级的算法，要远远落后于任何在n中呈多项式的算法。

当我们谈到一个对经典计算机来说很难，但对量子计算机来说很容易的问题时，指的就是这种区别。最好的经典算法需要指数时间，而量子计算机可以在多项式时间内解决问题。

不过，2019年的那篇论文没有考虑不完善的量子门造成错误的影响，研究结论实际上留了个口子，也就是说，没有纠错的随机电路采样，是否还能实现量子霸权？

实际上，如果考虑量子纠缠中产生的、可以累积的错误，那么用经典算法模拟随机电路采样实验的难度就会大大降低。而如果经典算法模拟的计算复杂度，降低到与量子算法相同的多项式级别，量子霸权就将不复存在。

这篇新论文表明，假设保持电路深度不变，比如说很浅的3层，随着量子比特数量的增加，不会有太多的量子纠缠，输出仍然可以进行经典模拟。

另一方面，如果增加电路深度，跟上不断增加的量子比特数量，那么由量子门错误累积的效应将冲淡纠缠产生的复杂程度，用经典算法模拟输出仍然会变得更加容易。

在这两者之间有一个「黄金地带」，即量子霸权得以继续存活的窗口，即传统算法模拟跟不上量子纠缠的范围。

在这篇论文发表之前，即使随着量子比特数的增加，当量子比特数量达到某个中间范围时，量子霸权是仍然存在的。

在这种电路深度下，即使输出会因量子算法错误而稳定地退化，但在每一步都难以进行经典算法模拟。

这篇新论文把这个「黄金地带」几乎消灭了。​

论文中推导出一种模拟随机电路采样的经典算法，并证明了其运行时间是运行相应量子实验所需时间的多项式函数，而非指数函数。

这一结果在随机电路采样的经典方法和量子方法的速度之间建立了紧密的理论联系，即宣告了在理论上已经实现的量子霸权，在实际上几乎并不存在。

之所以说「几乎」，是因为新算法的基本假设对某些较浅的电路是无效的，留下了一个未知的「小缺口」。

不过，很少有研究人员还对在这个缺口中实现量子霸权抱有希望。连2019年谷歌那篇论文的作者之一、芝加哥大学的计算机科学家比尔·费弗曼（Bill Fefferman）也表示：「我看这个几率相当小」。

可以这么说，按照计算复杂性理论的严格标准，随机电路采样已经不会产生量子霸权了。

另外，面对这个结论，所有研究人员都同意，量子纠错对于量子计算的长期成功将是多么关键。Fefferman说：「我们研究到最后都发现，量子纠错才是解决方案。」