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

摘要：

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

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

所属期刊栏目：46

分类号：TP391(计算技术、计算机技术)

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

在线出版日期：2020-03-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：25-30