量子近似优化算法在最大独立集中的应用

段孟环 李志强 郭玲玲

摘 要：最大独立集问题是著名的NP问题，并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题，提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型，推导出最大独立集问题的哈密顿量表达式；设计了基于量子近似优化算法的量子线路，采用COBYLA经典优化算法对参数量子门中的参数进行优化，并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明，使用量子近似优化算法可以在多项式时间以高概率内获得最大独立集问题的解，实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。

关键词：最大独立集； 量子近似优化算法； 量子线路； Qiskit

中图分类号：O4   文献标志码：A

文章编号：1001-3695（2023）09-013-0000-00

doi：10.19734/j.issn.1001-3695.2023.02.0031

Application of quantum approximate optimization algorithm in

max independent set problem

Duan Menghuan， Li Zhiqiang， Guo Lingling

（College of Information Engineering， Yangzhou University， Yangzhou Jiangsu 225100， China）

Abstract：The max independent set problem is a well-known NP problem and has applications in many scenarios. Traditional exact algorithms need exponential time complexity to solve the max independent set problem. In order to solve the max independent set problem more efficiently， this paper proposed a quantum circuit solution based on the quantum approximate optimization algorithm. In this scheme， derived the Hamiltonian expression of the max independent set problem from the mathematical model of the max independent set， designed the quantum circuit based on the quantum approximation optimization algorithm. It used the COBYLA classical optimization algorithm to optimize the parameters in the parameter quantum gate， and used the quantum development framework Qiskit provided by IBM to conduct simulation experiments. Simulation results show that the solution of the max independent set problem can be obtained in polynomial time with high probability using the quantum approximate optimization algorithm， achieving an exponential speedup. Quantum approximate optimization algorithm is feasible and effective for solving the max independent set problem.

Key words：max independent set problem; quantum approximate optimization algorithm; quantum circuit; Qiskit

0 引言

1972年，Karp提出了21個NP完全问题［1］，最大独立集问题（max independent set problem，MISP）就是其中之一。最大独立集问题是一个经典的组合优化问题［1，2］，数十年来受到了大量学者的关注，并且将其应用于各个场景中［3，4］。文献[5，6]提出了一系列基于分支定界策略（branch and bound strategy）的精确算法来解决最大独立集问题，这些精确算法解决最大独立集问题需要指数级的时间。

随着量子计算［7～9］的发展，量子计算有望成为一种具有颠覆性影响的计算方式。量子计算基于量子态的连贯性和纠缠性，可以轻松完成并行计算。某些在经典处理器上难以解决的问题，在量子处理器上可以实现指数加速或二次加速［10，11］。2014年，Farhi等人［12］提出了量子近似优化算法（quantum approximate optimization algorithm，QAOA）并将其应用于解决最大割问题。量子近似优化算法是一种启发式的量子经典混合算法，主要用于解决组合优化问题。相比于经典算法，量子近似优化算法对解决组合优化问题有指数加速。根据相关文献［13，14］，量子近似优化算法是在近期的量子计算机上实现的最有前途的显示量子优势的算法之一。近年来，量子近似优化算法被用于精确覆盖［15］、汉密尔顿路［16］、背包问题等问题［17］。

在本文中，提出了一种基于量子近似优化算法的量子线路解决方案用于解决最大独立集问题。首先，根据最大独立集问题的数学模型构建相应的二次无约束二元优化（quadratic unconstrained binary optimization，QUBO）模型。其次，根据量子系统理论，由QUBO模型推导出量子Ising模型和问题哈密顿量。第三，基于QAOA原理，得到基于初始哈密顿量和问题哈密顿量的参数酉变换。参数主要与量子门的旋转角度有关。交替使用酉变换可以得到最终的量子态。最后，根据初始量子态和参数酉变换设计量子门，生成可以在量子计算机上执行的量子线路。在演化过程中，采用经典优化算法对量子线路的参数进行优化，通过调整问题的哈密顿量的期望，从而提高解的概率。该方案可以有效地解决最大独立集问题。

1 问题模型

在无向图G=（V，E）中，其中V表示无向图G的顶点集，E表示无向图G的边集。

图G=（V，E）中两两互不相邻的顶点构成的集合称为独立集。最大独立集是具有最大尺寸的独立集。

