量子科技中心_量科网

本论文提出量子-经典分支定价（QCBP）算法，这是一种用于中性原子量子处理器（QPUs）上解决顶点着色问题的混合量子经典算法。QCBP将量子计算嵌入经典分支定价（BP）框架中，以解决传统BP算法的三个瓶颈：定价子问题（PSPs）的计算成本、分支效率和原始启发式质量。该算法采用基于量子绝热算法（QAA）的量子辅助列生成（CG）技术，通过采样高质量最大权重独立集（MWIS），减少重复求解NP难PSPs的需求。改进后的分支策略利用量子生成的独立集探索更少节点、收紧下界并加速收敛。经典原始启发式方法能快速基于量子生成集构建可行解，避免不必要的量子调用或额外整数线性规划（ILP）求解。相较于该团队先前的混合列生成（HCG）和基于最大独立集的分支定界（BBQ-mIS），QCBP在量子资源利用率和求解质量上均有提升。大量实验表明QCBP显著优于HCG和BBQ-mIS，在约98%的基准实例中达到最优解。中性原子量子硬件的初步验证表明，该方法对量子噪声和硬件限制具有鲁棒性，支持实际应用及向更大规模图实例的扩展。QCBP作为一种可行的组合优化混合方法，在近期量子硬件上展现出优异的可扩展性。