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

量子霸权自诞生以来，就成为无数研究者试图打破的命题现在，哈佛大学，加州大学伯克利分校和以色列希伯来大学的联合团队终于朝着这个方向迈出了坚实的一步

量子霸权这个词已经诞生了将近四年。

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

根据发表在《自然》杂志上的一篇论文，量子系统完成一次计算只需要200秒，而用当时最强大的超级计算机Summit进行同样的计算，大约需要1万年。

什么是量子霸权。

所谓量子霸权或量子优势，是指量子计算机所能完成的任务超出了任何可行的经典算法的范围。

即使这些任务放在最先进的传统超级计算机上，漫长的计算时间也会让算法形同虚设。

有意思的是，谷歌2019年的成果中，只实现了量子霸权，并没有说明在哪些具体情况下，量子计算机超越了经典计算机。

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

事实上，相比量子霸权的实现领域，科学家们更想知道另一个问题:伴随着量子计算机越来越大，经典算法能否跟上。

德克萨斯大学奥斯汀分校的计算机科学家斯科特·阿伦森说:我们希望最终量子一方能够完全拉开距离，彻底结束这场竞争。」

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

那就是经典算法总有一天会完全跟不上量子计算的步伐，但一直没能准确全面地证明这一点证明这一推论的一个方法是找到量子计算能够获得超越传统计算的持久优势的条件

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

节省流量:量子计算会出错如果纠错跟不上，这种错误就会打破理想状态下的量子霸权，让经典算法跟不上量子算法

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

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

不再有量子霸权黄金地带

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

从一组量子位开始，这些量子位被称为量子门的操作随机操纵一些量子门使成对的量子比特纠缠在一起，这意味着它们共享一个量子态，不能分开描述

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

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

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

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

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

2019年，谷歌研究人员证明了这个目标对于没有误差和没有误差的量子电路来说是困难的用经典算法模拟一个随机电路采样实验而不出错确实很难

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

当n足够大时，在n中是指数的算法远远落后于在n中是多项式的任何算法。

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

但2019年的论文没有考虑不完美量子门对误差的影响，研究结论实际上留了一个坑也就是说，不纠错的随机电路采样还能实现量子霸权吗

事实上，如果考虑到量子纠缠中可以积累的误差，用经典算法模拟随机电路采样实验的难度会大大降低但如果经典算法模拟的计算复杂度降低到与量子算法相同的多项式水平，量子霸权将不复存在

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

另一方面，如果增加电路深度以跟上量子比特数的增加，量子门误差积累的效应会稀释纠缠的复杂性，用经典算法模拟输出仍然会变得更容易。

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

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

在这种电路深度下，很难每一步都模拟经典算法，即使输出会因为量子算法的误差而稳步下降。

这篇新论文几乎抹去了这个黄金地带。

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

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

我们说差不多，是因为新算法的基本假设对一些浅电路无效，留下了一个未知的小缺口。

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

此外，面对这一结论，所有研究人员都同意，量子纠错将对量子计算的长期成功至关重要费夫曼说:在我们研究的最后，我们发现量子纠错是解决方案

参考资料: