耦合强度对量子绝热算法求解最大割的影响

• 作者: 高薪凯 倪明 周明 吴永政
• 来源期刊: 计算机系统应用
• 关键词: 量子绝热算法 最大割问题 耦合强度 哈密顿量 期望值
• 年，卷（期）: 2021,（4）
• 所属期刊栏目: 软件技术·算法|Software Technique · Algorithm
• 页码范围: 125-130
• 页数: 6页
• 语种: 中文
• DOI: 10.15888/j.cnki.csa.007867

摘要

本文分析基于量子绝热近似的不同顶点的最大割问题求解.该算法将无向图的顶点等效为量子比特,各个顶点间的边等效为两个量子比特之间的耦合,边的权重值等效为量子比特间的耦合强度.采用Python语言编写算法程序,模拟了6–13个顶点的完全无向图的最大割问题求解情况.实验结果表明,当完全无向图顶点个数取为8,12,13,同时耦合强度为1.0时,所求解最大割问题哈密顿量的期望值不收敛.进一步调整模拟计算中量子比特间耦合强度数值,观察期望值变化.实验发现,对于顶点数为12的完全无向图,耦合强度取0.95时,其期望值获得收敛.对于顶点数为8和13的完全无向图情形,当耦合强度取0.75时,所计算得到的期望值随演化时间变化收敛.由此推测超过13个顶点的完全无向图在用量子绝热算法求解最大割问题时,可将量子比特耦合强度归一化到0.75左右,使期望值有效收敛.