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

• 作者: 倪明 吴永政 周明 王富民
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 量子计算 量子绝热近似 最大割问题 哈密顿量 量子软件
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 热点与综述
• 页码范围: 25-30
• 页数: 6页
• 分类号: TP391
• 字数: 3993字
• 语种: 中文
• DOI: 10.19678/j.issn.1000-3428.0055347

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	倪明	中国电子科技集团公司第三十二研究所	24	151	5.0	11.0
2	周明	中国电子科技集团公司第三十二研究所	15	17	2.0	3.0
3	王富民	中国电子科技集团公司第三十二研究所	1	0	0.0	0.0
4	吴永政	中国电子科技集团公司第三十二研究所	1	0	0.0	0.0