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

Application of quantum approximate optimization algorithm in max independent set problem

作　　者：段孟环 李志强[1] 郭玲玲 Duan Menghuan;Li Zhiqiang;Guo Lingling(College of Information Engineering,Yangzhou University,Yangzhou Jiangsu 225100,China)

机构地区：[1]扬州大学信息工程学院,江苏扬州225100

出　　处：《计算机应用研究》2023年第9期2646-2649,2673,共5页Application Research of Computers

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

摘　　要：最大独立集问题是著名的NP问题,并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题,提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型,推导出最大独立集问题的哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用COBYLA经典优化算法对参数量子门中的参数进行优化,并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明,使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解,实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。The max independent set problem is a well-known NP problem and has applications in many scenarios.Traditional exact algorithms need exponential time complexity to solve the max independent set problem.In order to solve the max independent set problem more efficiently,this paper proposed a quantum circuit solution based on the quantum approximate optimization algorithm.In this scheme,it derived the Hamiltonian expression of the max independent set problem from the mathema-tical model of the max independent set,and designed the quantum circuit based on the quantum approximation optimization algorithm.It used the COBYLA classical optimization algorithm to optimize the parameters in the parameter quantum gate,and used the quantum development framework Qiskit provided by IBM to conduct simulation experiments.Simulation results show that the solution of the max independent set problem can be obtained in polynomial time with high probability using the quantum approximate optimization algorithm,achieving an exponential speedup.Quantum approximate optimization algorithm is feasible and effective for solving the max independent set problem.

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

分 类 号：O4[理学—物理]