-
题名基于Grover算法的图着色问题求解
被引量：1
- 1
-
-
作者
刘晓楠
刘正煜
谢浩山
赵晨言
-
机构
数学工程与先进计算国家重点实验室(信息工程大学)
郑州大学计算机与人工智能学院
-
出处
《计算机科学》
CSCD
北大核心
2023年第6期351-357,共7页
-
基金
国家自然科学基金(61972413,61701539)。
-
文摘
Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法,可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一,文中首先将图着色问题转化为数学上的无向图;然后采用布尔表达式将其转换为布尔可满足性问题,介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程;最后在IBMQ云平台上,对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性,在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中,分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题,拓展了该算法在此问题领域上的实验规模,且改进了现有实验的量子线路,使量子位成本更低,结果的成功率更高,展示了Grover算法在大型搜索问题中显著的加速效果。
-
关键词
GROVER算法
图着色问题
量子线路
ibmq
布尔可满足性问题
-
Keywords
Grover algorithm
Graph coloring problem
Quantum circuit
ibmq
Boolean satisfiability problem
-
分类号
TP385
[自动化与计算机技术—计算机系统结构]
-
-
题名基于Grover搜索算法的整数分解
被引量：4
- 2
-
-
作者
宋慧超
刘晓楠
王洪
尹美娟
江舵
-
机构
数学工程与先进计算国家重点实验室(信息工程大学)
-
出处
《计算机科学》
CSCD
北大核心
2021年第4期20-25,共6页
-
基金
国家自然科学基金项目(61972413,61701539)
国家密码发展基金(mmjj20180212)。
-
文摘
非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的。Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。文中提出基于Grover搜索算法并结合经典预处理实现整数分解。首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子P和Q;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率。仿真结果验证了使用Grover算法求解素因子P和Q的可行性。文中实现了在搜索空间为16且一次G迭代条件下以近78%的成功概率搜索到目标项。文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异。通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显。
-
关键词
GROVER算法
VQF算法
ibmq
整数分解
Shor算法
-
Keywords
Grover algorithm
Variational quantum factoring algorithm
ibmq
Integer factorization
Shor algorithm
-
分类号
TP385
[自动化与计算机技术—计算机系统结构]
-
