量子科技中心_量科网

中性原子量子计算机（NAQC）已成为解决最大加权独立集（MWIS）问题的潜力平台，但模拟量子方法面临两大局限：原子排布对可实现图结构的约束，以及性能保证的缺失。该研究团队提出Lp-Quts——一种将NAQC采样器嵌入经典割平面算法的混合量子-经典框架。在每轮迭代中，松弛线性规划（RLP）会限定MWIS边界并生成简化图，继而通过模拟量子采样器从中抽取独立集。新颖的样本信息分离问题引导奇环割选择，加速收敛过程。对于t-完美图，Lp-Quts从经典割平面理论继承了多项式时间收敛保证。该工作对多达300个顶点的算例进行了评估（这一规模已超出当前NAQC硬件能力），在同等采样预算下，其解与最优解的差距控制在5%-10%以内，优于直接模拟量子协议和贪心基线算法。正如预期，模拟退火在该规模下仍是基于采样的最强求解器。这些结果表明：通过将量子采样器有效嵌入经典优化框架，既能保留形式化保证，又能以更少量子资源获得近优解。