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

作     者：宋慧超 刘晓楠 王洪 尹美娟 江舵 SONG Hui-chao;LIU Xiao-nan;WANG Hong;YIN Mei-juan;JIANG Duo

作者机构：数学工程与先进计算国家重点实验室(信息工程大学)郑州450000 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2021年第48卷第4期

页      面：20-25页

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：Grover算法 VQF算法 IBMQ 整数分解 Shor算法 

摘      要：非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的。Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。文中提出基于Grover搜索算法并结合经典预处理实现整数分解。首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子P和Q;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率。仿真结果验证了使用Grover算法求解素因子P和Q的可行性。文中实现了在搜索空间为16且一次G迭代条件下以近78%的成功概率搜索到目标项。文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异。通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显。