近日，中国科学技术大学潘建伟、陆朝阳、刘乃乐等研究团队，基于“九章”光量子计算原型机，完成了对“稠密子图”和“Max-Haf”两类图论问题的求解，通过实验和理论研究了“九章”处理这两类图论问题为搜索算法带来的加速，以及该加速对于问题规模和实验噪声的依赖关系。
这是首次在具有量子计算优越性的光量子计算原型机上开展的面向具有应用价值问题的实验研究。
相关论文以“编辑推荐”的形式发表在国际知名学术期刊《物理评论快报》上，并被Physics网站专题报道。
该论文第一作者是博士研究生邓宇皓、龚思秋、顾义超。
01. 图论在量子计算中的应用
图论起源于著名的“哥尼斯堡七桥问题”，被广泛用于描述事物之间的关系，例如社交网络、分子结构和计算机科学中的许多问题均可对应到图论问题。
“稠密子图”和“Max-Haf”这两类图论在数据挖掘、生物信息、网络分析和某些化学模型研究等领域具有重要应用。
潘建伟团队在继续发展更高质量和更强拓展性的光量子计算原型机的同时，开展了将“九章”所执行的高斯玻色采样任务应用于图论问题的研究探索。
高斯玻色采样与图论问题具有紧密的数学联系，通过将高斯玻色采样设备的每个输出端口映射到图的顶点，将每个探测到的光子映射到子图的顶点，研究人员可以利用实验得到的样本加速搜索算法寻找具有更大密度或Hafnian的子图的过程，从而帮助“稠密子图”和“Max-Haf”这两类图论问题的求解。
图｜“九章”量子计算原型机与图论问题对应关系原理示意图
02. 量子加速与应用
目前，仅有谷歌、中国科大、以及加拿大Xanadu三个团队实现了“量子计算优越性”的目标。
只有在实现“量子计算优越性”的基础上，量子计算应用的实验研究才有望带来量子加速。
因此，国际学术界下一阶段的一个重要科研目标是探索利用量子计算原型机演示具有实用价值的问题的求解。
研究人员首次利用“九章”执行的高斯玻色采样来加速随机搜索算法和模拟退火算法对图论问题的求解。实验中使用了超过20万个80光子符合计数样本，得出结论：相比全球最快超级计算机，使用当前最优经典算法精确模拟该实验，速率快约1.8亿倍。
这一重大突破将为量子计算的应用开启全新的可能性。
该研究得到了安徽省、科技部、中科院、上海市和基金委的支持。
引用：
[1]https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.130.190601
[2]https://physics.aps.org/articles/v16/s64
[3]http://news.ustc.edu.cn/info/1055/83507.htm
-End-
声明：此文出于传递更多信息。若有错误或侵权，请联系