求解整数线性规划问题的量子近似优化算法.pdf
《求解整数线性规划问题的量子近似优化算法.pdf》由会员分享,可在线阅读,更多相关《求解整数线性规划问题的量子近似优化算法.pdf(9页珍藏版)》请在咨信网上搜索。
1、第40卷 第3期2 0 2 3 年 6 月沈 阳 航 空 航 天 大 学 学 报Journal of Shenyang Aerospace UniversityVol.40 No.3Jun.2 0 2 3求解整数线性规划问题的量子近似优化算法戚晗1,何婉莹1,邱涛1,Abdullah Gani2(1.沈阳航空航天大学 计算机学院,沈阳 110136;2.马来西亚沙巴大学 计算机与信息学院,亚庇 87000)摘要:量子近似优化算法是一种量子经典混合算法,它可以在多项式时间内求得组合优化问题的最优解。但是在低迭代水平时,得到问题最优解的概率较低。为了应对这一挑战,基于改进的目标哈密顿量,设计了一种
2、具有较少量子门的量子线路,简化了求解过程,提高了求解精度。通过求解整数线性规划问题进行实验,以验证所提出解决方案的可靠性,实验部署在本源量子的pyQpanda环境中。结果表明,平均执行时间为原始时间的20.8%,概率由54.156 3%提高到82.9%。关键词:量子计算;量子近似优化算法;整数线性规划;伊辛模型;哈密顿量中图分类号:TP3-05 文献标志码:Adoi:10.3969/j.issn.2095-1248.2023.03.004Quantum approximate optimization algorithm for integer linear programming probl
3、emQI Han 1,HE Wan-ying1,QIU Tao1,Abdullah Gani 2(1.College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China;2.Faculty of Computing and Informatics,University Malaysia Sabah,Kota Kinabalu 87000,Malaysia)Abstract:The Quantum approximate optimization algorithm is a quantum-classi
4、cal 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
5、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
6、 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.156 3%to 82.9%.Key words:quantum computing;quantum approximate optimization algorithm;integer linear programming;Ising model;Hamiltonian收稿日期:2
7、023-02-21基金项目:国家自然科学基金(项目编号:62002245);辽宁省教育厅科学基金(项目编号:LJKZ0208)作者简介:戚晗(1982-),男,黑龙江铁力人,副教授,博士,主要研究方向:量子机器学习、移动云计算、网络安全,E-mail:。文章编号:2095-1248(2023)03-0028-09戚晗,等:求解整数线性规划问题的量子近似优化算法第 3 期近年来,物联网、移动边缘计算、车载自组织网络(vehicular ad hoc network,VANET)发展迅速,随之而来的一些基站和服务器选址、资源分配调度等问题受到广泛关注。这些问题可以理解为在有限的可供选择的方案中,寻
8、找满足一定约束的最好方案,因此类似此类问题可以归结为整数线性规划问题1。整数线性规划问题属于线性规划中的一种,其中又分为二元整数线性规划、混合整数线性规划等。随着问题规模的扩大,在约束条件的限制下寻找到整数线性规划问题最优解的时间复杂度较高。随着“噪声中尺度量子”时代2的快速发展,量子优化算法逐渐受到关注,量子近似优化算法(quantum approximate optimization algorithm,QAOA)在 2014年由 Farhi 等提出3,被认为是在近年可以实现量子霸权的算法之一4。Willsch等5、Herrman等6以最大切割问题和2-SAT问题为例分析了QAOA的性能,
9、发现在D-Wave量子退火计算机上的性能优于量子计算机模拟器。Bengtsson 等7使用超导量子处理器实现QAOA,可以提高找到精确覆盖问题最优解的成功概率。QAOA 变分态的对称性会使算法本身有一定的局限性,但是基于伊辛模型的 QAOA 优于原始 QAOA,且优于Williamson 算法8。目前,QAOA 被用于解决许多组合优化问题,使用QAOA找到问题全局最优解的概率比较依赖于量子线路的迭代次数(即步长P)。然而,当QAOA的步长P很低时,找到近似最优解的概率很小。Azad等9在使用QAOA解决车辆路径规划问题时,迭代24次找到最优解的概率约为30%,当迭代次数更高时,概率并没有达到较
10、高的水平。Zhang等10在使用QAOA解决最小顶点覆盖问题时,迭代2次时,概率低于20%;迭代10次时,概率可以达到约80%。Vikstl 等11在使用QAOA解决精确覆盖问题时,在迭代2次时的单次测量下,找到最优解的概率为 8.97%,需要重复多次测量才能提高概率。此外,QAOA还被应用于哈密顿回路问题12和最大权独立集问题13。尽管成功概率因不同问题而异,但QAOA无疑是解决组合优化问题的一种较好的方法。2020年,Choi等13针对无线自组织网络中簇头选择的问题,采用量子经典混合方法求解簇头选择策略。为了让所选择的簇头具有较高的能效,将此问题定义为最大加权独立集问题,运用QAOA求解最
11、佳策略。2022年,Fan等 14使用QAOA解决图计算中最短路径问题,结果显示,QAOA在参数选择和步长选择上优于经典算法和基于Grover的最短路径算法,且需要的量子比特数更少。2023年,Soloviev等15为了解决许多传统方法无法解决的贝叶斯网络结构学习问题,采用基于 3n(n-1)/2个量子比特的QAOA进行求解(其中n为贝叶斯网络中的节点数量)。结果显示,在任何数据集上的性能都要优于经典和其他量子方法。在缩短整数线性规划问题的求解时间方面,QAOA是一种有意义且可行的解决方法。本文针对整数线性规划问题,提出一种基于改进目标哈密顿量的QAOA的量子线路方法,提高在低迭代时找到最优解
12、的概率并缩短程序执行时间。通过构造与整数线性规划问题对应的数学模型,将经典伊辛模型量子化,得到本文所要解决问题的目标哈密顿量。推导哈密顿量对应的量子门线路,并减少线路中使用的量子门数量。本文使用本源量子的pyQpanda框架进行模拟,验证了改进目标哈密顿量对找到基态概率和执行时间的影响。1资源分配问题的整数线性规划公式为了便于理解这一类场景下的整数线性规划问题,本文以车载自组织网络为例进行说明。通过车载自组织网络实现车辆之间通信可以有效地避免出现交通拥堵和事故,因为司机可以获得超出可视范围内的实时路况信息。但是远距离车辆无法直接通信,需要合作通信29沈 阳 航 空 航 天 大 学 学 报第 4
13、0 卷来获取信息,合作通信需要使用中继车辆节点的资源,但每辆车的剩余资源、移动速度和位置都是不固定的。在这种情况下,需要考虑中继节点如何选择。如果中继节点集中在一辆车上,那么会造成这辆车过载,从而导致通信失败,所以中继节点的负载平衡十分重要,需要合理分配中继节点的资源。针对资源分配下的整数线性规划问题,本文以源节点代表需要请求计算资源的设备,以目标节点代表提供计算资源的设备。假设目标节点具有相同的资源,源节点的资源需求量不同,那么影响延迟的主要因素即为通信距离。但是当目标节点的资源不足以处理所有请求时,会产生排队延迟。现在用G表示整个网络,V表示所有源节点的集合,R表示所有目标节点的集合,d表
14、示源节点和目标节点之间的通信距离。资源分配的目的是实现负载均衡的同时尽量减少通信延迟。每个源节点的资源需求表示为vl,xvr为二元决策变量。如果源节点与目标可以相连,则xvr为1,否则为0。此问题可以表述为minvrGvlvxvr(1)可选取的目标节点不确定是否每个都可以与全部源节点连接,但是需要确保总有一个目标节点可以为其提供资源。通信条件相同的情况下,访问距离越短,访问延迟越小,且距离越短,可以连接的概率也越大,所以将源节点与目标节点之间的距离表示为dvr,xvr同样为二元决策变量。如果源节点与目标连接,xvr为1,否则为0,此问题可以表述为minvrGdvrxvr(2)约束条件可以表述为
15、vrGxvr=n(3)式中:n为源节点的数目。式(1)和(2)为本文中的目标,式(3)为约束条件,即一个源节点只能分配给一个目标,不能分配给多个目标,规划范围内的所有源节点都要与相对应的目标连接,即所有源节点的请求都会受到相对应的目标的处理。与源节点相连的目标应该处理其所有的请求服务;一个目标节点可管理多个源节点;不考虑源节点与源节点之间、目标与目标之间的链路。2基于伊辛模型的量子近似优化算法对于同一个问题,当设置的目标哈密顿量不同时,结果是不同的。在解决整数线性规划问题时,设置了两个不同的目标哈密顿量。一种是仅为问题函数(用Hp表示)求解目标哈密顿量;另一种是将问题函数和变形约束求和,并忽略
16、公式中的常数,以获得改进的目标哈密顿量(用Hc表示)。以上两种方法用于设置不同的目标哈密顿量,为比较实验做准备。QAOA 的核心是通过从初始哈密顿量的基态,经过P步迭代演化至目标哈密顿量的基态,在这个过程中需要使用经典计算来完成参数的更新。图1为QAOA的算法结构图,它的线路是以初始量子态为生成元的酉变换和以目标量子态为生成元的酉变换乘积的累积。Hb为初始哈密顿量,以Hb为生成元的酉变换等于e-iHbi,Hp为目标哈密顿量,以Hp为生成元的酉变换为e-iHpi。其中i和i所代表的是不同的变分参数。图1QAOA的算法结构图30戚晗,等:求解整数线性规划问题的量子近似优化算法第 3 期对于目标哈密
17、顿量的设定,采用伊辛模型来实现,本文所描述问题的目标哈密顿量可以表示为HA+HB16,其中 HA=Aj=1m bj-i=1NSjixi2HB=-Bi=1Ncixi(4)使用二元决策变量xr01代替自旋变量sr-11,即xr=sr+12(5)2.1设置目标哈密顿量设置目标哈密顿量H HP P在资源分配整数线性规划问题中,主要考虑两个方面,即通信延迟和工作负载。本文将通信延迟转化为通信距离,以HA为目标哈密顿量;将工作负载转化为源节点的需求量,以HB为目标哈密顿量。将公式展开,得到问题中HA+HB=v=1V 1-r=1Rdvrxvr2+v=1Vr=1Rvlvxvr=14v=1Vr=1Rd2vrs2
18、vr+12v=1Vr=1R(d2vr-dvr)svr+v=1V(r=1Rdvr-2)+v=1Vr=1Rvlvsvr2+v=1Vvlv2(6)让A、B、C、D、E为A=14v=1Vr=1Rd2vrB=12v=1Vr=1R(d2vr-dvr)C=v=1V(r=1Rdvr-2)D=12v=1VvlvE=12v=1Vvlv(7)式中:C和E是常数,将自旋变量变为自旋泡利矩阵sizi,即得到最终目标哈密顿量Hp=v=1VrRAvrzvzr+v=1RBvzv+C+v=1VDvzv+E(8)由于绝热量子计算和量子门电路模型的计算能力相同17,本文将使用门电路构造QAOA的线路,经过推导,最终得到基于伊辛模型
19、的目标哈密顿量是19个CNOT门、CZ门和RZ门的组合,如式(9)所示U(Hpi)=e-iHpi=e-ii(AvrvrGzvzr+Bvr=1R+Cv=1VI+Dvv=1Vzv+Er=1RI)=vrGe-ii(Avrzvzr+Bvzv+CI+Dvzv+EI)(9)2.2改进目标哈密顿量改进目标哈密顿量H Hc c根据资源分配问题的定义,本文将目标哈密顿量改进为原始目标函数与约束条件函数之和,可以表述为=v=1V 1-r=1Rdvrxvr2+v=1Vr=1Rvlvxvr+v=1Vr=1R(xvr-n)2=v=1Vr=1R(14d2vr+14)s2vr+v=1Vr=1R(-dvr+12d2vr)sv
20、r+14v=1Vr=1Rd2vr-v=1Vr=1Rdvr+1+v=1Vr=1R(12v lv-n+12)svr+v=1Vvlv2+n 2-n+14(10)其中A、B、C、D、E为A=v=1Vr=1R(14d2vr)+14B=v=1Vr=1R(-dvr+12d2vr)C=14v=1Vr=1Rd2vr-v=1Vr=1Rdvr+1D=v=1Vr=1R(12vlv)-n+12E=v=1Vvlv2+n2-n+14(11)式中:C和E为常数,它只与哈密顿量的相位有关,对本征态没有影响10,所以可以进一步将其简化为H(s1.sN)=v=1Vr=1RAvrsvsr+v=1RBvsv+v=1VDvsv(12)将
21、自旋变量变为自旋泡利矩阵sizi,即得到最终目标哈密顿量,如式(13)所示Hc=v=1Vr=1RAvrzvzr+v=1RBvzv+v=1VDvzv(13)经过推导,目标函数Hc可以表示为 5 个CNOT门、RZ门组合,如式(14)所示31沈 阳 航 空 航 天 大 学 学 报第 40 卷U(Hci)=e-iHci=e-ii(v=1Vr=1RAvrzvzr+v=1RBvzv+v=1VDvzv)=vrGe-ii(Avrzvzr+Bvzv+Dvzv)=vrGCNOT(vr)RZ(j2iAvr)CNOT(vr)vrGRZ(i2iBv)vrGRZ(i2iDv)(14)2.3初始哈密顿量初始哈密顿量设定初
22、始哈密顿量为泡利X算符在每个量子位上的和,如式(15)所示Hb=i=0n-1xi(15)其基态是泡利算符对应特征能量的张量积,如式(16)所示0=+n(16)经过推导初始哈密顿量是H门操作,原始QAOA和改进QAOA的初始哈密顿量均为Hb。3仿真实验本文使用基于 python的本源量子的 pyQpanda 框架来执行 QAOA,并解决整数线性规划问题下的资源分配优化问题实例(4,2)。其中,4表示源节点的数量,2表示目标节点的数量。实验所需的实际量子位N根据源节点和目标节点之间的通信链路确定。当源节点请求目标节点的资源时,中间距离对通信延迟和连接的可能性都有影响。如果距离超过其覆盖区域,则无法
23、利用目标节点的资源。例如(4,2),使用式(17)来描述问题(它是归一化数据),相应连接如图2所示,覆盖区域分别表示E和F的可连接范围。M=0.4310.250.570.810.330.380.29(17)如图2所示,A和F之间的距离太大,超出了 F的通信覆盖范围,从而阻止了链路连接。实际距离应为,因此式(17)中使用 1表示无连接。为了编码这个问题,将每个量子位分配给图2中的每个链路,即如果使用了链路,则意味着对应的二进制决策变量为1,否则为0。为了使用QAOA,必须采取以下步骤:(1)初始化线路,并加入初始哈密顿量基态所对应的量子门;(2)通过初始化待优化的参数和来确定量子门的初始旋转角度
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 求解 整数 线性规划 问题 量子 近似 优化 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。