| 量子绝热近似求解最大割问题的最优解 |
| |
| 引用本文： | 王富民,倪明,周明,吴永政.量子绝热近似求解最大割问题的最优解[J].计算机工程,2020,46(1):25-30. |
| |
| 作者姓名： | 王富民 倪明 周明 吴永政 |
| |
| 作者单位： | 中国电子科技集团公司第三十二研究所,上海 201808;中国电子科技集团公司第三十二研究所,上海 201808;中国电子科技集团公司第三十二研究所,上海 201808;中国电子科技集团公司第三十二研究所,上海 201808 |
| |
| 基金项目： | 中国电子科技集团公司第三十二研究所创新基金 |
| |
| 摘 要： | 经典近似算法求解最大割问题时,时间复杂度与图的复杂度呈正相关。为提高求解效率,使用量子绝热近似算法求解无向图最大割问题哈密顿量的基态,其基态对应该问题的最优解。该算法的时间复杂度不依赖于图的顶点个数及边的条数,可以在有限步骤内计算得到最大割解。基于ProjectQ量子软件进行编程模拟,建立由初始哈密顿量线性变化到最大割问题哈密顿量的演化路径,分析该路径下最大割问题哈密顿量期望值的变化,判断算法能否求出最优解。数值分析结果表明,量子绝热近似算法能够以较高准确率计算出最大割解,其求解3个顶点无向图和6个顶点无向稀疏图最大割问题的准确率为0.999 9,求解6个顶点无向完全图最大割问题的准确率为0.969 6。
|
| 关 键 词： | 量子计算 量子绝热近似 最大割问题 哈密顿量 量子软件 |
Optimal Solution of Max-Cut Problem Using Quantum Adiabatic Approximation |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
