面向最优路径问题的量子近似优化算法研究

作     者：王婷 

作者单位：沈阳航空航天大学 

学位级别：硕士

导师姓名：拱长青;闻英友

授予年度：2022年

学科分类：07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：最优路径 量子近似优化算法 哈密顿路径 伊辛模型 

摘      要：近年来,组合优化问题得到广泛研究,主要应用于车辆路径规划、无线调度等工程问题。其中最优路径问题在工程领域中较难解决,主要是因为求解过程中易陷入局部最优解以及得到正确解的概率较低。针对上述问题,本文采用量子近似优化算法(quantum approximate optimization algorithm,QAOA)来解决最优路径问题。它将量子算法和经典优化器结合,利用了量子计算较高的并行计算能力,目的是使得QAOA能够以较高的概率得到最优路径问题的解决方案。首先,通过分析最优路径问题的特点,将其转化为组合优化问题中的哈密顿路径问题,并设定目标函数和问题约束条件。其次,根据目标函数和约束条件提出了两种不同的目标哈密顿量设定方法,同时引入了伊辛模型,并对设定的目标哈密顿量映射到伊辛模型上进行了理论推导。然后,理论证明了目标哈密顿量和初始哈密顿量对应的量子门,并设计了适用于求解最优路径问题的量子线路。通过实验比较不同优化器和不同步长对QAOA性能的影响,并分别对软件定义网络(software-defined network,SDN)架构下数据包转发的静态最优路径问题和动态最优路径问题进行求解,进一步在外卖送餐问题上验证不同目标哈密顿量对问题求解结果的影响。实验结果表明,本文提出的两种方法设定的两个不同目标哈密顿量均能正确地求解问题,但是在求得正确解的概率上不同。第一种方法设定的目标哈密顿量正确求解的概率是42.30%,第二种则是99.59%。两者相比,第二种方法设定的改进的目标哈密顿量减少了局部最优解的概率,并能够以一个较高的概率求得问题的正确解。