量子近似优化算法在指挥控制组织任务规划中的应用

张毅军 慕晓冬 刘潇文 王星宇 东晨 吴田宜 李凯

1) (火箭军工程大学研究生院,西安 710025)

2) (火箭军工程大学,西安 710025)

3) (国防科技大学信息通信学院,西安 710106)

4) (空军工程大学信息与导航学院,西安 710077)

指挥控制组织中的任务规划问题可以映射为变量较多、求解难度较大的组合优化问题.采用传统具有启发性列表规划方法解决这一问题面临求解时间复杂度高、实时响应性较差等问题.本文针对指挥控制组织中任务规划问题提出一种基于量子近似优化算法的量子线路求解方案.首先将任务规划问题转化为组合优化中的精确覆盖问题,通过构建相应的数学模型推导出精确覆盖问题的量子近似优化算法对应的末态哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用动量梯度下降法算法对量子逻辑门中的参数进行优化,并利用本源量子开发的量子软件开发环境进行仿真实验.仿真结果表明:该量子线路方案可以用于求解任务规划问题,同时降低了算法的时间复杂度,一定程度上提升了资源利用率,为进一步应用量子算法求解指挥控制组织中的任务规划问题打下基础.

1 引言

指挥控制(command and control,C2)组织是军事领域面向特定的使命任务,为实现作战资源有序利用,通过多种关联关系有机结合战场上各单元而形成的作战组织实体[1].C2 组织通过构建平台与任务之间的执行关系、决策实体与平台之间的指挥控制关系、各个决策实体之间的协作关系等实现面向任务的组织结构设计[2].其中,平台与任务之间执行关系（即任务规划问题）是C2 组织设计中的首要环节,属于涉及变量最多、求解难度最大的组合优化问题.

C2 组织中的任务规划问题需要在充分考虑平台资源、位置,任务资源、位置等制约因素前提下,优化平台与任务、平台与平台之间的各种关系.这属于大规模组合优化问题的范畴,也是NP 问题.解决此类问题一般主要采用具有启发性的列表规划方法进行求解.这些方法包括动态层级规划算法(dynamic level scheduling,DLS)[3]、多维动态列表规划算法 (multidimensional dynamic list scheduling,MDLS)[4]、多优先级列表动态规划算法 (multi-PRI list dynamic scheduling,MPLDS)[5].这些方法通常都是以整个任务完成时间最短或者以资源的充分利用为目标求解问题.以MDLS和MPLDS方法为例,两种方法的时间复杂度为其中m为平台数量,n为任务数量.而C2 组织中的任务规划问题往往对时间要求较高,特别是在战时,需要复杂度更低的算法来解决.随着量子计算机硬件的发展,一些在经典超级计算机上都很难模拟的量子算法现在可以在量子计算机上运行[7].如文献[8-13]显示,目前,量子近似优化算法(quantum approximate optimization algorithm,QAOA)[14]有望在量子计算机上实现,其理论基础已被谷歌、IBM、本源量子等研究机构在量子计算机上进行了实验验证.它是一种用于解决组合优化问题的启发式混合量子经典算法,由爱德华·法希等首次提出,可以看作是绝热量子计算的时间离散化[15].QAOA 最初主要应用于最大切割问题的求解,被证明对求解速度相对于现有经典算法而言具有指数级加速[16-18].近年来研究成果表明[19-24],QAOA可以用来求解精确覆盖问题.精确覆盖问题本质属于NP 问题[25],在经典计算机上需要指数级时间开销;而对于量子计算机来说,只需要多项式级时间开销就可以求解.这为C2 组织任务规划问题求解提供了一定的理论借鉴.为了缩短任务规划问题的求解时间,采用QAOA 求解C2 组织中的任务规划问题是一种有意义的且可行的方法.

本文通过对C2 组织中的任务规划问题进行分析和简化,将该问题映射成为一个组合优化中的精确覆盖问题;在上述构建问题数学模型的基础上,推导出QAOA 对应的末态哈密顿量表示形式;设计适用于求解C2 组织中的任务规划问题的QAOA 对应量子线路;通过采用经典优化算法对量子线路参数进行优化,采用本源量子开发的pyQPanda 量子软件开发环境在Python3 中进行仿真,并对结果进行分析讨论.

2 C2 组织中的任务规划问题的转化

本文以最小化整个任务流程完成时间为优化目标构建模型,用P表示平台集合,用A表示任务集合.用Fap=1 表示p平台执行a任务,用Fap=0 表示p平台没有执行a任务.用Cp=1 表示p平台被选中执行任务,用Cp=0 表示p平台没有被选中执行任务.Tap表示p平台执行a任务所用的时间.Tp表示p平台执行完分配的任务所用时间.T表示指挥控制组织系统完成所有任务所用时间.需要说明的是,为更好构建模型,对平台资源进行了约束,假设所选平台都可以独立完成任务.C2 组织任务规划通用模型如下所示:

