QAOA最大切割问题的类Dijkstra优化及实现  

QAOA maximum cutting problem analogous to Dijkstra optimization and implementation

作　　者：潘文杰 李志强[1] 杨辉[1] Pan Wenjie;Li Zhiqiang;Yang Hui(College of Information Engineering,Yangzhou University,Yangzhou Jiangsu 225100,China)

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

出　　处：《计算机应用研究》2023年第2期378-382,共5页Application Research of Computers

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

摘　　要：最大切割问题是可以用量子近似优化算法(QAOA)来解决的典型问题,Ansatz线路构造为该算法的重要组成部分。为了减少多种图结构在QAOA中的构造代价和提高其稳定性,从线路的可优化性出发进行分析,结合Dijkstra算法的点边存放特点,提出了该线路的类Dijkstra优化算法,并将其应用于QAOA最大切割问题。使用Qiskit量子框架来模拟优化算法的正确性,并用IBM Quantum Composer的真实环境进行对比实验来验证优化的稳定性。与未优化的线路相比,此优化算法下的CNOT门能减少约40%,其稳定性也得到了明显的提高。结果表明类Dijkstra优化算法可以适用于QAOA最大切割问题的多种图结构优化。The maximum cut problem is a typical problem in the quantum approximate optimization algorithm(QAOA),and Ansatz circuit is an important part of the algorithm.In order to reduce the construction cost of various graph structures in QAOA and improve its stability,this paper analyzed the optimizability of the circuit,combined the point edge storage characteristics of Dijkstra algorithm,proposed a Dijkstra-like optimization algorithm for the circuit,and applied it to the QAOA maximum cut problem.The paper used the Qiskit quantum framework to simulate the correctness of the optimization algorithm and used the real environment of IBM Quantum Composer to perform comparative experiments to verify the stability of the optimization.After comparing with the initial algorithm,the proposed algorithm reduced the CNOT gate by about 40%and significantly improves its stability.The results show that the Dijkstra-like optimization algorithm can optimize the QAOA maximum cut pro-blem of multiple graph structures.

关 键 词：量子信息 量子近似优化算法 量子线路 最大切割问题 IBM Quantum 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]