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

记者从中国科大获悉，该校潘建伟、陆朝阳、刘乃乐等组成的研究团队，基于“九章”光量子计算原型机，完成了对“稠密子图”和“Max-Haf”两类图论问题的求解，实验速率比全球最快超级计算机快约1.8亿倍。该研究成果是首次在具有量子计算优越性的光量子计算原型机上开展的面向具有应用价值问题的实验研究。

量子计算机的物理实现是当前科技前沿的重大挑战之一。国际学术界对量子计算的实验发展制定了三步走的路线图，其中第一步是实现“量子计算优越性”。“量子计算优越性”是指，通过高精度地操纵近百个物理比特，高效求解超级计算机无法在合理时间内解决的特定的高复杂度数学问题。

近期，潘建伟团队在继续发展更高质量和更强拓展性的光量子计算原型机的同时，开展了将“九章”所执行的高斯玻色采样任务应用于图论问题的研究探索。高斯玻色采样与图论问题具有紧密的数学联系，通过将高斯玻色采样设备的每个输出端口映射到图的顶点，将每个探测到的光子映射到子图的顶点，研究人员可以利用实验得到的样本加速搜索算法寻找具有更大密度或Hafnian的子图的过程，从而帮助这两类图论问题的求解。这两类图论问题在数据挖掘、生物信息、网络分析和某些化学模型研究等领域具有重要应用。（记者 葛清政）