计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 20-25.doi: 10.11896/jsjkx.200800117
所属专题: 密码学 虚拟专题
宋慧超, 刘晓楠, 王洪, 尹美娟, 江舵
SONG Hui-chao, LIU Xiao-nan, WANG Hong, YIN Mei-juan, JIANG Duo
摘要: 非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的。Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。文中提出基于Grover搜索算法并结合经典预处理实现整数分解。首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子P和Q;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率。仿真结果验证了使用Grover算法求解素因子P和Q的可行性。文中实现了在搜索空间为16且一次G迭代条件下以近78%的成功概率搜索到目标项。文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异。通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显。
中图分类号:
[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. |
|