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

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

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

计算机工程杂志要求:

{1}文献按作者姓氏的第一个字母依A－Z顺序分中、英文两部分排列，中文文献在前，英文文献在后。引文中的英文书名及期刊名用斜体，论文题目写入“”号内。

{2}来稿应是未以任何形式公开发表过的论文，亦不接受一稿多投的文章。稿件寄出1个月未接到本刊通知即可自行处理。

{3}本刊已许可中国知网以数字化方式复制、汇编、发行、信息网络传播本刊全文。如有异议，请在投稿时说明，本刊将按作者说明处理。

{4}标题之下如“(1)(2)”和“①②”序数不分行显示。

{5}作者简介：第一作者姓名（出生年月），性别，毕业院校及学位，职称，研究方向。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社