其中目标函数是最小化整个任务流程完成时间,约束条件(2)式确保每一个任务都有且仅有一个平台执行,约束条件(3)式限制Fap和Cp的取值范围.

准确高效地求解上述模型是实现C2 组织任务规划的关键.为提高模型求解效率、缩短问题求解时间,实现任务尽可能及时准确被执行,将问题转化为在确保所有任务被执行的前提下,在已有的平台执行方案中选出满足(2)式和(3)式约束条件的解决方案.而这些已有的平台执行方案都是从经过优化的平台执行方案数据库中随机选取的,将问题转化成一个精确覆盖问题不仅可以确保所有任务被执行,还可以减少平台需求数量,提升平台利用率.

3 基于QAOA 的C2 任务规划问题求解

根据文献[26,27]论述的研究内容,大部分的NP 完全问题和NP 问题(包括精确覆盖问题)都可以生成对应的经典伊辛模型.而根据文献[25,28]论述的研究内容,经典伊辛模型可以通过定义旋转算子的方式转化为量子伊辛模型,而通过量子伊辛模型可以描述量子系统的哈密顿量.这样就可以将求解NP 问题与求解量子伊辛模型对应的哈密顿量的本征态或最小能量状态联系起来,使采用QAOA进行求解问题成为可能.本文将精确覆盖问题的量子伊辛模型对应的哈密顿量表示如下:

Hc为目标哈密顿量(也是QAOA 对应的末态哈密顿量),n和j分别表示第n个和第j个量子比特位,它们的取值范围为 1≤n,j≤N;和表示作用在第n个量子比特位和第j个量子比特位上的泡利Z算符;Gnj和qn为相关系数,属于常量.

3.1 任务规划问题对应的伊辛模型

如前所述,求出问题的解,必须满足(2)式和(3)式的约束,所以以(2)式和(3)式为基础推导该问题对应的伊辛模型.首先在(2)式两边同时减1;然后在(2)式两边同时进行平方;最后在所有任务上进行累加运算,可以得出如下表达式:

其中|P|表示平台集合P的数量,|A|表示任务集合A的数量.如果(5)式等于0,那么所有约束条件都能得到满足.下面用旋转变量Sp ∈{-1,1}代替Cp ∈{0,1},公式如下:

而后将(6)式代入(5)式,并将(5)式展开,可以得出如下表达式:

如果用泡利旋转算子替换(11)式中的旋转变量,就可以得到形如 (4)式的精确覆盖问题的量子伊辛模型对应的哈密顿量表达式.此表达式中的常量只改变哈密顿量的整体相位,而对哈密顿量对应的本征态或最小能量状态没有影响.

3.2 基于QAOA 算法的求解思路

首先我们需要制备一个初态,即一个均匀分布的量子叠加态|+〉⊗N;然后需要以HC和HB两个哈密顿量为生成元制备两个酉变换,它们分别为

(15)式中 (γ*,β*)为参数γ和β经过优化后所取得数值.

基于QAOA 的任务规划问题求解过程如图1所示,主要由量子处理器和经典处理器两部分组成.经典处理器部分为辅助模块,主要采用经典优化方法对参数γ和β进行优化,辅助量子处理器部分完成对酉变化中参数γ和β取值的调整;量子处理器部分为主体模块,主要采用QAOA 算法进行量子态演化和问题求解.

图1 QAOA 实现框架示意图Fig.1.Schematic diagram of the QAOA implementation.

3.3 基于QAOA 的量子线路设计方案

与经典计算相对应,量子计算机通过量子线路来执行程序.为了使QAOA 在量子软件开发环境中运行,需要设计相应的量子线路.

本文设计的QAOA 量子线路主要包含三个环节,如图2所示.首先是制备量子初态|+〉⊗N,主要通过给每个量子比特作用一个H门来实现.然后实现以HC和HB两个哈密顿量为生成元,得到两个酉变换乘积的累积U(γ,β),

图2 基于QAOA 的4 个量子比特量子线路图Fig.2.Four-qubit quantum circuit based on QAOA.

(16)式中k代表演化的步数,两个酉变换之间的乘积代表每一步对应的量子线路;βi和γi为每一步对应的参数.一般演化的步数越大,量子线路得到的效果就越好.最后采用计算基进行测量.其中第一部分和第三部分都比较容易实现,下面重点推导第二部分的量子线路.

对于以HB为生成元、参数为βi的酉变换,将哈密顿量HB的值代入,可以推导出一组 RX 门操作.推导如下:

对于以HC为生成元,参数为γi的酉变换,将哈密顿量HC的值代入,可以推导出 CNOT门和RZ 门的组合操作以及一组 RZ 门单独操作.推导如下:

