发文PRL！潘建伟团队证明「九章」的“量子计算优势”

光子盒研究院出品

在解决某些计算问题时，量子计算机可以超过它们的经典对应物；但对于大多数任务来说，普通的、现成的笔记本电脑仍然要好得多。

现在，陆朝阳、潘建伟等中国科学技术大学的实验团队已经使用基于光子网络的量子计算机（九章）解决了两个图论问题——他们的结果扩展了今天含噪声的中等规模量子计算机(NISQ)比经典计算机具有“优势”的任务清单。

5月9日，研究成果以《使用高斯玻色采样解决图论问题(Solving Graph Problems Using Gaussian Boson Sampling)》为题，发表在物理学顶刊《物理评论快报》上。

高斯玻色采样(GBS)是Aaronson-Arkipov玻色采样的变种，因其在图相关问题、量子化学和机器学习中的潜在应用而引起了相当大的关注。
这是因为GBS与图论有潜在的数学联系。GBS不仅是证明量子计算优势(quantum computational advantage)的可行协议，而且在数学上也与某些与图相关的问题和量子化学问题相关。特别是，有人提出可以利用高斯玻色采样产生的样本来加强经典随机算法在搜索图的性能。

此次，实验团队研究了一个开放性的问题：在计算上有意义的体系（含噪声的中等规模量子计算机）上，GBS对经典随机算法的增强是否持续存在？它如何随着系统规模的增加而扩展？
实验中的样本是由一个144个模式(mode)的全连接光子处理器产生的。

这些光子被逐一注入网络时，GBS解决方案是对网络的144个输出探测器上记录的光子的概率分布的预测或“抽样”。
这种抽样方法在数学上与图的问题相联系，图的问题是由矩阵定义的对象之间的配对关系。实验中，研究人员使用他们的光子处理器来实现由两个这样的问题定义的搜索算法。

对Max-Haf和密集k子图(subgraph)问题解决的GBS增强

通过分数优势(score advantage)、速度优势作为光子点击数(photon-click number)的函数来衡量GBS的扩展性。

GBS增强的RS算法实现目标值的步骤直方图，是各种噪声水平的函数。对于每个子图，重复若干次试验，Y轴对应的是超过目标值的步骤数的发生次数。目标被设定为经典RS算法在10000步时达到的平均值。(a-b) 理论上模拟了光子损失噪声对Max-Haf问题的GBS增强的影响
通过将处理器的每个输出端口视为一个图形顶点、将每个检测到的光子视为一个子图顶点，他们可以确定哪个子图映射到解决方案。最终，他们的处理器在获得221891个样本后得出了一个解决方案，每个样本对应于多达80个检测到的光子的特定分布——而每个样本在世界最快的超级计算机上使用精确算法，则需要运行700秒。

在这项工作中，实验团队已经证明了GBS对随机算法的增强作用：即在量子计算优势制度下，用144模式的NISQ器件“九章”解决两个不同性质的图问题。
“以前关于量子优势的说法受到了挑战，有人认为量子计算机没有与该任务的最佳可能的经典算法竞争。” Physics Magazine编辑评价道。
“然而，与改进的经典算法和量子启发算法相比，GBS是否能产生优势，仍是一个开放的问题。”
论文中，实验团队也表示，“我们期望对各种情况进行更全面的算法分析和讨论。我们也希望我们的工作将刺激更大规模、更高延性和完全可编程的GBS的实验工作，探索现实世界中计算问题可以映射到GBS上的应用，以及开发更有效的经典和量子启发算法。”
参考链接：[1]https://physics.aps.org/articles/v16/s64[2]https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.130.190601

相关阅读：

每周一到周五，我们都将与光子盒的新老朋友相聚在微信视频号，不见不散！

|qu|cryovac>

|qu|cryovac>

你可能会错过：|qu|cryovac>

|qu|cryovac>