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

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

doi:10.7498/aps.70.20211028

摘要

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

关键词:

Abstract

The mission planning problem in command and control organization can be mapped into a combinatorial optimization problem with many variables and is difficult to solve. The traditional heuristic list planning method faces the problems of high time complexity and poor real-time response. For the mission planning problem in command and control organization, a quantum circuit solution scheme is proposed based on quantum approximate optimization algorithm in this work. Firstly, the mission planning problem is transformed into a typical combinatorial optimization problem, the exact coverage problem. Then, by constructing the corresponding mathematical model, the final state Hamiltonian expression of the quantum approximate optimization algorithm for the exact coverage problem is derived. The quantum circuit based on the quantum approximate optimization algorithm is designed. Finally the parameters in the quantum logic gate are optimized by the momentum gradient descent algorithm, and the simulation experiment is carried out by using the quantum software development environment of the Origin Quantum Computing Company. The simulation results show that the quantum circuit scheme can be used to solve the mission planning problem, reduce the time complexity of the algorithm, and improve the resource utilization to a certain extent. This work lays the foundation for further application of quantum algorithm to solving the mission planning problem in command and control organization.

Keywords:

quantum approximate optimization algorithm /
quantum circuit /
mission planning

作者及机构信息

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

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

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

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

通信作者: 东晨, dongchengfkd@163.com

Authors and contacts

1.
Graduate Institute, Rocket Force University of Engineering, Xi’an 710025, China

2.
Rocket Force University of Engineering, Xi’an 710025, China

3.
Institute of Information and Communication, National University of Defense Technology, Xi’an 710106, China

4.
Institute of Information and Navigation, Air Force Engineering University, Xi’an 710077, China

Corresponding author: Dong Chen, dongchengfkd@163.com

文章全文 : translate this paragraph

参考文献

