基于利润松弛框架的约束组合优化问题量子近似优化方法

《IEEE Transactions on Quantum Engineering》：The Art of Avoiding Constraints: A Penalty-free Approach to Constrained Combinatorial Optimization with QAOA

　　

摘要：

量子近似优化算法（QAOA）旨在确定二次（及高阶）无约束二进制优化（QUBO或HUBO）问题的最优和近似最优解，这些问题可以准确建模无约束组合优化问题。对于无约束组合优化问题，其解空间由目标函数决策变量的所有可能组合组成，而对于约束组合优化问题，解空间仅由满足问题约束的解组成。虽然以最优方式解决这样的QUBO问题可以得到底层约束问题的最优解，但设置正确的惩罚参数至关重要。此外，找到确保近似最优解的合适惩罚参数也很有挑战性。在本文中，我们介绍了创新的利润松弛框架来解决约束组合优化问题。我们有效的量子-经典混合方法将选定的约束组合优化问题转化为无约束利润问题，使得两个问题的解空间与其解质量相关。我们的方法使我们能够确定约束问题的最优和近似最优解。我们使用三个NP难问题——最小顶点覆盖、最大独立集和最大团——来演示我们方法的可行性和有效性。我们在两个不同平台上对我们的利润松弛框架进行了详细的性能评估：Xanadu PennyLane和Argonne QTensor量子电路模拟器。我们的研究结果提供了使用原生QAOA构建和求解约束组合优化问题的宝贵见解。