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

摘要：

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

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

所属期刊栏目：40

分类号：O4(物理学)

资助基金：国家自然科学基金;国家自然科学基金;江苏省高校基金资助项目

在线出版日期：2023-10-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2646-2649,2673