量子科技中心_量科网

最大割（MaxCut）是图论中经典的NP难组合优化问题，其应用范围涵盖从物理学到生物信息学等多个领域。尽管变分量子算法提供了有望超越经典方案的新途径，但受限于资源约束和可训练性问题（如贫瘠高原现象），使得该问题在含噪声中等规模量子（NISQ）设备上难以处理大规模实例。本研究提出了一种针对大规模MaxCut问题的增强型分布式变分量子本征求解器，通过整合新型经典-量子混合扰动策略扩展了先前的分布式框架，显著提升了优化可扩展性和效率。该算法仅需10个量子比特即可求解包含1000个顶点的加权MaxCut实例，数值结果表明其性能始终优于Goemans-Williamson算法。研究人员进一步采用热启动初始化策略，以Goemans-Williamson算法的高质量解作为初始种子，实验结果证实经典最优解可被有效进一步优化。该算法在人类ABCA1基因测序数据的单倍型定相（haplotype phasing）应用中展现出实用价值，所获高质量单倍型可与Goemans-Williamson算法经过10^6次投影所得结果相媲美。这些成果确立了该算法作为兼容NISQ设备、可扩展的近期量子增强型大规模组合优化框架的地位。