“九章”光量子计算原型机求解图论问题

中国科学技术大学潘建伟、陆朝阳、刘乃乐等组成的研究团队，基于“九章”光量子计算原型机，完成了对“稠密子图”和“Max-Haf”两类图论问题的求解，通过实验和理论研究了“九章”处理这两类图论问题为搜索算法带来的加速，及该加速对于问题规模和实验噪声的依赖关系，实验速率比全球最快超级计算机快约1.8亿倍。该研究成果是首次在具有量子计算优越性的光量子计算原型机上开展的面向具有应用价值问题的实验研究。相关论文近日以编辑推荐形式发表于《物理评论快报》。

量子计算机的物理实现是当前科技前沿的重大挑战之一。国际学术界为量子计算的实验发展制定了三步走的路线图，其中第一步是实现“量子计算优越性”，即通过高精度操纵近百个物理比特，高效求解超级计算机无法在合理时间内解决的特定高复杂度数学问题。这一步的意义在于首次从实验上确切证明量子计算加速，并挑战“扩展的丘奇-图灵论题”。

目前，仅有谷歌、中国科学技术大学以及加拿大Xanadu等3个团队实现了“量子计算优越性”的目标。而只有在实现“量子计算优越性”的基础上，量子计算应用的实验研究才有望带来量子加速。因此，国际学术界下一阶段的一个重要科研目标是探索利用量子计算原型机演示具有实用价值的问题的求解。

近期，潘建伟团队将“九章”所执行的高斯玻色采样任务应用于图论问题的研究探索。高斯玻色采样与图论问题具有紧密的数学联系，可将高斯玻色采样设备的每个输出端口映射到图的顶点，将每个探测到的光子映射到子图顶点。研究人员可以利用实验得到的样本加速搜索算法寻找具有更大密度或Hafnian的子图的过程，从而帮助求解这两类图论问题。这两类图论问题在数据挖掘、网络分析、某些化学模型研究等领域具有重要应用价值。

研究人员首次利用“九章”执行的高斯玻色采样来加速随机搜索算法和模拟退火算法对图论问题的求解。在实验中，研究人员使用了超过20万个80光子符合计数样本，相比全球最快超级计算机，使用当前最优经典算法精确模拟，该实验速率快约1.8亿倍。

相关论文信息：https://doi.org/10.1103/PhysRevLett.130.190601

来源：中国科学报

转自：“中科院之声”微信公众号

如有侵权，请联系本站删除！