量子科技中心_量科网

整数规划（IP）是一种NP难组合优化问题，被广泛应用于金融、工程、物流和运筹学等多个领域的现实问题建模。由于该问题的复杂度随规模呈指数级增长，传统算法难以高效求解。现有大多数量子算法通过将整数编码为量子比特来实现求解，但存在严重的资源效率低下问题。goswami2024integer研究通过将整型变量映射至量子多态位（qudit）解决了资源效率问题，但因缺乏多qudit可扩展性而无法编码更大规模问题，实际应用价值有限。本研究基于goswami2024integer的思路进行扩展，提出一种基于量子电路的可扩展算法，利用多交互qudit实现了量子加速。该算法包含三个核心组件：高效分离可行域与不可行域的蒸馏函数、成本函数的相位-振幅编码，以及结合多控制单量子比特旋转的量子相位估计优化模块。研究证明该算法测量得到最优解的概率最大，其时间复杂度为O(d^(n/2) + m·n²·log(d) + n/ϵ_QPE)，其中n为变量数，d为整数值域，m为约束条件数，ϵ_QPE为精度。相较于经典穷举法复杂度O(d^n)和最优经典精确算法复杂度O((log(n))^(3n))，该算法在求解一般多项式整数规划问题时，时间复杂度关于n的维度实现了d^(n/2)量级的降低。