如图2所示,环节2 为演化步数为1 时对应的量子线路图.如果演化步数为k时,对应的第二部分量子线路重复k次.

4 仿真结果与分析

4.1 迭代次数的优化与分析

本文对6 种平台12 种任务的C2 组织任务规划问题进行实验研究,问题相关信息在表1中详细列出.在整个实验过程中,为了使QAOA 得到理想的结果,在经典计算部分必须能够取得较优的(γ*,β*)数值.这部分通常采用的经典优化算法有梯度下降算法、Broyden-Fletcher-Goldfarb-Shanno(BFGS)算法[29]、Nelder-Mead 算法[30]和贝叶斯优化算法[31],采用动量梯度下降法,在Python3 运行环境下实现.为了得到较优的 (γ*,β*),我们在经典优化过程中分别将迭代次数设置为10,20,30,40,50,60,70,80,90和100 进行计算,并对结果进行对比分析.

表1 平台对应可执行任务分配方案Table 1.Platforms corresponding executable mission allocation.

图3所示为迭代次数为10,20,30,40,50,60,70,80,90和100 情况下,演化步数k从2 至12,目标函数对应的损失值（因为目标函数对应的损失值趋近于负的const,所以目标函数绝对值越大表示得到的 (γ*,β*) 数值越优,取得正确解的概率越大）.水平坐标分别表示迭代次数和演化步数,纵坐标表示目标函数对应的损失值.图3中结果显示在演化步数相同的情况下,迭代次数为50 对应的损失值的绝对值普遍高于其他迭代次数对应的损失值的绝对值.这是因为随着迭代次数增大,算法在计算的过程中出现了过拟合现象.如图4所示为在演化步数为12 时,迭代次数分别为50,60,70,80,90和100 对应损失值的曲线图.而在迭代次数相同的情况下,随着演化步数增加,对应损失值的绝对值也随之增加,这与相关理论完全吻合.所以,在接下来的实验中,将迭代次数设置为50 进行实验研究.

图3 不同迭代次数和演化步数对应的损失值Fig.3.Loss values corresponding to different iterations and evolution steps.

图4 演化步数为12,迭代次数分别为50-100 对应的损失值Fig.4.The corresponding loss values with 12 evolution steps and 50-100 iterations,respectively.

4.2 仿真结果分析

本文主要利用本源量子开发的pyQPanda 量子软件开发环境在Python3 中对上述设计的量子线路进行仿真实现.图5表示的是在迭代次数为50 情况下,2 至12 指定演化步数对应的问题正确解概率.图5显示随着演化步数的增加,问题正确解概率随着增大,在演化步数为12 时取得了最大值(89%).图6显示了迭代次数为50,演化步数为12 对应的测量结果.从结果可以得出,本文中提出的基于QAOA 的求解方案可以用于求解C2 组织中任务规划问题.

图5 迭代次数为50,演化步数为2 至12 对应的问题正确解概率Fig.5.The accuracy of the QAOA with 50 iterations and 2-12 evolution steps.

图6 迭代次数为50,演化步数为12 对应的测量结果Fig.6.Results with 50 iterations and 12 evolution steps.

4.3 基于QAOA 的求解方案复杂度分析

采用了动量梯度下降法对量子线路中的参数进行优化,属于启发式策略优化方法.结合文献[32]的研究内容和本文仿真实验设计,提出的基于QAOA 的量子线路求解方案的时间复杂度为O[poly(k)],其中k为上述中的演化步数.而传统的求解算法时间复杂度为,其中m为平台数量,n为任务数量.所以,随着平台和任务数量的增加,基于QAOA 的量子线路求解方案的时间复杂度要优于传统求解算法时间复杂度.

5 结论

本文根据C2 组织中的任务规划问题特点,将其转化成组合优化中的精确覆盖问题.通过理论推导提出了一种基于QAOA 算法的量子线路求解方案,并利用经典优化算法对量子逻辑门中的参数进行优化,在本源量子开发的pyQPanda 量子软件开发环境中进行仿真编译.仿真结果表明,本文提出的基于QAOA 的量子线路设计及方法可以有效求解C2 组织中的任务规划问题,为提高任务规划问题的求解速度提供了理论支撑.经过分析,本文所采用的QAOA 算法是一种普适的方法.实际中能转化为组合优化中的精确覆盖问题的实际问题都可以尝试采用本文的求解方案进行求解.下一步将通过采用一些群智能算法[33]进一步优化适用于求解任务规划问题的QAOA 算法设计与实现,在降低经典计算部分复杂度的同时提高参数的优化效果;另一方面对量子线路中的量子逻辑门进行优化,在降低演化步数的同时提高计算的正确率.

感谢国防科技大学信息通信学院刘雍讲师、王勋讲师的讨论和帮助.