求解整数线性规划问题的量子近似优化算法  

Quantum approximate optimization algorithm for integer linear pro⁃gramming problem

作　　者：戚晗 何婉莹 邱涛 Abdullah Gani QI Han;HE Wan-ying;QIU Tao;Abdullah Gani(College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China;Faculty of Computing and Informatics,University Malaysia Sabah,Kota Kinabalu 87000,Malaysia)

机构地区：[1]沈阳航空航天大学计算机学院,沈阳110136 [2]马来西亚沙巴大学计算机与信息学院,亚庇87000

出　　处：《沈阳航空航天大学学报》2023年第3期28-36,共9页Journal of Shenyang Aerospace University

基　　金：国家自然科学基金(项目编号:62002245);辽宁省教育厅科学基金(项目编号:LJKZ0208)。

摘　　要：量子近似优化算法是一种量子经典混合算法,它可以在多项式时间内求得组合优化问题的最优解。但是在低迭代水平时,得到问题最优解的概率较低。为了应对这一挑战,基于改进的目标哈密顿量,设计了一种具有较少量子门的量子线路,简化了求解过程,提高了求解精度。通过求解整数线性规划问题进行实验,以验证所提出解决方案的可靠性,实验部署在本源量子的pyQpanda环境中。结果表明,平均执行时间为原始时间的20.8%,概率由54.1563%提高到82.9%。The Quantum approximate optimization algorithm is a quantum-classical hybrid algorithm,which can obtain the optimal solution of combinatorial optimization problems in polynomial time.But at a low level of iteration,there is no guarantee that the problem will be solved optimally.A quantum circuit with fewer quantum gates based on the revised target Hamiltonian was developed by this study to address this difficulty,the solution procedure was streamlined and solution precision was boosted.In order to verified the reliability of the proposed solution,experiments were carried out by solving the integer linear programming problem.The experiment was deployed in the Pyqpanda environment of the origin quantum.The findings show that the average execution time is 20.8%of the original,and the probability is enhanced from 54.1563%to 82.9%.

关 键 词：量子计算 量子近似优化算法 整数线性规划 伊辛模型 哈密顿量 

分 类 号：TP3-05[自动化与计算机技术—计算机科学与技术]