-
题名量子近似优化算法在最大独立集中的应用
被引量：1
- 1
-
-
作者
段孟环
李志强
郭玲玲
-
机构
扬州大学信息工程学院
-
出处
《计算机应用研究》
CSCD
北大核心
2023年第9期2646-2649,2673,共5页
-
基金
国家自然科学基金资助项目(61070240,62071240)
江苏省高校基金资助项目(10KJB520021)
-
文摘
最大独立集问题是著名的NP问题,并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题,提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型,推导出最大独立集问题的哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用COBYLA经典优化算法对参数量子门中的参数进行优化,并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明,使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解,实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。
-
关键词
最大独立集
量子近似优化算法
量子线路
Qiskit
-
Keywords
max independent set problem
quantum approximate optimization algorithm
quantum circuit
Qiskit
-
分类号
O4
[理学—物理]
-
