量子哈密顿算法求解最大独立集问题的等效机制与性能优势研究

北京大学吴飙团队与Frank Wilczek合作，针对NP难的最大独立集(MIS)问题，通过理论证明PK算法与HV算法的数学等效性（前者是后者的相互作用绘景），发现基于非阿贝尔规范矩阵的PK算法在7顶点图测试中成功率提升25%、节省6×106次测量，同时揭示PXP模型可解释为独立集中值图上的量子扩散，为量子优化算法和量子多体疤痕研究开辟新视角。

　　

在组合优化领域，最大独立集（MIS）问题犹如一座难以攻克的高峰——给定一个图结构，寻找互不相连的最大顶点子集。这类NP难问题在物流路径优化、芯片设计等领域具有重要应用价值，但经典算法最优时间复杂度仍高达1.1996ⁿn^O(1)。近年来，基于Rydberg原子阵列的量子模拟器为实现MIS量子求解带来曙光，但不同算法间的内在联系与性能差异始终迷雾重重。

北京大学量子材料科学中心吴飙团队与诺贝尔奖得主Frank Wilczek合作，在《National Science Review》发表的研究犹如拨云见日。研究人员通过严密的数学推导，首次证明两种主流量子算法——基于非阿贝尔规范势的PK算法与基于单比特操作的HV算法——存在深刻的等效性：PK算法的哈密顿量实质是HV哈密顿量在相互作用绘景下的表达。这一发现如同为量子优化理论架起一座隐形的桥梁，将看似迥异的算法体系统一于同一数学框架。

研究采用理论推导与数值模拟相结合的方法，通过构建绝热演化路径参数方程（Δ(t)=ω_φcos(ω_θt)，Ω(t)=√(ω_φ²sin²(ω_θt)+ω_θ²)），对7顶点图进行系统性测试。关键技术包括：1）Schrieffer-Wolff变换实现HV哈密顿量到PK算法的映射；2）量子绝热定理分析规范矩阵A(t)的能隙特性；3）Adam/SGD优化器对比评估算法性能；4）Chernoff边界确定测量次数下限。

两种量子算法的数学等效性

研究团队通过构建相互作用绘景下的幺正算符U_I(t)=Te^{-i∫₀tH₁(t')dt'}，揭示PK算法的哈密顿量H_PK(t)正是HV算法哈密顿量H_HV=H₁(t)+H₂的相互作用绘景表达。关键方程H₁=-iU^?(t)?_tU(t)=(μ?×μ?')·∑_jσ?_j显示，规范势的交叉项直接决定了单自旋操作参数Ω(t)、φ(t)、Δ(t)的时变规律。

性能优势的数值验证

在1000个7顶点单位圆图测试中，PK算法平均成功率高达97%（标准差2.2%），显著优于HV算法的45%（标准差41.2%）。

更惊人的是，PK算法仅需单次测量即可获得结果，而HV算法需要约6×10⁶次测量才能达到同等置信度，这归因于PK算法末态能隙ΔE=(4ω_φ²sin²(θ/2)+ω_θ²)^1/2的单调递增特性。

PXP模型的新诠释

研究突破性地发现，描述量子多体疤痕的PXP模型实质是规范矩阵A在独立集中值图上的投影。如图6所示，

将MIS问题转化为中值图上的单粒子扩散，为理解PXP模型的动力学特性提供了全新视角。这种联系使得PXP模型可从一维链推广至任意图结构，极大拓展了量子疤痕现象的研究维度。

这项研究在三个层面实现突破：理论层面首次建立两种量子算法的等效关系，技术层面证明非阿贝尔规范路径的绝热优势，物理层面为PXP模型提供图论解释。其意义不仅在于提升MIS求解效率，更在于为量子优化算法设计提供了"相互作用绘景"这一新范式，同时为量子多体系统与组合数学的交叉研究开辟了新途径。正如作者指出，当V_ij?‖H₁(t)‖时，有效哈密顿量H_eff(t)=Δ(t)D+Ω(t)O/2的简单形式，预示着可能存在更普适的量子优化原理等待发掘。