量子科技中心_量科网

整数线性规划（ILP）是离散优化问题中一种灵活且普遍应用的模型。尽管求解ILP属于NP难问题，但其实际应用价值巨大。针对多约束ILP的经典算法具有全局性和穷举性特点，而能实现超二次加速的量子框架则依赖于目标函数与可行集的局部结构特性，这使得获得ILP的超二次量子加速长期面临挑战。本研究通过为Gomory群松弛设计量子算法来解决该问题——群松弛通过放宽线性规划（LP）松弛最优解中正值变量的非负约束，同时保留决策变量的整数性来获得。该团队提出了一种具有竞争力的经典局部搜索算法（保持群松弛可行性），并在合理技术条件下实现了对应量子算法的超二次加速。当群松弛满足类似于（但强于）LP非退化条件的非退化性时，该方法可直接获得原ILP的最优解；否则群松弛会收紧ILP最优目标值的界限，并通过减小整数间隙提升后续分支切割法的效率——该团队在多个实际相关ILP案例中验证了这一现象。为实现这些结果，该团队还推导出具有优良谱特性且可高效构建的约束保持混频器（对群松弛而言），这本身也具有独立研究价值。