量子退火是重要的量子算法之一，在处理组合优化问题上具有得天独厚的优势。通过编码组合优化问题成求解量子哈密顿量的基态问题，在特定动力学的演化驱动下利用量子涨落在希尔伯特空间中寻找全局最优解对应的量子态。通过量子隧穿效应，量子退火可以高效地摆脱希尔伯特空间中较浅的局部势阱制约，展现量子搜寻的性能优势。通过演化实际的物理系统，量子退火算法天然规避了经典计算中运行时间和内存空间随优化问题规模指数爆炸的困难，是处理大规模组合优化问题为数不多的实用手段之一。目前它的关键应用瓶颈集中在动力学驱动的设计上：它直接决定了获得最优解的成功率。
北京大学吴飙团队在2020年提出了非阿贝尔混合算法用于求解最大独立集问题 [Phys. Rev. A 101, 012318 (2020)，Chinese Physics Letters 38, 030304 (2021)]，该算法通过缓慢旋转的量子绝热路径，在解空间中实现非阿贝尔混合来寻找最大独立集，显著优于传统的量子退火成功率上。相比于2022年哈佛大学Lukin团队基于里德堡原子平台，实验上实现的寻找最大独立集的变分量子退火算法 [Science 376, 1209–1215 (2022)]具有优势。
最近清华物理系尤力课题组与北京大学及麻省理工学院研究人员合作取得重要进展：通过对比Lukin团队实验上采用的启发式绝热算法和之前吴飙团队基于对系统希尔伯特空间结构的理解而提出的非阿贝尔绝热退火算法，证明了二者在相互作用绘景变换下的等价性，并从数值和解析两方面展现了非阿贝尔绝热退火的优势。
图1.(a)两种绝热路径寻找最大独立集的表现。(b)传统启发式绝热路径寻找独立集的表现,对应于本工作报道的蓝线表示的结果展示出明显的优势。
该工作从理论上证明了最大独立集的非阿贝尔混合算法可以由里德堡原子哈密顿量配合含时驱动忠实地实现，并通过相互作用绘景变换给出了非阿贝尔混合算法对应绝热路径的解析表达式。数值结果表明，非阿贝尔混合绝热路径的成功率远高于实验上使用的传统启发式绝热路径，平均差距在50%以上；即使加上变分优化，传统启发式绝热路径也仅仅是把差距缩小到25%，同时还要再进行由变分优化导致的106量级的额外测量。该工作还通过解析分析考虑了引入测量时的随机量子比特翻转误差带来的影响，并说明了非阿贝尔混合绝热路径对该扰动较变分方法拥有更强的鲁棒性。此外，通过对两种绝热路径在解空间上诱导的有效哈密顿量应用严格的绝热定理，发现非阿贝尔混合绝热路径的优势源自于其表达式的特殊形式，该形式会为绝热定理提供一个很小的上界，从而提高算法的成功率，为进一步的实验研究指明了方向。
该成果以“Quantum Hamiltonian Algorithms for Maximum Independent Sets”为题发表于《国家科学评论》（National Science Review, NSR）第12期: nwaf304 (2025)。北京大学物理学院博士生赵贤觉和清华大学物理系博士生葛培云分别为论文第一和第二作者，通讯作者为北京大学物理系吴飙教授，其他合作者还包括诺贝尔奖得主、麻省理工学院(MIT)物理系Frank Wilczek教授，清华大学物理系尤力教授和石溪大学博士生余泓烨。
文章链接：https://academic.oup.com/nsr/article/12/9/nwaf304/8217250?login=true
