量子科技中心_量科网

针对二元优化问题的量子算法已得到广泛研究，然而量子算法在整数优化问题中的应用仍相对空白。本工作研究了应用于图结构整数问题的量子近似优化算法（QAOA），其中每个整数变量编码于一个量子位（qudit）中。该团队推导出适用于任意规模高围长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。但数值证据表明，在深度p≤20时QAOA可能反超该启发式算法。这些结果表明，突破二元问题转向整数优化领域，有望开辟量子优势的新途径。