删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

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

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

English Abstract


全文HTML

--> --> -->
1.引　言
指挥控制(command and control, C2)组织是军事领域面向特定的使命任务, 为实现作战资源有序利用, 通过多种关联关系有机结合战场上各单元而形成的作战组织实体[1]. C2组织通过构建平台与任务之间的执行关系、决策实体与平台之间的指挥控制关系、各个决策实体之间的协作关系等实现面向任务的组织结构设计[2]. 其中, 平台与任务之间执行关系（即任务规划问题）是C2组织设计中的首要环节, 属于涉及变量最多、求解难度最大的组合优化问题.
C2组织中的任务规划问题需要在充分考虑平台资源、位置, 任务资源、位置等制约因素前提下, 优化平台与任务、平台与平台之间的各种关系. 这属于大规模组合优化问题的范畴, 也是NP问题. 解决此类问题一般主要采用具有启发性的列表规划方法进行求解. 这些方法包括动态层级规划算法 (dynamic level scheduling, DLS)[3]、多维动态列表规划算法 (multidimensional dynamic list scheduling, MDLS)[4]、多优先级列表动态规划算法 (multiPRI list dynamic scheduling, MPLDS)[5]. 这些方法通常都是以整个任务完成时间最短或者以资源的充分利用为目标求解问题. 以MDLS和MPLDS方法为例, 两种方法的时间复杂度为$ O\left(m\cdot {n}^{2}\right) $[4-6], 其中$ 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 $表示任务集合. 用$ {F}_{ap} $ = 1表示$ p $平台执行$ a $任务, 用$ {F}_{ap} $ = 0表示$ p $平台没有执行$ a $任务. 用$ {C}_{p} $ = 1表示$ p $平台被选中执行任务, 用$ {C}_{p} $ = 0表示$ p $平台没有被选中执行任务. $ {T}_{ap} $表示$ p $平台执行$ a $任务所用的时间. $ {T}_{p} $表示$ p $平台执行完分配的任务所用时间. $ T $表示指挥控制组织系统完成所有任务所用时间. 需要说明的是, 为更好构建模型, 对平台资源进行了约束, 假设所选平台都可以独立完成任务. C2组织任务规划通用模型如下所示:
$\begin{split}{\rm{Minimize}}\;T =\;& {{\rm{max}}}_{p \in P} \left( {\sum\limits_{a \in A} {{T_{ap}}} {F_{ap}}{C_p}} \right),\\&\forall~ p \in P,\end{split}$
${\rm{Subject \;to }}\;\sum\limits_{p \in P} {{F_{ap}}} {C_p}{\rm{ = 1,}}\;\;\;\;\;\;\forall~ a \in A,$
${F_{ap}}{{,}}~{C_p} \in \left\{ {0,} \right.\left. 1 \right\},$
其中目标函数是最小化整个任务流程完成时间, 约束条件(2)式确保每一个任务都有且仅有一个平台执行, 约束条件(3)式限制$ {F}_{ap} $和$ {C}_{p} $的取值范围.
准确高效地求解上述模型是实现C2组织任务规划的关键. 为提高模型求解效率、缩短问题求解时间, 实现任务尽可能及时准确被执行, 将问题转化为在确保所有任务被执行的前提下, 在已有的平台执行方案中选出满足(2)式和(3)式约束条件的解决方案. 而这些已有的平台执行方案都是从经过优化的平台执行方案数据库中随机选取的, 将问题转化成一个精确覆盖问题不仅可以确保所有任务被执行, 还可以减少平台需求数量, 提升平台利用率.
3.基于QAOA的C2任务规划问题求解
根据文献[26, 27]论述的研究内容, 大部分的NP完全问题和NP问题(包括精确覆盖问题)都可以生成对应的经典伊辛模型. 而根据文献[25, 28]论述的研究内容, 经典伊辛模型可以通过定义旋转算子的方式转化为量子伊辛模型, 而通过量子伊辛模型可以描述量子系统的哈密顿量. 这样就可以将求解NP问题与求解量子伊辛模型对应的哈密顿量的本征态或最小能量状态联系起来, 使采用QAOA进行求解问题成为可能. 本文将精确覆盖问题的量子伊辛模型对应的哈密顿量表示如下:
$ {H}_{\mathrm{C}}=\sum \limits_{n < j}{G}_{nj}{\mathrm{\sigma }}_{n}^{Z}{\mathrm{\sigma }}_{j}^{Z}+\sum \limits _{n=1}^{N}{q}_{n}{\mathrm{\sigma }}_{n}^{Z}\text{,} $
$ {H}_{\mathrm{c}} $为目标哈密顿量(也是QAOA对应的末态哈密顿量), $ n $和$ j $分别表示第$ n $个和第$ j $个量子比特位, 它们的取值范围为$1\leqslant n, j\leqslant N$; $ {\mathrm{\sigma }}_{n}^{Z} $和$ {\mathrm{\sigma }}_{j}^{Z} $表示作用在第$ n $个量子比特位和第$ j $个量子比特位上的泡利$ Z $算符; $ {G}_{nj} $和$ {q}_{n} $为相关系数, 属于常量.
2
3.1.任务规划问题对应的伊辛模型
-->

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

