计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 20-25.doi: 10.11896/jsjkx.200800117

所属专题: 密码学 虚拟专题

• 计算机科学理论 • 上一篇    下一篇

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

宋慧超, 刘晓楠, 王洪, 尹美娟, 江舵   

  1. 数学工程与先进计算国家重点实验室(信息工程大学) 郑州450000
  • 收稿日期:2020-06-24 修回日期:2020-11-19 出版日期:2021-04-15 发布日期:2021-04-09
  • 通讯作者: 刘晓楠(prof.liu.xn@foxmail.com)
  • 基金资助:
    国家自然科学基金项目(61972413,61701539);国家密码发展基金(mmjj20180212)

Integer Decomposition Based on Grover Search Algorithm

SONG Hui-chao, LIU Xiao-nan, WANG Hong, YIN Mei-juan, JIANG Duo   

  1. State Key Laboratory of Mathematical Engineering and Advanced Computing,PLA Information Engineering University,Zhengzhou 450000,China
  • Received:2020-06-24 Revised:2020-11-19 Online:2021-04-15 Published:2021-04-09
  • About author:SONG Hui-chao,born in 1996,postgra-duate.His main research interests include quantum algorithm and so on.(quantumsong@163.com)
    LIU Xiao-nan,born in 1977,Ph.D,associate professor,master’s supervisor,is a member of China Computer Federation.His main research interests include quantum algorithm and high-perfor-mance parallel computation.
  • Supported by:
    National Natural Science Foundation of China(61972413,61701539) and National Cryptography Development Fund(mmjj20180212).

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

关键词: Grover算法, IBMQ, Shor算法, VQF算法, 整数分解

Abstract: 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.

Key words: Grover algorithm, IBMQ, Integer factorization, Shor algorithm, Variational quantum factoring algorithm

中图分类号: 

  • TP385
[1]GROVER L K.A Fast Quantum Mechanical Algorithm for Database Search [C]//Proceedings 28th ACM Symposium on Theo-ry of Computation.New York,1996:212-219.
[2]YOUNES A,ROWE J,MILLER J.A Hybrid Quantum Search Engine:A Fast Quantum Algorithm for Multiple Matches[C]//Proceedings of ICENCO.2006.
[3]YOUNES A,ROWE J,MILLER J.Quantum Search Algorithm with More Reliable Behavior Using Partial Diffusion[C]//Proceedings of the seventh International Conference on Quantum Communication,Measurement and Computing.2004:171-174.
[4]AARONSON S,RALL P.Quantum Approxim- ate Counting,Simplified[J].arXiv:1908.10846.
[5]YODER T J,LOW G H,CHUANG I L.Fixed-Point Quantum Search with an Optimal Number of Queries[J].Physical Review Letters,2014,113(21):210501.
[6]ZALKA C.Grover’s Quantum Searching Algori- thm is Optimal[J].Physical Review A,1999,60(4):2746-2751.
[7]GILLIAM A,WOERNER S,GONCIULEA C.Grover Adaptive Search for Constrained Polynomial Binary Optimization[J].ar-Xiv:1912.04088,2019.
[8]RUAN Y,CHEN H W,LIU Z H,et al.Quantum PrincipalComponent Analysis Algorithm[J].Chinese Journal of Compu-ters,2014,37(3):666-676.
[9]JAQUES S,NAEHRIG M,ROETTELER M,et al.Implementing Grover Oracles for Quantum Key Search on AES and LowMC [M]//Advances in Cryptology-EUROCRYPT 2020.2020.
[10]WANG P,TIAN S P,SUN Z W,et al.Quantum Algorithms for Hash Preimage Attacks[J].Quantum Engineering,2020,2(2).
[11]VIKRAM M.Quantum String Comparison Method[J].arXiv:2005.08950,2020.
[12]AMIT S,DEBASRI S,AMLAN C.Circuit Design for K-coloring Problem and It’s Implementation on Nearterm Quantum Devices [J].arXiv:2009.06073,2020.
[13]ANSCHUETZ E R,OLSON J P,ASPURU-GUZIK A,et al.Variational Quantum Factoring [J].arXiv:1808.08927,2018.
[14]GILLIAM A,VENCI C,MURALIDHA-RAN S,et al.Foundational Patterns for Efficient Quan-tum Computing[J].arXiv:1907.11513,2019.
[15]ALAM M,ASH-SAKI A,GHOSH S.Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits [J].arXiv:1907.09631,2019.
[16]WILLSCH M,WILLSCH D,JIN F,et al.Benchmarking theQuantum Approximate Optimization Algorithm[J].Quantum Information Processing,2020,19(7):197.
[17]XU N Y,ZHU J,LU D W,et al.Quantum Factorization of 143 on a Dipolar-Coupling Nuclear Magnetic Resonance System[J].Physical Review Letters,2012,108(13):130501.
[18]CROSS A.The IBM Q Experience and QISKit Open-SourceQuantum Computing Software[C]//APS March Meeting 2018.American Physical Society,2018.
[19]SHOR P W.Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J].Siam Review,1999,41(2):303-332.
[20]YASUHIRO T,NOBORU K.AQuantum Circuit for Shor's Factoring Algorithm Using 2n+2 Qubits [J].Quantum Information and Computation 2006,6(2):184-192.
[1] 刘建美, 王洪, 马智.
Shor整数分解算法的线路优化
Optimization for Shor's Integer Factorization Algorithm Circuit
计算机科学, 2022, 49(6A): 649-653. https://doi.org/10.11896/jsjkx.210600149
[2] 刘晓楠, 宋慧超, 王洪, 江舵, 安家乐.
Grover算法改进与应用综述
Survey on Improvement and Application of Grover Algorithm
计算机科学, 2021, 48(10): 315-323. https://doi.org/10.11896/jsjkx.201100141
[3] 刘晓楠, 荆丽娜, 王立新, 王美玲.
基于申威26010处理器的大规模量子傅里叶变换模拟
Large-scale Quantum Fourier Transform Simulation Based on SW26010
计算机科学, 2020, 47(8): 93-97. https://doi.org/10.11896/jsjkx.200300015
[4] .
应用n—adic展开的快速Harn体制

计算机科学, 2007, 34(5): 79-80.
[5] .
一种新的基于大整数分解困难问题的叛逆者追踪方案

计算机科学, 2006, 33(7): 131-133.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!