假设S是无向图G=（V，E）的独立集。|S|表示独立集中顶点的个数。最大独立集问题的目标函数可以由F1表示，其中xi对应于第i个顶点的取值，当vi∈S时，xi=1；viS时，xi=0。

3 仿真与结果分析

使用QAOA解决最大独立集问题时，首先需要将图的顶点映射至量子比特。然后根据图中的边和第2章中所示方案生成QAOA量子线路，对量子比特进行测量并计算哈密頓量的期望值，在经典部分使用经典参数优化器对量子线路中的参数进行优化。重复上述步骤，直到收敛。最终得到的量子比特的测量值组成的字符串就是最大独立集所对应的解。本文对图3中的示例进行实验仿真。因为该示例有6个顶点，在初始化时需要准备6个量子比特，每个量子比特对应于一个顶点。然后根据第三部分的内容构造量子线路。最后对最终状态进行测量可以得到由“0”和“1”组成的6位字符串，其中“0”表示该顶点未被选中，“1”表示该顶点被选中。算法1给出了该方案的主要伪代码。

算法1 基于QAOA的最大独立集算法

输入：无向图G=（V，E），演化步数p。

输出： 最优解S。

nqubits←|V|

qc←QuantumCircuit（nqubits） //初始化量子线路

γ，β←1.0  //初始化2p个参数

for i←0： nqubits do //制备初始叠加态

qc.h（i）

end for

while stop criterion is no satisfied do

for k←1：p do

qc.append（U（HC，γk）） //式（17）

qc.append（U（HM，βk）） //式（20）

end for

计算期望值Fp（γ，β） //式（11）

使用经典优化器优化参数γ和β

end while

测量量子态

S←具有最高概率的量子态对应的比特串

输出S

3.1 仿真结果与分析

本文主要使用IBM开发的量子软件开发工具Qiskit［22］在Python 3中模拟和实现所设计的量子线路。可以知道，图3中的示例，其最大独立集S={0，1，4，5}。相应地，在QAOA下，获得字符串“110011”的概率应该最大。本文选取了演化步数为1至11进行仿真实验。

在使用QAOA求解图2的最大独立集时，在不限制迭代次数的情况下，当演化步数为1～11时，得到正确解“110011”的概率如图5所示。

从图5可以看出，当p=1时，QAOA算法获得正确解的概率为21.4%，当p=2时，获得正确解的概率显著增加，并且随着演化步数的增加，获得的问题解的正确率总体呈现上升趋势。但并不是所有的演化结果都比之前的演化结果好，它是会有波动的。在达到一定数量的进化步骤后，其正确率可能会下降，但仍保持在较高水平，这与文献［12］的结论一致。从图4可以看出，当演化步数p为1到11时，在p=7时的结果最好，正确率达到94.5%。

图6显示了当p=7时，QAOA算法所得到的结果及其对应的概率。图7给出了在p=7的结果空间下，p分别为1，3，5，7，9时获得各个结果的概率。

从图7中可以看出，当演化步数p为3， 5， 7， 9时，正确解的概率非常显著。因此，结果表明，本文提出的基于QAOA的解决方案可以用于解决最大独立集问题。

3.2 迭代与优化结果与分析

在实验过程中，为了使QAOA得到较好的结果，需要在经典计算部分采用优化算法来优化参数（γ，β）以得到较优的（γ，β）。常用的优化方法有CG算法［23］、BFGS算法［24］、Nelder-Mead算法［25］和COBYLA算法［26］等。各经典优化算法在p=1时，获得正确解的概率如表1所示。可以看出，使用COBYLA经典优化算法能以更高的概率获得正确解。因此，本文使用COBYLA经典优化算法来优化参数（γ，β）。

图8显示了当演化步数为1到11时，经典优化算法COBYLA获得最佳参数所需的迭代次数。可以看出，随着演化步数的增加，所需迭代次数也会增加。因为所需要优化的参数的数量会随着演化步数的增加而增加，参数的优化更加复杂，获得最优参数的迭代次数也会增加。

图8显示了当演化步数为1到11时，经典优化算法COBYLA获得最佳参数所需的迭代次数。可以看出，随着演化步数的增加，所需迭代次数也会增加。因为所需要优化的参数的数量会随着演化步数的增加而增加，参数的优化更加复杂，获得最优参数的迭代次数也会增加。

