Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation

doi:10.19678/j.issn.1000-3428.0055347

Computer Engineering ›› 2020, Vol. 46 ›› Issue (1): 25-30. doi: 10.19678/j.issn.1000-3428.0055347

Previous Articles Next Articles

Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation

WANG Fumin, NI Ming, ZHOU Ming, WU Yongzheng

The 32nd Research Institute of China Electronics Technology Group Corporation, Shanghai 201808, China

Received:2019-07-01 Revised:2019-09-18 Online:2020-01-15 Published:2019-09-24

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

王富民, 倪明, 周明, 吴永政

中国电子科技集团公司第三十二研究所, 上海 201808

作者简介:王富民(1995-),男,硕士研究生,主研方向为量子算法;倪明,研究员;周明,高级工程师、博士;吴永政,博士。
基金资助:
中国电子科技集团公司第三十二研究所创新基金（EX170410-00）。

Abstract

Abstract: 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.999 9 for 3-vertex undirected graph and 6-vertex undirected sparse graph,and the results for the 6-vertex undirected complete graph is 0.969 6.

Key words: quantum computing, quantum adiabatic approximation, max-cut problem, Hamiltonian, quantum software

摘要： 经典近似算法求解最大割问题时，时间复杂度与图的复杂度呈正相关。为提高求解效率，使用量子绝热近似算法求解无向图最大割问题哈密顿量的基态，其基态对应该问题的最优解。该算法的时间复杂度不依赖于图的顶点个数及边的条数，可以在有限步骤内计算得到最大割解。基于ProjectQ量子软件进行编程模拟，建立由初始哈密顿量线性变化到最大割问题哈密顿量的演化路径，分析该路径下最大割问题哈密顿量期望值的变化，判断算法能否求出最优解。数值分析结果表明，量子绝热近似算法能够以较高准确率计算出最大割解，其求解3个顶点无向图和6个顶点无向稀疏图最大割问题的准确率为0.999 9，求解6个顶点无向完全图最大割问题的准确率为0.969 6。

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

CLC Number:

TP391

WANG Fumin, NI Ming, ZHOU Ming, WU Yongzheng. Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation[J]. Computer Engineering, 2020, 46(1): 25-30.

王富民, 倪明, 周明, 吴永政. 量子绝热近似求解最大割问题的最优解[J]. 计算机工程, 2020, 46(1): 25-30.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0055347

http://www.ecice06.com/EN/Y2020/V46/I1/25

Figures/Tables 7

References

[1] PETROV S.Image segmentation with maximum cuts[D].Berkeley,USA:University of California at Berkeley,2005.
[2] WANG Wei,LIU Bo,YANG Ming,et al.Max-cut based overlapping channel assignment for 802.11 multi-ratio wireless mesh networks[C]//Proceedings of IEEE International Conference on Computer Supported Cooperative Work in Design.Washington D.C.,USA:IEEE Press,2013:662-667.
[3] CHEN Ning,LI Zifen,CHEN Jinzhu.Solutions to max-cut problem using five different intelligent algorithms[J].Journal of Naval Aeronautical Engineering Institute,2009,24(4):447-452.(in Chinese)陈宁,黎子芬,陈金柱.五种智能算法解决最大割问题分析与比较[J].海军航空工程学院学报,2009,24(4):447-452.
[4] SUN Ting,LI Gaidi,XU Wenqing.Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations[J].Operations Research Transactions,2016,20(3):21-32.(in Chinese)孙婷,李改弟,徐文青.最大割问题和最大平分割问题基于半定规划松弛的近似算法[J].运筹学学报,2016,20(3):21-32.
[5] GOEMANS M,WILLIAMSON D.0.879-approximation algorithms for MAX-CUT and MAX 2SAT[C]//Proceedings of the 26th Annual ACM Symposium on the Theory of Computing.New York,USA:ACM Press,1994:422-431.
[6] ASANO T.An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT[J].Theoretical Computer Science,2005,354(3):339-353.
[7] LI Huazhong.Quantum adiabatic theorem (II):approximate and applicable conditions[J].Physics,2007,36(1):26-31.(in Chinese)李华钟.量子绝热定理(II):近似和适用条件[J].物理,2007,36(1):26-31.
[8] NIELSEN M A,CHUANG I L.Quantum computation and quantum information[M].Cambridge,UK:Cambridge University Press,2011.
[9] FARHI E,GOLDSTONE J,GOSSET D,et al.Quantum adiabatic algorithms,small gaps,and different paths[EB/OL].[2019-06-02].https://arxiv.org/pdf/0909.4766.pdf.
[10] HEN I,YOUNG A P.Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems[J].Physical Review E:Statistical Nonlinear and Soft Matter Physics,2011,84(6 Pt 1):1-5.
[11] MCGEOCH C C,CONG W.Experimental evaluation of an adiabiatic quantum system for combinatorial optimization[C]//Proceedings of ACM International Conference on Computing Frontiers.New York,USA:ACM Press,2013:1-5.
[12] STEIGER D S,HÄNER T,TROYER M.ProjectQ:an open source software framework for quantum computing[EB/OL].[2019-06-02].https://arxiv.org/abs/1612.08091v1.
[13] CORNISH M,BROWN M,JAIN A,et al.An open source software framework for the implementation of an open systems architecture,run-time system[C]//Proceedings of AUTOTESTCON'12.Washington D.C.,USA:IEEE Press,2012:1-3.
[14] GYONGYOSI L.Quantum circuit designs for gate-model quantum computer architectures[EB/OL].[2019-06-02].https://arxiv.org/pdf/1803.02460v1.pdf.
[15] WEI Jia,NI Ming,ZHOU Ming.Research of quantum algorithm based on IBM Q platform[J].Computer Engineering,2018,44(12):6-12.(in Chinese)卫佳,倪明,周明,等.基于IBM Q平台的量子算法研究[J].计算机工程,2018,44(12):6-12.
[16] FARHI E,GOLDSTONE J,GUTMANN S.A quantum approximate optimization algorithm[EB/OL].[2019-06-02].https://arxiv.org/pdf/1411.4028.pdf.
[17] ZHANG J,RIEFFEL E G,WANG Z.A QAOA-inspired circuit for Grover's unstructured search using a transverse field[EB/OL].[2019-06-02].https://arxiv.org/abs/1702.02577v1.
[18] HAN Yongjian,LI Chuanfeng,GUO Guangcan.The principle and development of quantum computation[J].Science and Technology Review,2017,35(23):70-75.(in Chinese)韩永建,李传锋,郭光灿.量子计算原理及研究进展[J].科技导报,2017,35(23):70-75.
[19] XI Zhengjun,LI Yongming.Measurement-based quantum circuits model[J].Journal of Computer Research and Development,2011,48(11):2155-2160.(in Chinese)席政军,李永明.基于测量的量子线路[J].计算机研究与发展,2011,48(11):2155-2160.
[20] SUN Jie.Research on quantum search algorithm based on adiabatic evolution[D].Wuhan:Huazhong University of Science and Technology,2013.(in Chinese)孙杰.基于绝热演化的量子搜索算法研究[D].武汉:华中科技大学,2013.

Please choose a citation manager

Content to export