量子科技中心_量科网

量子近似优化算法（QAOA）在组合优化领域被广泛研究，其理论保证和实际性能均取得显著进展。然而针对一般组合优化问题，固定轮次QAOA的预期性能与经典可模拟性仍不明确。聚焦Max-Cut问题，该研究团队首先证明：对于任意固定轮次p≥2的通用图，在给定角度精确计算固定轮次QAOA期望值属于NP难问题；而当顶点数n的加性误差逼近2^-O(n)时，该近似计算亦为NP难问题。为评估QAOA预期性能，研究人员提出基于树分解的动态规划算法。作为衍生成果，当p-局部树宽随顶点数呈对数增长时，该算法可在图规模n的多项式时间内实现精确计算。除Max-Cut外，该工作还将框架扩展至一般二元无约束组合优化问题（BUCO）。最后，团队在广义Petersen图GP(15,2)、双层三角2-提升图和截角二十面体图C60等典型结构化图谱上，对p≤3的轮次进行了可复现评估，并在与局域性匹配的经典基线对比中报告了切割比率。