如前所述, 求出问题的解, 必须满足(2)式和(3)式的约束, 所以以(2)式和(3)式为基础推导该问题对应的伊辛模型. 首先在(2)式两边同时减1; 然后在(2)式两边同时进行平方; 最后在所有任务上进行累加运算, 可以得出如下表达式:
$ \mu \left({C}_{1},\cdots,{C}_{\left|P\right|}\right)=\sum \limits _{a=1}^{\left|A\right|}{\left(\sum \limits _{p=1}^{\left|P\right|}{F}_{ap}{C}_{p}-1\right)}^{2}\text{,} $
其中$ \left|P\right| $表示平台集合$ P $的数量, $ \left|A\right| $表示任务集合$ A $的数量. 如果(5)式等于0, 那么所有约束条件都能得到满足. 下面用旋转变量$ {S}_{p}\in \left\{-1, \right.\left.1\right\} $代替 $ {C}_{p}\in \left\{0, \right.\left.1\right\} $, 公式如下:
$ {C}_{p}= ({{S}_{p}+1})/{2}\text{.} $
而后将(6)式代入(5)式, 并将(5)式展开, 可以得出如下表达式:
$ \begin{split} &\mu \left({C}_{1},\cdots,{C}_{\left|P\right|}\right)=\sum \limits _{a=1}^{\left|A\right|}{\left(\sum \limits _{p=1}^{\left|P\right|}{F}_{ap}\frac{{S}_{p}+1}{2}-1\right)}^{2}\\=\;&\frac{1}{4}\sum \limits _{a=1}^{\left|A\right|}\sum \limits _{p=1}^{\left|P\right|}\sum \limits _{p{'}=1}^{\left|P\right|}{F}_{ap}{F}_{ap{'}}{S}_{p}{S}_{p{'}}\\&+\frac{1}{2}\sum \limits _{a=1}^{\left|A\right|}\sum \limits _{p=1}^{\left|P\right|}{F}_{ap}{S}_{p}\left(\sum \limits _{p{'}=1}^{\left|P\right|}{F}_{ap{'}}-2\right)\\&+\frac{1}{4}\sum \limits _{a=1}^{\left|A\right|}{\left(\sum \limits _{p=1}^{\left|P\right|}{F}_{ap}-2\right)}^{2}\text{.}\\[-15pt]\end{split} $
设${G}_{pp{'}}$和$ {q}_{p} $分别为
$ {G}_{pp{'}}=\frac{1}{2}\sum \limits _{a=1}^{\left|A\right|}{F}_{ap}{F}_{ap{'}}\text{,} $
$ {q}_{p}=\frac{1}{2}\sum \limits _{a=1}^{\left|A\right|}{F}_{ap}\left(\sum \limits _{p{'}=1}^{\left|P\right|}{F}_{ap{'}}-2\right)\text{.} $
由于$\dfrac{1}{4}\displaystyle\sum \limits _{a=1}^{\left|A\right|}{\left(\displaystyle\sum \limits _{p=1}^{\left|P\right|}{F}_{ap}-2\right)}^{2}$为常数, 所以(7)式可变换为
$\begin{split} &\mu \left({C}_{1},\cdots,{C}_{\left|P\right|}\right)\\=&\frac{1}{2}\sum \limits _{p=1}^{\left|P\right|}\sum \limits _{p{'}=1}^{\left|P\right|}{G}_{pp{'}}{S}_{p}{S}_{p{'}}+\sum \limits _{p=1}^{\left|P\right|}{q}_{p}{S}_{p}+\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\text{.} \\[-10pt]\end{split}$
${G}_{pp{'}}$具有对称性, (10)式可以进一步变化为
$\begin{split} &\mu \left({C}_{1},\cdots,{C}_{\left|P\right|}\right)\\=&\sum \limits _{p < p{'}}{G}_{pp{'}}{S}_{p}{S}_{p{'}}+\sum \limits _{p=1}^{\left|P\right|}{q}_{p}{S}_{p}+\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\text{.} \end{split}$
如果用泡利旋转算子替换(11)式中的旋转变量, 就可以得到形如 (4)式的精确覆盖问题的量子伊辛模型对应的哈密顿量表达式. 此表达式中的常量只改变哈密顿量的整体相位, 而对哈密顿量对应的本征态或最小能量状态没有影响.
2
3.2.基于QAOA算法的求解思路
-->

3.2.基于QAOA算法的求解思路

首先我们需要制备一个初态, 即一个均匀分布的量子叠加态${|+ \rangle}^{ \otimes N}$; 然后需要以$ {H}_{\mathrm{C}} $和$ {H}_{\mathrm{B}} $两个哈密顿量为生成元制备两个酉变换, 它们分别为
$\begin{split} U\left({H}_{\mathrm{C}},{\gamma }_{i}\right)=\;&{\mathrm{e}}^{-\mathrm{i}{\gamma }_{i}{H}_{\mathrm{C}}},~~ U\left({H}_{\mathrm{B}},{\beta }_{i}\right)={\mathrm{e}}^{-\mathrm{i}{\beta }_{i}{H}_{B}},\\&i=\mathrm{1,2},\cdots,k\text{.} \end{split}$
$ {H}_{\mathrm{C}} $为(4)式表示的哈密顿量, $ {\gamma }_{i} $为参数; $ {H}_{B} $为初态量子叠加态${| + \rangle}^{ \otimes N}$对应的哈密顿量, 等于$\displaystyle\sum \nolimits _{n=1}^{N}{\mathrm{\sigma }}_{n}^{X}$, 即所谓的混合哈密顿量, $ {\beta }_{i} $为参数. 交替使用含有参数的$ U\left({H}_{\mathrm{C}}, {\gamma }_{i}\right) $和$ U\left({H}_{\mathrm{B}}, {\beta }_{i}\right) $两个酉变换作用于量子叠加态${| +\rangle }^{ \otimes N}$. 当交替次数为$ k $时, 得到的量子态如下:
$\begin{split}\left|{\psi }_{k}\left(\gamma,\beta \right)\right. = \;& \;U\left({H}_{\mathrm{B}},{\beta }_{k}\right)U\left({H}_{\mathrm{C}},{\gamma }_{k}\right)\cdots \\& \left. U\left({H}_{\mathrm{B}},{\beta }_{1}\right)U\left({H}_{\mathrm{C}},{\gamma }_{1}\right)\right| + \rangle ^{ \otimes N}\text{,} \end{split}$
其中$ \gamma =\left({\gamma }_{1}, \cdots, {\gamma }_{k}\right) $, $ \beta =\left({\beta }_{1}, \cdots, {\beta }_{k}\right) $. 通过计算基对量子态$\left|{\psi }_{k}\left(\gamma, \beta \right) \right\rangle$进行测量, 得到$ {H}_{\mathrm{C}} $在$\left|{\psi }_{k}\left(\gamma, \beta \right) \right\rangle$上的期望值:
${F_k}\left( {\gamma ,\beta } \right) = \left\langle {{\psi _k}\left( {\gamma ,\beta } \right)|{H_{\rm{C}}}|{\psi _k}\left( {\gamma ,\beta } \right)} \right\rangle {\rm{.}} $
通过(14)式可以得出, 当$ {H}_{\mathrm{C}} $对应的能量本征值越低的那个本征态出现的概率越高时, 则期望值就越小, 从而$ \mathrm{\mu }\left({C}_{1}, \cdots, {C}_{\left|P\right|}\right) $越接近0. 所以, 我们通过经典优化算法对参数$ \gamma $和$ \beta $进行优化, 使得$ {H}_{\mathrm{C}} $的期望值最小化.
$\left( {{\gamma ^*},{\beta ^*}} \right) = {\rm{arg}}\;{\rm{mi}}{{\rm{n}}_{\gamma ,\beta }}{F_k}\left( {\gamma ,\beta } \right){\rm{,}} $
(15)式中$ \left({\gamma }^{*}, {\beta }^{*}\right) $为参数$ \gamma $和$ \beta $经过优化后所取得数值.
基于QAOA的任务规划问题求解过程如图1所示, 主要由量子处理器和经典处理器两部分组成. 经典处理器部分为辅助模块, 主要采用经典优化方法对参数$ \gamma $和$ \beta $进行优化, 辅助量子处理器部分完成对酉变化中参数$ \gamma $和$ \beta $取值的调整; 量子处理器部分为主体模块, 主要采用QAOA算法进行量子态演化和问题求解.
图 1 QAOA实现框架示意图
Figure1. Schematic diagram of the QAOA implementation.

2
3.3.基于QAOA的量子线路设计方案
-->

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

与经典计算相对应, 量子计算机通过量子线路来执行程序. 为了使QAOA在量子软件开发环境中运行, 需要设计相应的量子线路.
本文设计的QAOA量子线路主要包含三个环节, 如图2所示. 首先是制备量子初态${| + \rangle}^{ \otimes N}$, 主要通过给每个量子比特作用一个$ H $门来实现. 然后实现以$ {H}_{\mathrm{C}} $和$ {H}_{\mathrm{B}} $两个哈密顿量为生成元, 得到两个酉变换乘积的累积$ U\left(\gamma, \beta \right) $,
图 2 基于QAOA的4个量子比特量子线路图
Figure2. Four-qubit quantum circuit based on QAOA.

$ U\left(\gamma,\beta \right)= \prod \nolimits _{i=1}^{k}U\left({H}_{\mathrm{B}},{\beta }_{i}\right)U\left({H}_{\mathrm{C}},{\gamma }_{i}\right)\text{.} $
(16)式中$ k $代表演化的步数, 两个酉变换之间的乘积代表每一步对应的量子线路; $ {\beta }_{i} $和$ {\gamma }_{i} $为每一步对应的参数. 一般演化的步数越大, 量子线路得到的效果就越好. 最后采用计算基进行测量. 其中第一部分和第三部分都比较容易实现, 下面重点推导第二部分的量子线路.
对于以$ {H}_{\mathrm{B}} $为生成元、参数为$ {\beta }_{i} $的酉变换, 将哈密顿量$ {H}_{\mathrm{B}} $的值代入, 可以推导出一组$ \mathrm{R}\mathrm{X} $门操作. 推导如下:
$ {H}_{\mathrm{B}}=\displaystyle\sum \nolimits _{n=1}^{N}{\mathrm{\sigma }}_{n}^{X}\text{,} $
$ \begin{split} \;& U\left({H}_{\mathrm{B}},{\beta }_{i}\right)={\mathrm{e}}^{-\mathrm{i}{\beta }_{i}{H}_{B}}={\mathrm{e}}^{-\mathrm{i}\sum \limits _{n=1}^{N}{\mathrm{\sigma }}_{n}^{X}{\beta }_{i}}\\=\;& \prod \limits _{n=1}^{N}{\mathrm{e}}^{-\mathrm{i}{{\mathrm{\sigma }}_{n}^{X}\beta }_{i}}= \prod \limits _{n=1}^{N}RX\left(n,2{\beta }_{i}\right)\text{.} \end{split} $
对于以$ {H}_{\mathrm{C}} $为生成元, 参数为$ {\gamma }_{i} $的酉变换, 将哈密顿量$ {H}_{\mathrm{C}} $的值代入, 可以推导出$ \mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T} $门和$ \mathrm{R}\mathrm{Z} $门的组合操作以及一组$ \mathrm{R}\mathrm{Z} $门单独操作. 推导如下:
$ {H}_{\mathrm{C}}=\sum \limits _{n < j}{G}_{nj}{\mathrm{\sigma }}_{n}^{Z}{\mathrm{\sigma }}_{j}^{Z}+\sum \limits _{n=1}^{N}{q}_{n}{\mathrm{\sigma }}_{n}^{Z}\text{,} $
$\begin{split} \;& U\left({H}_{\mathrm{C}},{\gamma }_{i}\right)={\mathrm{e}}^{-\mathrm{i}{\gamma }_{i{H}_{\mathrm{C}}}}\\=\;&{\mathrm{e}}^{-\mathrm{i}{\gamma }_{i}\left(\sum \limits _{n < j}{G}_{nj}{\mathrm{\sigma }}_{n}^{Z}{\mathrm{\sigma }}_{j}^{Z}+\sum \limits _{n=1}^{N}{q}_{n}{\mathrm{\sigma }}_{n}^{Z}\right)}\\=\;&{\mathrm{e}}^{-\mathrm{i}{\gamma }_{i}\left(\sum \limits _{n < j}{G}_{nj}{\mathrm{\sigma }}_{n}^{Z}{\mathrm{\sigma }}_{j}^{Z}\right)}\times {{\rm{e}}}^{-{\rm{i}}{\gamma }_{i}\left(\sum \limits _{n=1}^{N}{q}_{n}{\mathrm{\sigma }}_{n}^{Z}\right)}\\=\;& \prod \limits _{n < j}{\mathrm{e}}^{-\mathrm{i}{\gamma }_{i}{G}_{nj}{\mathrm{\sigma }}_{n}^{Z}{\mathrm{\sigma }}_{j}^{Z}}\times \prod \limits _{n=1}^{N}{\mathrm{e}}^{-\mathrm{i}{\gamma }_{i}{q}_{n}{\mathrm{\sigma }}_{n}^{Z}}\\=\;& \prod \limits _{n < j}\left[\right.\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}\left(n,j\right)\mathrm{R}\mathrm{Z}\left(j,2{\gamma }_{i}{G}_{nj}\right)\\\;&\times\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}\left(n,j\right)\left.\right]\times \prod \limits _{n=1}^{N}\left(\mathrm{R}\mathrm{Z}\left(n,2{\gamma }_{i}{q}_{n}\right)\right)\text{.} \end{split}$
如图2所示, 环节2为演化步数为1时对应的量子线路图. 如果演化步数为$ k $时, 对应的第二部分量子线路重复$ k $次.
4.仿真结果与分析
2
4.1.迭代次数的优化与分析
-->

4.1.迭代次数的优化与分析

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


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

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

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

2
4.2.仿真结果分析
-->

4.2.仿真结果分析

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

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

2
4.3.基于QAOA的求解方案复杂度分析
-->

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

采用了动量梯度下降法对量子线路中的参数进行优化, 属于启发式策略优化方法. 结合文献[32]的研究内容和本文仿真实验设计, 提出的基于QAOA的量子线路求解方案的时间复杂度为$ O\left[\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\left(k\right)\right] $, 其中$ k $为上述中的演化步数. 而传统的求解算法时间复杂度为$ O\left(m\cdot {n}^{2}\right) $, 其中$ m $为平台数量, $ n $为任务数量. 所以, 随着平台和任务数量的增加, 基于QAOA的量子线路求解方案的时间复杂度要优于传统求解算法时间复杂度.
5.结　论
本文根据C2组织中的任务规划问题特点, 将其转化成组合优化中的精确覆盖问题. 通过理论推导提出了一种基于QAOA算法的量子线路求解方案, 并利用经典优化算法对量子逻辑门中的参数进行优化, 在本源量子开发的pyQPanda量子软件开发环境中进行仿真编译. 仿真结果表明, 本文提出的基于QAOA的量子线路设计及方法可以有效求解C2组织中的任务规划问题, 为提高任务规划问题的求解速度提供了理论支撑. 经过分析, 本文所采用的QAOA算法是一种普适的方法. 实际中能转化为组合优化中的精确覆盖问题的实际问题都可以尝试采用本文的求解方案进行求解. 下一步将通过采用一些群智能算法[33]进一步优化适用于求解任务规划问题的QAOA算法设计与实现, 在降低经典计算部分复杂度的同时提高参数的优化效果; 另一方面对量子线路中的量子逻辑门进行优化, 在降低演化步数的同时提高计算的正确率.
感谢国防科技大学信息通信学院刘雍讲师、王勋讲师的讨论和帮助.
相关话题/优化 规划 组织 计算 方案
  • 领限时大额优惠券,享本站正版考研考试资料!
    大额优惠券
    优惠券领取后72小时内有效，10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材，产品类型包含电子书、题库、全套资料以及视频，无论您是考研复习、考证刷题，还是考前冲刺等，不同类型的产品可满足您学习上的不同需求。 ...
    考试优惠券 本站小编 Free壹佰分学习网 2022-09-19
  • 电子束对ZnO和TiO<sub>2</sub>辐照损伤的模拟计算
    摘要:电子辐照在材料中产生的缺陷主要是相互独立的空位-间隙原子对,由于不同靶原子的离位阈能不同,通过改变电子束的能量可以调控在材料中产生的缺陷类型,同时,电子的注量又可以决定电子辐照产生的缺陷的浓度.ZnO和TiO2的磁光电特性受Zn空位、Ti空位、O空位、Zn间隙原子、Ti间隙原子等缺陷的影响,因 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • 基于机器学习和器件模拟对Cu(In,Ga)Se<sub>2</sub>电池中Ga含量梯度的优化分析
    摘要:Cu(In,Ga)Se2(CIGS)太阳能电池是一种高效薄膜太阳能电池,Ga含量(Ga/(Ga+In),GGI)梯度调控是在不损失短路电流情况下,获得高开路电压的一种有效方法.本文基于对薄膜电池效率极限的对比分析,首先评估了CIGS电池性能提升的优化空间和策略.进而,通过机器学习与电池模拟分析 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • 基于电荷和热输运的石墨烯热电子器件性能优化
    摘要:科研人员近年来提出了石墨烯热电子能量转换器件(graphenethermionicenergyconverter,GTEC)的模型,对其物理机理与参数优化展开了研究,为高品位热能开发提供了新途径.然而,空间电荷积累和近场热辐射效应对GTEC能量转换性能的影响却鲜有报道.本文结合热电子发射、朗缪 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • 基于测量的量子计算研究进展
    摘要:相比于量子门电路模型,基于测量的量子计算模型为实现普适量子计算提供了另一途径,且经过近二十年的发展其内涵已得到了极大丰富.本文对基于测量的量子计算模型的研究历史和现状进行综述.首先简要介绍该模型的基本理论,包括量子图态等资源态的概念和工作原理、模型的计算普适性和经典模拟方法、在相关量子信息处理 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • 硅和锗量子计算材料研究进展
    摘要:半导体量子点量子计算是实现固态量子计算的重要途径之一,高质量量子计算材料制备是其中的关键.硅和锗材料能够实现无核自旋的同位素纯化,满足量子比特对长退相干时间的要求,同时与当前的硅工艺兼容,是实现半导体量子计算的重要材料平台.本文首先概述了近年来半导体量子点量子计算领域取得的重要进展,然后详细介 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • 基于MXene涂层保护Cs<sub>3</sub>Sb异质结光阴极材料的计算筛选
    摘要:以锑化铯(Cs3Sb)为代表的碱金属型半导体光阴极具有高量子效率、低电子发射度、光谱响应快等特点,可作为理想的新型电子发射源.然而Cs3Sb中碱金属敏感于含氧气体,从而导致其结构不稳定,工作寿命低,影响电子发射效率.利用超薄层状的二维材料进行涂层保护Cs3Sb基底,有望构建新型高性能光阴极材料 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • 混合时钟驱动的自旋神经元器件激活特性和计算性能
    摘要:自旋神经元是一种新兴的人工神经形态器件,其具有超低功耗、强非线性、高集成度和存算一体等优点,是构建新一代神经网络的强有力候选者.本文提出了一种磁场辅助磁弹应变驱动的混合时钟自旋神经元,利用OOMMF微磁学仿真软件建立了该神经元器件的微磁学模型,基于LLG方程建立了其数值仿真模型,利用所设计的自 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • 磁制冷材料LaFe<sub>11.5</sub>Si<sub>1.5</sub>基合金成分与磁相变温度关系的高通量计算
    摘要:获得具有不同磁相变温度的La(Fe,Si)13基合金对拓宽磁制冷工作温区具有重要意义.借助第一性原理模拟软件AMS-BAND模块并结合平均场理论对LaFe11.5Si1.5基磁制冷合金的磁相变温度进行了高通量计算.研究了Mn,Co,Ni,Al和Fe缺位掺杂对LaFe11.5Si1.5基合金体系 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • X射线荧光CT成像中荧光产额、退激时间、散射、偏振等关键物理问题计算与分析
    摘要:X射线荧光CT(X-rayfluorescencecomputedtomography,XFCT)是一种使用X射线荧光(X-rayfluorescence,XRF)实现功能性成像的新技术,在生物医学成像中表现出较大潜力.但是,X射线穿过生物体的同时还会产生大量康普顿散射光子,对XRF信号的采集 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29
  • 石墨烯晶体管优化制备工艺在单片集成驱动氮化镓微型发光二极管中的应用
    摘要:在显示领域,微型发光二极管(micro-LED)潜力巨大,有望引领下一代新型显示技术的发展方向,其显示性能在很多方面优于现有的液晶、有机发光二极管(OLED),但巨量的micro-LED像素点与驱动电路不在同一晶圆上制备,面临巨量转移的技术瓶颈.本文将新兴的石墨烯场效应晶体管作为驱动元件与氮化 ...
    中科院物理研究所 本站小编 Free考研考试 2021-12-29

Free考研考试FreeKaoYan.Com
欢迎来到Free考研考试，"为实现人生的Free而奋斗"

© 2020 FreeKaoYan! . All rights reserved.