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

doi:10.19678/j.issn.1000-3428.0055347

计算机工程 ›› 2020, Vol. 46 ›› Issue (1): 25-30. doi: 10.19678/j.issn.1000-3428.0055347

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

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

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

收稿日期:2019-07-01 修回日期:2019-09-18 出版日期:2020-01-15 发布日期:2019-09-24
作者简介:王富民(1995-),男,硕士研究生,主研方向为量子算法;倪明,研究员;周明,高级工程师、博士;吴永政,博士。
基金资助:
中国电子科技集团公司第三十二研究所创新基金（EX170410-00）。

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

摘要/Abstract

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

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

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

中图分类号:

TP391

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

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.

https://www.ecice06.com/CN/Y2020/V46/I1/25

图/表 7

20200115083304

20200115083307

20200115083311

20200115083314

20200115083317

20200115083320

20200115083323

参考文献

[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.

选择文件类型/文献管理软件名称

选择包含的内容

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

Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张然, 高莹雪, 赵钰, 丁元明. 基于Q学习量子蚁群的微纳卫星路由算法[J]. 计算机工程, 2022, 48(3): 162-169,188.
[2]	喻志超, 李扬中, 刘磊, 冯圣中. 量子计算模拟及优化方法综述[J]. 计算机工程, 2022, 48(1): 1-11.
[3]	陈振宇,杨阳,季赛,刘文杰. 基于量子委托计算模式的半量子密钥协商[J]. 计算机工程, 2018, 44(3): 178-181,188.
[4]	张弘弛,刘百祥,文捷. 量子非局域性与量子通信复杂度研究[J]. 计算机工程, 2018, 44(12): 28-32.
[5]	卫佳,倪明,周明,江文兵. 基于IBM Q平台的量子算法研究[J]. 计算机工程, 2018, 44(12): 6-12.
[6]	栾添,张雪松,陈徐宗. 量子气体在光晶格中的一维玻色-哈伯德模型模拟[J]. 计算机工程, 2018, 44(12): 1-5.
[7]	沙林秀，贺昱曜. 一种新的自适应量子遗传算法[J]. 计算机工程, 2013, 39(9): 218-221.
[8]	戴勇谦, 张明武, 祝胜林, 戴勇新. 基于变异概率分析的改进QGA及其应用[J]. 计算机工程, 2013, 39(7): 247-251,256.
[9]	赵程程, 杨亚涛, 李子臣, 阎晓姮. 基于McEliece公钥密码体制的盲签名算法[J]. 计算机工程, 2013, 39(6): 146-149.
[10]	黄俊华, 唐平, 陈松龄, 江小平, 梁英蓬. 量子遗传算法在口腔种植定位中的研究与应用[J]. 计算机工程, 2013, 39(1): 208-212.
[11]	曹斯彤, 陈贤富. 一种新型量子演化算法及其应用研究[J]. 计算机工程, 2012, 38(24): 188-190.
[12]	鲁晓彬, 李发达, 田礼, 鲍皖苏. 一种改进的多变量数字签名方案安全性分析[J]. 计算机工程, 2012, 38(22): 95-98.
[13]	张建航, 胡予濮, 来齐齐. 基于高斯抽样算法的NTRU类数字签名方案[J]. 计算机工程, 2012, 38(17): 126-128.
[14]	孙昌毅, 李益发, 斯雪明. 基于多变量公钥密码体制的代理重签名方案[J]. 计算机工程, 2012, 38(17): 116-118.
[15]	曹军宏, 韦灼彬, 高屹, 张宁. 基于量子遗传算法的盲源分离时延优选[J]. 计算机工程, 2012, 38(11): 170-172,176.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 15

编辑推荐

Metrics

本文评价