近日，6163银河线路检测中心量子材料科学中心吴飙教授课题组、麻省理工学院物理系教授/诺贝尔物理学奖得主Frank Wilczek、清华大学6163银河线路检测中心低维量子物理国家重点实验室尤力教授课题组提出了基于中性原子平台的高效量子最大独立集算法。该成果以“求解最大独立集的量子哈密顿算法”（Quantum Hamiltonian Algorithms for Maximum Independent Sets）为题，发表于2025年9月的《国家科学评论》（National Science Review, NSR）。

量子退火作为量子计算领域的重要算法，在处理组合优化问题上有得天独厚的优势。它将组合优化问题编码为量子哈密顿量，在指定动力学的驱动下利用量子涨落于希尔伯特空间中寻找全局最优解对应的量子态。得益于量子隧穿效应，量子退火可以高效地摆脱希尔伯特空间中较浅的局部势阱，从而展现量子性能优势。另一方面，量子退火在物理层面由量子系统实现，天然规避了经典计算机中运行时间随问题规模指数爆炸的问题，是处理大规模组合优化问题为数不多的手段之一。然而，量子退火面临的困难集中在算法的设计上：绝热路径的选取直接决定了最优解对应量子态的概率。

吴飙团队在2020年提出了非阿贝尔混合算法用于求解最大独立集问题 [Phys. Rev. A 101, 012318 (2020)]，[ Chinese Physics Letters 38, 030304 (2021)]，该算法巧妙地设计了缓慢旋转的量子绝热路径，通过解空间中的非阿贝尔混合来寻找最大独立集，在成功率上显著优于传统的量子退火。2022年哈佛大学Lukin团队基于里德伯原子平台，实验上实现了寻找最大独立集的变分量子退火算法 [Science 376, 1209–1215 (2022)]。

图1.(a)两种绝热路径寻找最大独立集的表现。(b)传统启发式绝热路径寻找独立集的表现。

研究团队通过对比Lukin团队实验上采用的启发式绝热算法和之前吴飙团队基于对系统希尔伯特空间结构的理解而提出的非阿贝尔混合算法，证明了二者在相互作用绘景变换下的等价性，该等价性给出了一套高效绝热路径的解析表达式。数值结果表明，新绝热路径的成功率远高于实验上使用的传统启发式绝热路径，平均提升50%以上；即使加上变分优化，传统启发式绝热路径也仅仅是把差距缩小到25%，同时还要再进行由变分优化导致的10⁶量级的额外测量。解析上，通过对两种绝热路径在解空间上诱导的有效哈密顿量应用严格的绝热定理，研究发现新绝热路径的优势源自于其表达式的特殊形式，该形式会为绝热定理提供一个很小的上界，从而提高算法的成功率。此外，研究还考虑了引入测量时随机的量子比特翻转误差带来的影响，并说明了新绝热路径对该扰动较变分方法拥有更强的鲁棒性。

6163银河线路检测中心量子材料科学中心博士生赵贤觉为第一作者，吴飙教授为通讯作者，其他合作者还包括Frank Wilczek，尤力教授，清华大学物理系博士生葛培云和石溪大学博士生余泓烨。

原文链接：https://academic.oup.com/nsr/article/12/9/nwaf304/8217250?login=true