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

从某种意义上说,当然,他们已经做到了。 2019 年,谷歌的物理学家 公布 他们使用 53 量子比特的机器来实现 量子至上,一个象征性的里程碑,标志着量子计算机可以做一些超出任何实用经典算法范围的事情。 类似 示威 中国科学技术大学的物理学家紧随其后。

 

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

 

这个一般性问题仍然很难回答,部分原因还是因为那些讨厌的错误。 (未来的量子机器将使用一种称为 量子误差校正,但这种能力还有很长的路要走。)即使有未纠正的错误,是否有可能获得希望的失控量子优势?

 

大多数研究人员怀疑答案是否定的,但他们无法在所有情况下证明这一点。 现在,在一个  发布到预印本服务器 arxiv.org,一组计算机科学家已迈出重要一步,全面证明纠错对于随机电路采样中持久的量子优势是必要的 - 这是谷歌用来展示量子霸权的定制问题。 他们通过开发一种经典算法来做到这一点,该算法可以在存在错误时模拟随机电路采样实验。

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

 

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

 

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

 

量子优势的问题很简单:很难模仿概率分布吗 用经典算法 那不使用任何纠缠?

 

在2019,研究人员 证明 对于无错误的量子电路,答案是肯定的:当没有错误时,确实很难经典地模拟随机电路采样实验。 研究人员在计算复杂性理论的框架内工作,该理论对不同问题的相对难度进行了分类。 在这个领域,研究人员并不把量子比特的数量当作一个固定的数字,比如 53。“把它想象成 n,这是一些会增加的数字,”说 阿兰哈罗,麻省理工学院物理学家。 “然后你想问:我们是否正在做一些努力成倍增长的事情? n 或多项式 n? 这是对算法的运行时间进行分类的首选方法——当 n 增长到足够大,一个指数增长的算法 n 远远落后于多项式的任何算法 n. 当理论家谈到一个对经典计算机来说很难但对量子计算机来说很容易的问题时,他们指的是这种区别:最好的经典算法需要指数时间,而量子计算机可以在多项式时间内解决问题。

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

 

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

 

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

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

 

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

 

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

 

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

翻译»