量子霸权，这个词曾经降生了近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说：「我们研讨到最后都发现，量子纠错才是处理计划。」