[1]	张杰勇, 姚佩阳, 周翔翔, 孙鹏 2012 火力与指挥控制 37 2293 Zhang J Y, Yao P Y, Zhou X X, Sun P 2012 Fire Control and Command Control 37 2293
[2]	张杰勇, 姚佩阳, 周翔翔, 王欣 2012 系统工程与电子技术 34 947 Google Scholar Zhang J Y, Yao P Y, Zhou X X, Wang X 2012 Syst. Eng. Electron. 34 947 Google Scholar
[3]	Sih G C, Lee E A 1993 IEEE Trans. Parallel Distrib. Syst. 4 175 Google Scholar
[4]	Levchuk G M, Levchuk Y N, Luo J 2002 IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 32 346 Google Scholar
[5]	阳东升, 张维明, 刘忠, 等 2006 系统工程理论与实践 01 26 Google Scholar Yang D S, Zhang W M, Liu Z, et al. 2006 Syst. Eng. Theor. Pract. 01 26 Google Scholar
[6]	鲁音隆, 阳东升, 刘忠, 等 2006 火力与指挥控制 31 12 Google Scholar Lu Y L, Yang D S, Liu Z, et al. 2006 Fire Control and Command Control 31 12 Google Scholar
[7]	Arute F, Arya K, Babbush R, et al. 2019 Nature 574 505 Google Scholar
[8]	Farhi E, Harrow A W 2019 arXiv: 1602.07674 v2 [quant-ph]
[9]	Lin C Y Y, Zhu Y 2016 arXiv: 1601.01744 v1 [quant-ph]
[10]	Wecker D, Hastings M B, Troyer M 2016 Phys. Rev. A 94 022309 Google Scholar
[11]	Lechner W 2020 IEEE Trans. Quantum Eng. 1 3102206
[12]	Yang Z C, Rahmani A, Shabani A, Neven H, Chamon C 2017 Phys. Rev. X 7 021027
[13]	Zahedinejad E, Zaribafiyan A 2017 arXiv: 1708.05294 v1 [quant-ph]
[14]	Farhi E, Goldstone J, Gutmann S 2014 arXiv: 1411.4028 v1 [quant-ph]
[15]	Albash T, Lidar D A 2018 Rev. Mod. Phys. 90 015002 Google Scholar
[16]	Crooks G E 2018 arXiv: 1811.08419 v1[quant-ph]
[17]	Guerreschi G G, Matsuura A Y 2019 Sci. Rep.s 9 6903 Google Scholar
[18]	Wang Z, Hadfield S, Jiang Z, Rieffel E G 2018 Phys. Rev. A 97 022304 Google Scholar
[19]	Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D 2001 Science 292 472 Google Scholar
[20]	Young A P, Knysh S, Smelyanskiy V N 2010 Phys. Rev. Lett. 104 020502 Google Scholar
[21]	Altshuler B, Krovi H, Rol J 2010 Proc. Natl.Acad. Sci. U. S. A. 107 12446 Google Scholar
[22]	Choi V 2010 Comput. Sci. 108 7
[23]	Wang H, Wu L A 2016 Sci. Rep. 6 22307 Google Scholar
[24]	Graß T 2019 Phys. Rev. Lett. 123 120501 Google Scholar
[25]	Lucas A 2014 Front.Phys. 2 5
[26]	Fu Y, Anderson P W 1986 J. Phys. A 19 1605 Google Scholar
[27]	Mézard M, Montanari A 2009 Information, Physics and Computation P35
[28]	Vikstål P, Grönkvist M, Svensson M, et al. 2020 Phys. Rev. Appl. 14 034009 Google Scholar
[29]	Broyden C G 1970 IMA J. Appl. Math. 6 76 Google Scholar
[30]	Nelder J A, Mead R 1965 Comput. J. 7 308 Google Scholar
[31]	Frazier P I 2018 arXiv: 1807.02811 v1 [stat.ML]
[32]	Zhou L, Wang S T, Choi S, et al. 2020 Phys. Rev. X 10 021067
[33]	王培良, 张婷, 肖英杰 2020 物理学报 69 080504 Google Scholar Wang P L, Zhang T, Xiao Y J 2020 Acta Phys. Sin. 69 080504 Google Scholar

施引文献

图 1 QAOA实现框架示意图

Fig. 1. Schematic diagram of the QAOA implementation.

下载: 全尺寸图片幻灯片

图 2 基于QAOA的4个量子比特量子线路图

Fig. 2. Four-qubit quantum circuit based on QAOA.

下载: 全尺寸图片幻灯片

图 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.

下载: 全尺寸图片幻灯片

图 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.

下载: 全尺寸图片幻灯片

表 1 平台对应可执行任务分配方案

Table 1. Platforms corresponding executable mission allocation.

平台 1 2 3 4 5 6

平台可执
行的任务 1,2,3 1,2,3,4 3,4,5,6 5,6,7,8 7,8,9,10 9,10,11,12

下载: 导出CSV