图9显示了当演化步数为1，3，5，7，9时，随着迭代次数的增加，损失值的变化过程。从图9可以看出，在演化步数一定时，迭代次数越多，损失值的绝对值越大。但在达到某个值后，损失值变化很小或根本没有变化。这是因为当目标函数接近局部最优解或目标函数已达到最优且优化已完成时，目标函数的收敛速度减慢。当演化步数分别为5和9时，它们的损失值相差不大，图5的结果也表明它们之间的差异仅为1.9%。因此，当获得正确解的概率相差不大时，本文可以优先选择较少的演化步数，同时选择适当的迭代次数，以节省时间和空间开销。

3.3 QAOA复杂度分析

本文采用混合量子—经典算法QAOA求解最大独立集问题。它主要包括两部分：经典处理器部分和量子处理器部分。在经典处理器中，使用COBYLA算法来优化参数。COBYLA算法的时间复杂度是O（poly（m）），其中m是迭代次数，可以自己设置。poly（m）是m的多项式函数，这意味着COBYLA算法的计算复杂度是多项式级别的。在量子处理器中，主要完成量子态从量子初始态到量子最终态的演化，并测量量子最终态。结合相关文献［27］，量子态的演化是最耗时的，几乎相当于整个量子电路的时间复杂度。因此，量子部分的时间复杂度是O（poly（p）），为多项式级别，其中p演化步数。因此，本文提出的量子线路求解方案的时间复杂度为O［poly（m）+poly（p）］。而求解最大独立集问题的精确算法的时间复杂度是指数级的。由此，可以得出结论，基于QAOA的求解算法的时间复杂度优于传统的求解算法，尤其是當问题规模较大时。

4 结束语

本文针对最大独立集问题，提出了一种基于QAOA量子线路的解决方案。根据最大独立集问题的性质，建立了最大独立集的问题模型。推导出了最大独立集的问题哈密顿量，并且根据其哈密顿量，设计了一个基于QAOA的量子线路，使用经典优化算法来优化参数，并在IBM开发的Qiskit框架中进行了仿真。仿真结果表明，本文提出的基于QAOA算法的量子线路求解方案能够有效地获得最大独立集问题的解。与经典的精确算法相比，本文方案实现了指数加速，大大提高了效率。

本文提出的方案仍需改进，主要包括两个方面：

a）经典优化器的优化效果不太理想;b）可以进一步优化所设计的量子线路。

为了解决上述两个问题，今后主要关注以下工作：a）研究参数酉变换的参数特性，选择或设计一个更好的经典优化器，以提高优化效率和效果;b）设计一个QAOA线路的编译方案用于优化QAOA的线路，减少量子门的数量，提高QAOA线路的执行效率。

参考文献：

[1]Karp R M，Miller R E，Thatcher J W.Reducibility among combinatorial problems［J］.The Journal of Symbolic Logic，1975，40：618-619.

［2]Shen Yunzhuang，Sun Yuan，Li Xiaodong，et al.Multi-shot solution prediction for combinatorial optimization［EB/OL］.（2022）［2023-03-31］.https：//arxiv.org/abs/2204.08700.

［3]Li Lianjie，Huang Wenqian，Wang Zheli，et al.Calibration transfer between developed portable Vis/NIR devices for detection of soluble solids contents in apple［J］.Postharvest Biology and Technology，2022，183：111720.

［4]Davoudi M，Moosavi M R，Sadreddini M H.DSS：a hybrid deep model for fake news detection using propagation tree and stance network［J］.Expert Systems with Applications，2022，198：116635.

［5]Dai Jinyu，Wu Zhengtia，Karimi H R，et al.An approximation lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network［J］.Journal of the Franklin Institute，2022，359（12）：6080-6098.

［6]Forget N，Gadegaard S L，Klamroth K，et al.Branch-and-bound and objective branching with three or more objectives［J］.Computers & Operations Research，2022，148：106012.

［7]Zhong Hansen，Wang Hui，Deng Yuhao，et al.Quantum computational advantage using photons［J］.Science，2020，370（6523）：1460-1463.

［8]Arute F，Arya K，Babbush R，et al.Quantum supremacy using a programmable superconducting processor［J］.Nature，2019，574（7779）：505-510.

