量子科技中心_量科网

针对二元优化问题的量子算法已得到广泛研究，然而量子算法在整数优化问题中的应用仍相对空白。该工作研究了应用于图结构整数问题的量子近似优化算法（QAOA），其中每个整数变量均编码于一个量子位中。研究人员推导出任意规模高围长d-正则图上深度p的QAOA期望值的通用迭代公式，该公式计算成本随QAOA深度p呈指数增长，但与图规模无关。通过对Max-k-Cut问题在p≤4时的公式评估，该团队发现当参数范围为（k=3且度数d≤10；k=4且d≤40）时，QAOA表现优于提供最佳最坏情况近似比保证的Frieze-Jerrum半定规划（SDP）算法。为强化经典基准线，研究人员提出基于饱和度启发式的新算法，其实证表现优于Frieze-Jerrum算法和浅层QAOA。但数值证据表明，QAOA在深度p≤20时可能反超该启发式算法。这些成果表明，突破二元问题转向整数优化领域有望开辟量子优势的新路径。