量子绝热演化求解最大割的研究

作     者：高薪凯 

作者单位：中国电子科技集团公司电子科学研究院 

学位级别：硕士

导师姓名：倪明

授予年度：2021年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 081104[工学-模式识别与智能系统] 08[工学] 070201[理学-理论物理] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0702[理学-物理学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：量子计算 最大割 量子绝热演化算法 低温超导量子计算机 

摘      要：本文主要研究量子绝热演化算法在求解最大割时出现的算法精确度下降问题,利用Project Q量子编程架构编写相关求解程序,并针对四种影响因子进行测试研究,从而提出一种对量子绝热演化算法的改进方案。求解程序构造一个绝热演化的量子系统,根据相关的量子逻辑线路使系统的量子态由一个简单态不断向最大割问题哈密顿量的基态靠近,该基态则对应了最大割问题的一个解。量子绝热演化算法最终输出系统在演化结束后所处的量子态,从而得到一个近似解,并且根据待求解问题哈密顿量对应的期望值变化情况判断该近似解是否为最优解。本文利用该求解程序在经典计算机上模拟量子系统的绝热演化,并计算了顶点数为3到13的完全无向图对应的最大割问题求解过程。测试结果表明对于3、4、5、6、7、9、10和11个顶点的最大割问题,量子绝热演化算法能以较高的精确度给出最优解;而量子绝热演化算法在求解顶点数为8、12和13的完全无向图对应的过程中,出现最大割问题哈密顿量的期望值的变化曲线与最优情况不相符,量子系统的能量在绝热演化过程中并未始终处于最低能级,算法的精确度大大降低,输出结果只能以小概率为最优解。本文根据相关理论针对量子绝热演化算法研究了四种影响因子,分别为演化次数、演化路径、哈密顿量以及耦合强度。并根据这四种影响因子对于出现算法精确度降低的三种完全无向图进行调整测试。对比测试结果发现增加演化次数与设置简单的演化路径并未使得算法的精确度提高,改进哈密顿量只在部分情况下有所改进,而将最大割问题中的耦合强度映射到一个较小区间内,最大割问题哈密顿量的期望值变化情况满足算法精确度的要求,映射耦合强度可作为改进方案。此外本文针对低温超导量子计算机根据目前使用的相关硬件设备设计了一套相应的体系结构。该体系结构同时包含经典计算以及量子计算两大部分,前者作为主控端控制整个量子计算机的运行,后者则作为一个协同处理端,专门以量子计算方式处理大规模数据计算。量子协同处理端又可拆分下来与不同经典计算机相连接组成完整的量子计算机。在这种混合体系结构下,量子计算机的指令集系统同样分为量子指令与经典指令。由于当前相关技术的限制,低温超导量子计算机只能初步组建成型,尚且只能实现一些简单的量子逻辑门操作,不能运算量子算法,因此本文简单介绍了未来量子绝热演化算法在量子计算机上的运算过程。