多项式时间经典算法“关闭”量子霸权的窗口

煤油灯科技2023-01-16 09:19

在哪些具体情况下量子计算机会超越经典计算机?这是一个很难回答的问题,部分原因是当今的量子计算机非常挑剔,错误会堆积起来,破坏它们的计算。

当然,从某种意义上说,他们已经做到了。2019 年,谷歌的物理学家宣布他们使用 53 量子比特的机器实现了量子霸权,这是一个象征性的里程碑,标志着量子计算机可以做任何实际的经典算法都无法做到的事情。中国科学技术大学的物理学家很快也进行了类似的演示。

但是,计算机科学家不是专注于一台特定机器的实验结果,而是想知道当量子计算机变得越来越大时,经典算法是否能够跟上。德克萨斯大学奥斯汀分校的计算机科学家Scott Aaronson说,“我们希望最终量子方面完全拉开距离,直到不再有竞争。”

这个一般性问题仍然很难回答,部分原因还是因为那些讨厌的错误。(未来的量子机器将使用一种称为量子纠错的技术来弥补它们的缺陷,但实现这种能力仍有一段路要走。)即使有未纠正的错误,也有可能获得所期望的失控的量子优势吗?

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

“这是一个漂亮的理论结果,”Aaronson 说,同时强调新算法在模拟谷歌等真实实验方面没有实际用处。

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

为了了解这种量子状态,研究人员然后测量阵列中的所有量子比特。这导致它们的集体量子态坍缩为普通比特(0和1)的随机串。可能的结果的数量随着数组中量子比特的数量迅速增长:在谷歌的实验中,53个量子比特接近10千万亿。并不是所有的字符串都是等可能的。从随机电路中采样意味着多次重复这样的测量,以建立一个结果背后的概率分布图像。

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

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

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

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

但在两者之间是一个宜居区。在这篇新论文发表之前,即使量子比特的数量增加,量子优势仍然有可能在这里存在。在这种中等深度的情况下,随着量子比特数量的增加,您将极其缓慢地增加电路深度:即使输出将稳步因错误而退化,但仍然很难在每个步骤进行经典的模拟。

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

新算法适用于一大类中深度电路,但其基本假设对某些较浅的电路无效,在高效的经典模拟方法未知的地方留下了一个小缺口。但很少有研究人员抱有希望,认为随机电路采样将很难在这仅存的小窗口内进行经典模拟。“我认为可能性很小,”芝加哥大学计算机科学家、2019年理论论文的作者之一Bill Fefferman说。

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

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



原文链接:https://www.quantamagazine.org/new-algorithm-closes-quantum-supremacy-window-20230109/


---煤油灯科技victorlamp.com翻译整理---

你可能也喜欢这些文章