[1]	张杰勇, 姚佩阳, 周翔翔, 孙鹏 2012 火力与指挥控制 37 2293 Zhang J Y, Yao P Y, Zhou X X, Sun P 2012 Fire Control and Command Control 37 2293
[2]	张杰勇, 姚佩阳, 周翔翔, 王欣 2012 系统工程与电子技术 34 947 Google Scholar Zhang J Y, Yao P Y, Zhou X X, Wang X 2012 Syst. Eng. Electron. 34 947 Google Scholar
[3]	Sih G C, Lee E A 1993 IEEE Trans. Parallel Distrib. Syst. 4 175 Google Scholar
[4]	Levchuk G M, Levchuk Y N, Luo J 2002 IEEE Trans. Syst. Man Cybern. Part A Syst. Humans 32 346 Google Scholar
[5]	阳东升, 张维明, 刘忠, 等 2006 系统工程理论与实践 01 26 Google Scholar Yang D S, Zhang W M, Liu Z, et al. 2006 Syst. Eng. Theor. Pract. 01 26 Google Scholar
[6]	鲁音隆, 阳东升, 刘忠, 等 2006 火力与指挥控制 31 12 Google Scholar Lu Y L, Yang D S, Liu Z, et al. 2006 Fire Control and Command Control 31 12 Google Scholar
[7]	Arute F, Arya K, Babbush R, et al. 2019 Nature 574 505 Google Scholar
[8]	Farhi E, Harrow A W 2019 arXiv: 1602.07674 v2 [quant-ph]
[9]	Lin C Y Y, Zhu Y 2016 arXiv: 1601.01744 v1 [quant-ph]
[10]	Wecker D, Hastings M B, Troyer M 2016 Phys. Rev. A 94 022309 Google Scholar
[11]	Lechner W 2020 IEEE Trans. Quantum Eng. 1 3102206
[12]	Yang Z C, Rahmani A, Shabani A, Neven H, Chamon C 2017 Phys. Rev. X 7 021027
[13]	Zahedinejad E, Zaribafiyan A 2017 arXiv: 1708.05294 v1 [quant-ph]
[14]	Farhi E, Goldstone J, Gutmann S 2014 arXiv: 1411.4028 v1 [quant-ph]
[15]	Albash T, Lidar D A 2018 Rev. Mod. Phys. 90 015002 Google Scholar
[16]	Crooks G E 2018 arXiv: 1811.08419 v1[quant-ph]
[17]	Guerreschi G G, Matsuura A Y 2019 Sci. Rep.s 9 6903 Google Scholar
[18]	Wang Z, Hadfield S, Jiang Z, Rieffel E G 2018 Phys. Rev. A 97 022304 Google Scholar
[19]	Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D 2001 Science 292 472 Google Scholar
[20]	Young A P, Knysh S, Smelyanskiy V N 2010 Phys. Rev. Lett. 104 020502 Google Scholar
[21]	Altshuler B, Krovi H, Rol J 2010 Proc. Natl.Acad. Sci. U. S. A. 107 12446 Google Scholar
[22]	Choi V 2010 Comput. Sci. 108 7
[23]	Wang H, Wu L A 2016 Sci. Rep. 6 22307 Google Scholar
[24]	Graß T 2019 Phys. Rev. Lett. 123 120501 Google Scholar
[25]	Lucas A 2014 Front.Phys. 2 5
[26]	Fu Y, Anderson P W 1986 J. Phys. A 19 1605 Google Scholar
[27]	Mézard M, Montanari A 2009 Information, Physics and Computation P35
[28]	Vikstål P, Grönkvist M, Svensson M, et al. 2020 Phys. Rev. Appl. 14 034009 Google Scholar
[29]	Broyden C G 1970 IMA J. Appl. Math. 6 76 Google Scholar
[30]	Nelder J A, Mead R 1965 Comput. J. 7 308 Google Scholar
[31]	Frazier P I 2018 arXiv: 1807.02811 v1 [stat.ML]
[32]	Zhou L, Wang S T, Choi S, et al. 2020 Phys. Rev. X 10 021067
[33]	王培良, 张婷, 肖英杰 2020 物理学报 69 080504 Google Scholar Wang P L, Zhang T, Xiao Y J 2020 Acta Phys. Sin. 69 080504 Google Scholar

