量子霸权，这个词已经诞生将近4年了。2019年，谷歌的物理学家宣布，他们已经用一台53量子比特的机器成功实现了量子霸权，这是一个具有重大象征意义的里程碑。根据发表在《自然》杂志上的论文，量子系统只需200秒即可完成一次计算，而同样的计算使用当时最强大的超级计算机Summit则需要大约10,000年才能完成。什么是量子霸权？所谓“量子至上”或“量子优越性”（以下简称“量子至上”），是指量子计算机所能完成的任务超出任何可行的经典算法的范围。即使在最先进的传统超级计算机上，这些任务的计算时间（通常数万年）也会让算法无用武之地。有趣的是，在谷歌2019年的业绩中，只表示实现了量子霸权，并没有具体说明在哪些具体情况下，量子计算机超越了经典计算机。这是一个很难回答的问题，因为当前的量子计算机受到频繁错误的困扰，这些错误会累积并破坏量子计算的性能和稳定性。事实上，除了量子霸权的实现，科学家们更想知道另一个问题：随着量子计算机越来越大，经典算法是否能跟得上。“我们希望最终量子方面能够完全退出并结束这场竞赛，”德克萨斯大学奥斯汀分校的计算机科学家ScottAaronson说。大多数研究人员推测答案是否定的。也就是说，经典算法总有一天会完全跟不上量子计算的步伐，只是一直没能准确、全面地证明这一点。为了确定地证明这一推论，一种方法是找到量子计算能够获得优于传统计算的“持久优势”的条件。现在，这个问题似乎有了初步的答案：存流：量子计算会产生错误，如果纠错跟不上，这个错误就会打破理想中的“量子霸权”，让经典算法跟上量子的脚步算法。最近，在Arxiv上发表的一篇预印本论文中，来自哈佛大学、加州大学伯克利分校和以色列希伯来大学的联合团队朝着证实这一结论迈出了一大步。他们证明了目标纠错是随机电路采样中持久量子霸权的必要条件，为几年前谷歌研究的结论提供了支持。在目前的量子纠错水平上，实际上并不存在量子霸权。不再有量子霸权“黄金地带”的研究人员开发了一种经典算法，可以在存在误差的情况下模拟随机电路采样实验来证明这一结论。从一组量子位开始，使用称为“量子门”的操作随机操纵这些量子位。一些量子门使成对的量子位处于纠缠态，这意味着它们彼此共享一个无法单独描述的量子态。在多层电路中重复这些量子门允许量子比特进入更复杂的纠缠态。左侧是理想状态下的随机电路样本，右侧是包含扰动的随机电路样本为了了解这种量子状态，研究人员测量了阵列中的所有量子位。这种行为导致所有量子比特的集体量子态坍缩成普通比特的随机串，即0和1。可能结果的数量随着阵列中量子比特的数量而迅速增长。在谷歌2019年的实验中，53个量子比特包含了近10万亿个结果。此外，这种方法需要对随机电路进行多次重复测量，以构建结果的概率分布图。关于量子霸权的问题是，用不使用任何纠缠的经典算法来模拟这种概率分布是否困难甚至不可能？2019年，谷歌研究人员证明，这一目标对于无错误、无差错的量子电路来说很难实现。用经典算法模拟一次随机电路采样实验确实很难做到没有错误。从计算复杂度来看，当量子比特数增加时，传统分类算法的计算复杂度呈指数增长，而量子算法则呈多项式增长。当n足够大时，在n中呈指数的算法远远落后于在n中呈多项式的任何算法。这就是我们在谈论一个对经典计算机来说很难但对量子计算机来说很容易的问题时所指的区别。最好的经典算法需要指数时间，而量子计算机可以在多项式时间内解决问题。但是，2019年的论文没有考虑不完善的量子门造成的错误影响。研究结论实际上留下了一个漏洞，即不进行纠错的随机电路采样是否还能实现量子霸权？事实上，如果考虑到量子纠缠产生的累积误差，用经典算法模拟随机电路采样实验的难度会大大降低。而如果将经典算法模拟的计算复杂度降低到与量子算法相同的多项式水平，量子霸权将不复存在。新论文表明，假设电路深度保持不变，比如非常浅的3层，随着量子比特数量的增加，不会有太多的量子纠缠，输出仍然可以进行经典模拟。另一方面，如果增加电路深度以跟上不断增加的量子比特数，那么量子门错误的累积效应将稀释纠缠的复杂性，并且仍然更容易用经典来模拟输出算法。两者之间有一个“黄金地带”，即量子霸权能够继续生存的窗口，也就是传统算法模拟跟不上量子纠缠的范围。在这篇论文发表之前，即使随着量子比特数的增加，当量子比特数达到一定的中间范围时，量子霸权仍然存在。在这个电路深度，即使输出会由于量子算法错误而稳定下降，也很难在每一步都模拟经典算法。新论文几乎抹杀了这个“黄金地带”。在论文中，我们推导了一种模拟随机电路采样的经典算法，并证明其运行时间是运行相应量子实验所需时间的多项式函数，而不是指数函数。这一结果在随机电路采样的经典方法的速度与量子方法的速度之间建立了紧密的理论联系，宣布了理论上已经实现但在实践中几乎不存在的量子霸权。之所以说“差不多”，是因为新算法的底层假设对于一些较浅的电路是无效的，留下了一个未知的“小差距”。尽管如此，很少有研究人员对这一差距中的量子霸权抱有希望。就连芝加哥大学的计算机科学家、2019年谷歌论文的作者之一比尔·费弗曼(BillFefferman)也表示：“我认为可能性很小。”可以说，按照计算复杂度理论的严格标准，随机电路采样将不再产生量子霸权。此外，面对这一结论，所有研究人员都同意量子纠错对量子计算的长期成功至关重要。“我们的研究即将结束，发现量子纠错是解决方案，”费弗曼说。