［9]李晓巍，付祥，燕飞，等.量子计算研究现状与未来发展［J］.中国工程科学，2022，24（4）：133-144.（Li Xiaowei，Fu Xiang，Yan Fei，et al.Current status and future development of quantum computation［J］.Strategic Study of CAE，2022，24（4）：133-144.）

［10]Ahnefeld F，Theurer T，Egloff D，et al.Coherence as a resource for Shors algorithm［J］.Physical Review Letters，2022，129（12）：120501.

［11]吴希，李志强，杨东晗.Grover量子搜索算法的线路优化［J］.计算机工程与科学，2023，45（3）：420-425.（Wu Xi，Li Zhiqiang，Yang Donghan.Circuit optimization of Grover quantum search algorithm［J］.Computer Engineering & Science，2023，45（3）：420-425.）

［12]Farhi E，Goldstone J，Gutmann S.A quantum approximate optimization algorithm［EB/OL］.（2014）［2022-05-31］.http：//arxiv.org/abs/1411.4028.

［13]Bechtold M，Barzen J，Leymann F，et al.Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices［EB/OL］.（2023）［2023-03-31］.https：//arxiv.org/abs/2302.01792.

［14]Preskill J.Quantum computing in the NISQ era and beyond［J］.Quantum，2018，2：79.

［15]Vikstl P，Grnkvist M，Svensson M，et al.Applying the quantum approximate optimization algorithm to the tail-assignment problem［J］.Physical Review Applied，2020，14（3）：034009.

［16]Gong Changqing，Wang Ting，He Wanying，et al.A quantum approximate optimization algorithm for solving Hamilton path problem［J］.The Journal of Supercomputing，2022，78（13）：15381-15403.

［17]Roch C，Impertro A，Phan T，et al.Cross entropy hyperparameter optimization for constrained problem Hamiltonians applied to QAOA［C］// Proc of International Conference on Rebooting Computing.Piscataway，NJ：IEEE Press，2020：50-57.

［18]Lucas A.Ising formulations of many NP problems［J］.Frontiers in Physics，2014，2：5.

［19]Schmitt M，Rams M M，Dziarmaga J，et al.Quantum phase transition dynamics in the two-dimensional transverse-field Ising model［J］.Science Advances，2022，8（37）：eabl6850.

［20]Choi J，Oh S，Park S，et al.Proper cost hamiltonian design for combinatorial optimization problems：a boolean function approach［C］//Proc of International Conference on Information Networking.Piscataway，NJ：IEEE Press，2021：469-472.

［21]Majumdar R，Bhoumik D，Madan D，et al.Depth optimized ansatz circuit in QAOA for max-cut［EB/OL］.（2021）［2022-06-30］.https：//arxiv.org/abs/2110.04637.

［22]https：//qiskit.org/［EB/OL］.

［23]Wasi H A，Shiker M A K.Proposed CG method to solve unconstrained optimization problems［J］.Journal of Physics：Conference Series，2021，1804（1）：012024.

［24]Liu Qiancheng，Beller S，Lei Wenjie，et al.Pre-conditioned BFGS-based uncertainty quantification in elastic full-waveform inversion［J］.Geophysical Journal International，2022，228（2）：796-815.

［25]Liu Yun，Chong Guoshuang，Heidari A A，et al.Horizontal and vertical crossover of Harris hawk optimizer with Nelder-Mead simplex for parameter estimation of photovoltaic models［J］.Energy Conversion and Management，2020，223：113211.

［26]Pellow-Jarman A，Sinayskiy I，Pillay A，et al.A comparison of various classical optimizers for a variational quantum linear solver［J］.Quantum Information Processing，2021，20（6）：202.

［27]Zhou L，Wang Shengtao，Choi S，et al.Quantum approximate optimization algorithm：Performance，mechanism，and implementation on near-term devices［J］.Physical Review X，2020，10（2）：021067.

收稿日期：2023-02-16；

修回日期：2023-04-03

基金項目：国家自然科学基金资助项目（61070240，62071240）；江苏省高校基金资助项目（10KJB520021）

作者简介：段孟环（2000-），女，湖南衡阳人，硕士研究生，主要研究方向为量子算法、量子电路；李志强（1974-），男（通信作者），江苏扬州人，教授，硕导，博士研究生，主要研究方向为量子计算、量子可逆电路（yzqqlzq@163.com）；郭玲玲（1999-），女，江苏盐城人，硕士研究生，主要研究方向为量子算法、量子电路.