量子科技中心_量科网

过去几十年间，运筹学领域已开发出众多高效的优化算法，然而量子计算作为一种新兴计算范式，正展现出更高效处理优化问题的潜力。Grover算法为组合优化问题提供了可证明的加速，但其电路深度超出了当前含噪声中等规模量子（NISQ）设备的承受范围。一个更易实现的替代方案是将优化问题重新表述为二次无约束二元优化（QUBO）问题并应用量子退火；然而，现有硬件仍无法处理实际规模的问题实例。该团队提出AtomTreeSearch，一种混合经典-量子算法，该算法在蒙特卡洛树搜索框架中集成了一个可原生实现于中性原子量子计算机的量子子程序。在每次扩展步骤中，选取由量子处理器提供的候选动作的最大加权独立集，并执行这些集体动作以获得子节点。该研究以旅行商问题为基准，在随机欧几里得实例中测试了多达60个城市，在TSPLIB实例中测试了多达100个城市。该混合算法在这些实例上的表现普遍优于或持平于OR-Tools和模拟退火，且研究发现量子子程序相比经典替代子程序能够生成更多样且更高质量的分支。这些结果表明，将精心设计的量子子程序嵌入经典搜索框架，是通向近期量子计算在组合优化中发挥实用价值的可行路径。