基于Grover搜索算法的整数分解  

Integer Decomposition Based on Grover Search Algorithm

作　　者：宋慧超 刘晓楠[1] 王洪[1] 尹美娟[1] 江舵 SONG Hui-chao;LIU Xiao-nan;WANG Hong;YIN Mei-juan;JIANG Duo(State Key Laboratory of Mathematical Engineering and Advanced Computing,PLA Information Engineering University,Zhengzhou 450000,China)

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

出　　处：《计算机科学》2021年第4期20-25,共6页Computer Science

基　　金：国家自然科学基金项目(61972413,61701539);国家密码发展基金(mmjj20180212)。

摘　　要：非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的。Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。文中提出基于Grover搜索算法并结合经典预处理实现整数分解。首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子P和Q;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率。仿真结果验证了使用Grover算法求解素因子P和Q的可行性。文中实现了在搜索空间为16且一次G迭代条件下以近78%的成功概率搜索到目标项。文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异。通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显。One of the most fundamental problems in computer science is unstructured search,and Grover quantum search algorithm is designed for the unstructured search problem.Grover quantum search algorithm can be used to solve graph coloring,shortest path sorting and other problems,and it can also effectively decipher the cipher system.In this paper,Grover search algorithm combined with classical pretreatment is proposed to realize integer decomposition.Firstly,quantum circuits of Grover algorithm with different qubits are simulated based on IBMQ cloud platform,and the prime factors P and Q of N are simulated using Grover algorithm.Then,the simplified equation is transformed into Boolean logic relation to build Oracle in Grover algorithm.Finally,the probability of finding the solution is changed by changing the number of iterations.According to the experimental results of the simulation circuit,the feasibility of solving prime factors P and Q using Grover algorithm is verified,and the target item is searched with 78%probability of success under the condition of 16 search space and one G iteration.The differences of quantum bit number and time asymptotic complexity between Grover algorithm and Shor algorithm for solving some numbers are compared.The experiment of integer decomposition by Grover quantum search algorithm expands the application field of this algorithm,and the acceleration effect of Grover algorithm is especially obvious in large search problems.

关 键 词：GROVER算法 VQF算法 IBMQ 整数分解 Shor算法 

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