基于Grover算法的图着色问题求解  

Solving Graph Coloring Problem Based on Grover Algorithm

作　　者：刘晓楠[1] 刘正煜 谢浩山 赵晨言 LIU Xiaonan;LIU Zhengyu;XIE Haoshan;ZHAO Chenyan(State Key Laboratory of Mathematical Engineering and Advanced Computing,PLA Information Engineering University,Zhengzhou 450000,China;School of Computer and Artificial Intelligence,Zhengzhou University,Zhengzhou 450000,China)

机构地区：[1]数学工程与先进计算国家重点实验室(信息工程大学),郑州450000 [2]郑州大学计算机与人工智能学院,郑州450000

出　　处：《计算机科学》2023年第6期351-357,共7页Computer Science

基　　金：国家自然科学基金(61972413,61701539)。

摘　　要：Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法,可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一,文中首先将图着色问题转化为数学上的无向图;然后采用布尔表达式将其转换为布尔可满足性问题,介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程;最后在IBMQ云平台上,对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性,在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中,分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题,拓展了该算法在此问题领域上的实验规模,且改进了现有实验的量子线路,使量子位成本更低,结果的成功率更高,展示了Grover算法在大型搜索问题中显著的加速效果。Grover quantum search algorithm is a famous quantum algorithm designed for unstructured search problems.It can be used to solve problems such as graph coloring and shortest path sorting,and can also effectively decipher cryptosystems.Graph coloring problem is one of the most famous NP complete problems.In this paper,the graph coloring problem is transformed into an undirected graph in mathematics,and then it is transformed into a Boolean satisfiability problem by using Boolean expression.The steps and principles of solving Boolean expression in quantum circuit diagram and the transformation process from graph co-loring problem to Boolean satisfiability problem are introduced.Finally,on the IBMQ cloud platform,for the three nodes,2-coloring problem and 4-coloring problem are simulated.Experimental results verify the feasibility of using Grover algorithm to solve the graph coloring problem.In the 2-coloring problem with search space of 8 and the 4-coloring problem with search space of 64,the target items are searched with nearly 82%and 97%success probability respectively.In this paper,Grover algorithm is used to solve the 4-coloring problem,expand the experimental scale of the algorithm in this problem field,and improve the quantum circuit of the existing experiments,so that the qubit cost is lower and the result success rate is higher,which shows the remarkable acceleration effect of Grover algorithm in large-scale search problems.

关 键 词：GROVER算法 图着色问题 量子线路 IBMQ 布尔可满足性问题 

分 类 号：TP385[自动化与计算机技术—计算机系统结构]