量子近似优化算法在最大独立集中的应用

来源：计算机应用研究杂志2023年第9期北京时间：

作者：段孟环,李志强,郭玲玲,

单位：扬州大学信息工程学院,江苏扬州225100；

摘要：最大独立集问题是著名的NP问题，并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题，提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型，推导出最大独立集问题的哈密顿量表达式；设计了基于量子近似优化算法的量子线路，采用COBYLA经典优化算法对参数量子门中的参数进行优化，并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明，使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解，实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。

关键词：最大独立集,量子近似优化算法,量子线路,Qiskit,

基金资助：国家自然科学基金资助项目(61070240,62071240)；江苏省高校基金资助项目(10KJB520021)；；