计算机工程

作者：王富民, 倪明, 周明, 吴永政

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

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

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

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

来源：2020年第1期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第1期