[1]	黄天龙, 吴永政, 倪明, 汪士, 叶永金. 量子噪声对Shor算法的影响. 物理学报, 2024, 73(5): 050301. doi: 10.7498/aps.73.20231414
[2]	李家祥, 王慧琴, 徐和庆, 张华, 冯艳, 董美彤. 基于序列二次规划算法的超小尺寸微纳波长分束器的逆向设计. 物理学报, 2023, 72(19): 194101. doi: 10.7498/aps.72.20230892
[3]	张毅军, 慕晓冬, 郭乐勐, 张朋, 赵导, 白文华. 一种基于量子线路的支持向量机训练方案. 物理学报, 2023, 72(7): 070302. doi: 10.7498/aps.72.20222003
[4]	陈以鹏, 刘靖阳, 朱佳莉, 方伟, 王琴. 机器学习在量子通信资源优化配置中的应用. 物理学报, 2022, 71(22): 220301. doi: 10.7498/aps.71.20220871
[5]	陈然一鎏, 赵犇池, 宋旨欣, 赵炫强, 王琨, 王鑫. 混合量子-经典算法: 基础、设计与应用. 物理学报, 2021, 70(21): 210302. doi: 10.7498/aps.70.20210985
[6]	张仁强, 蒋翔宇, 俞炯弛, 曾充, 宫明, 徐顺. 格点量子色动力学蒸馏算法中关联函数的计算优化. 物理学报, 2021, 70(16): 161201. doi: 10.7498/aps.70.20210030
[7]	王芙蓉, 杨帆, 张亚, 李世中, 王鹤峰. 基于奇异值分解的矩阵低秩近似量子算法. 物理学报, 2021, 70(15): 150201. doi: 10.7498/aps.70.20210411
[8]	王培良, 张婷, 肖英杰. 蚁群元胞优化算法在人群疏散路径规划中的应用. 物理学报, 2020, 69(8): 080504. doi: 10.7498/aps.69.20191774
[9]	杨乐, 李凯, 戴宏毅, 张明. 基于量子算法的量子态层析新方案. 物理学报, 2019, 68(14): 140301. doi: 10.7498/aps.68.20190157
[10]	舒安庆, 吴锋. 量子热声微循环的优化性能. 物理学报, 2016, 65(16): 164303. doi: 10.7498/aps.65.164303
[11]	聂敏, 刘广腾, 杨光, 裴昌幸. 基于最少中继节点约束的量子VoIP路由优化策略. 物理学报, 2016, 65(12): 120302. doi: 10.7498/aps.65.120302
[12]	凌宏胜, 田佳欣, 周淑娜, 魏达秀. Ising耦合体系中量子傅里叶变换的优化. 物理学报, 2015, 64(17): 170301. doi: 10.7498/aps.64.170301
[13]	文方青, 张弓, 贲德. 基于块稀疏贝叶斯学习的多任务压缩感知重构算法. 物理学报, 2015, 64(7): 070201. doi: 10.7498/aps.64.070201
[14]	黄宇, 刘玉峰, 彭志敏, 丁艳军. 基于量子并行粒子群优化算法的分数阶混沌系统参数估计. 物理学报, 2015, 64(3): 030505. doi: 10.7498/aps.64.030505
[15]	高洪元, 李晨琬. 膜量子蜂群优化的多目标频谱分配. 物理学报, 2014, 63(12): 128802. doi: 10.7498/aps.63.128802
[16]	梁彦霞, 聂敏, 刘欣, 张美玲, 姜静. 量子语音多带激励算法. 物理学报, 2014, 63(12): 120301. doi: 10.7498/aps.63.120301
[17]	郭业才, 胡苓苓, 丁锐. 基于量子粒子群优化的正交小波加权多模盲均衡算法. 物理学报, 2012, 61(5): 054304. doi: 10.7498/aps.61.054304
[18]	李盼池, 王海英, 宋考平, 杨二龙. 量子势阱粒子群优化算法的改进研究. 物理学报, 2012, 61(6): 060302. doi: 10.7498/aps.61.060302
[19]	刘凯, 李文东, 张闻钊, 史鹏, 任春年, 顾永建. 高维辅助的普适量子线路优化. 物理学报, 2012, 61(12): 120301. doi: 10.7498/aps.61.120301
[20]	方伟, 孙俊, 谢振平, 须文波. 量子粒子群优化算法的收敛性分析及控制参数研究. 物理学报, 2010, 59(6): 3686-3694. doi: 10.7498/aps.59.3686

计量

文章访问数: 5232
PDF下载量: 119
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板

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