量子绝热近似求解最大割问题的最优解  

Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation

作　　者：王富民 倪明[1] 周明 吴永政 WANG Fumin;NI Ming;ZHOU Ming;WU Yongzheng(The 32nd Research Institute of China Electronics Technology Group Corporation,Shanghai 201808,China)

机构地区：[1]中国电子科技集团公司第三十二研究所

出　　处：《计算机工程》2020年第1期25-30,共6页Computer Engineering

基　　金：中国电子科技集团公司第三十二研究所创新基金(EX170410-00)

摘　　要：经典近似算法求解最大割问题时,时间复杂度与图的复杂度呈正相关。为提高求解效率,使用量子绝热近似算法求解无向图最大割问题哈密顿量的基态,其基态对应该问题的最优解。该算法的时间复杂度不依赖于图的顶点个数及边的条数,可以在有限步骤内计算得到最大割解。基于ProjectQ量子软件进行编程模拟,建立由初始哈密顿量线性变化到最大割问题哈密顿量的演化路径,分析该路径下最大割问题哈密顿量期望值的变化,判断算法能否求出最优解。数值分析结果表明,量子绝热近似算法能够以较高准确率计算出最大割解,其求解3个顶点无向图和6个顶点无向稀疏图最大割问题的准确率为0.9999,求解6个顶点无向完全图最大割问题的准确率为0.9696。When using classical approximation algorithm to solve the max-cut problem,the time complexity increases with the complexity of graph.In order to improve the solution efficiency,this paper uses quantum adiabatic approximation algorithm to solve the ground state for Hamiltonian of max-cut problem,and the ground state value is the optimal solution.The time complexity is independent of the number of vertices and edges of graph using quantum adiabatic approximation algorithm,and the max-cut problem can be calculated within finite steps.The computing process is based on the ProjectQ software developed.By establishing the evolutionary path from initial Hamiltonian to max-cut problem Hamiltonian,the change of the expected value is analyzed to determine whether the algorithm can find the optimal solution of max-cut problem or not.Numerical analysis results show that,this algorithm can effectively improve the efficiency of solving the max-cut problem,the accuracy of solution is 0.9999 for 3-vertex undirected graph and 6-vertex undirected sparse graph,and the results for the 6-vertex undirected complete graph is 0.9696.

关 键 词：量子计算 量子绝热近似 最大割问题 哈密顿量 量子软件 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]