计算机科学 ›› 2021, Vol. 48 ›› Issue (10): 315-323.doi: 10.11896/jsjkx.201100141

• 交叉&前沿 • 上一篇    下一篇

Grover算法改进与应用综述

刘晓楠, 宋慧超, 王洪, 江舵, 安家乐   

  1. 数学工程与先进计算国家重点实验室(信息工程大学) 郑州450000
  • 收稿日期:2020-11-20 修回日期:2021-02-26 出版日期:2021-10-15 发布日期:2021-10-18
  • 通讯作者: 宋慧超(quantumsong@163.com)
  • 作者简介:prof.liu.xn@foxmail.com
  • 基金资助:
    国家自然科学基金项目(61972413,61701539);国家密码发展基金(mmjj20180212)

Survey on Improvement and Application of Grover Algorithm

LIU Xiao-nan, SONG Hui-chao, WANG Hong, JIANG Duo, AN Jia-le   

  1. State Key Laboratory of Mathematical Engineering and Advanced Computing(PLA Information Engineering University),Zhengzhou 450000,China
  • Received:2020-11-20 Revised:2021-02-26 Online:2021-10-15 Published:2021-10-18
  • About author: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.
    SONG Hui-chao,born in 1996,postgra-duate.His main research interests include quantum algorithm and so on.
  • Supported by:
    National Natural Science Foundation of China(61972413,61701539) and National Cryptography Development Fund(mmjj20180212).

摘要: 量子信息科学是一门新兴的交叉学科,它在信息领域中有着独特的性能,在提高运算速度、确保信息安全、增大信息容量和提高检测精度等方面可突破现有经典信息系统的极限。Grover算法是一类典型的量子算法,能够对任意经典暴力穷举搜索问题实现二次加速,进一步推动了量子计算的发展,如何有效地改进和应用Grover算法成为量子计算的一个重要研究领域。文中综述了Grover算法的优化改进和应用,对Grover算法在不同领域应用及不同方面的改进进行了概述,并对Grover算法未来的改进和相关应用的若干研究方向进行了探讨。

关键词: Grover算法, 量子计算, 密钥搜索, 数据挖掘, 相位改进

Abstract: Quantum information science is a new interdisciplinary subject,which has unique performance in the field of information.It can break through the limits of the existing classical information systems in the aspects of improving computing speed,ensuring information security,increasing information capacity and improving detection accuracy.Grover algorithm is a typical quantum algorithm,which can realize quadratic acceleration for any classical brute force exhaustive search problem,further promoting the development of quantum computing.How to effectively improve and apply Grover algorithm has become an important research field of quantum computing.This paper summarizes the optimization,improvement and application of Grover algorithm,summarizes the application and improvement of Grover algorithm in different fields,and discusses some research directions of future algorithm improvement and related applications of Grover algorithm.

Key words: Data mining, Grover algorithm, Key search, Phase improvement, Quantum computing

中图分类号: 

  • TP385
[1]FEYMAN R P.Simulating Physics with Computers[J].International Journal of Theoretical Physics,1982,21(6):467-488.
[2]DEUTSCH D.Quantum Theory,the Church-Turing Principle and the UniversalQuantum Computer[J].Proceedings of the Royal Society of London,1985,400(1818):97-117.
[3]SHOR P W.Algorithm for Quantum Computation:Discrete Logarithms and Factoring Algorithm[C]// Proceedings of the 35th Annual Symposium on Foundations of Computer Science.Santa Fe,USA,1994:124-134.
[4]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.
[5]GROVER L K.A Framework for Fast Quantum Mechanical Algorithms[C// Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing(STOC '98).1998:53-62.
[6]LONG G L,ZHANG W L,LI Y S,et al.ArbitraryPhase Rotation of the Marked State Cannot Be Used for Grover's Quantum Search Algorithm[J].Communication in Theoretical Physics,1999,32(3):335-270.
[7]LONG G L,LI Y S,XIAO L,et al.Grover Quantum Search Algorithm and Its Improvement [J].Nuclear Physics Review,2004,21(2):114-116.
[8]LONG G L.Grover Algorithm with Zero Theore-tical FailureRate[J].Physical Review A,2001,64(2):436-454.
[9]HOYER P.On Arbitrary Phases in Quantum Amplitude Amplification[J].Physical Review A,2000,62(5):052304.
[10]LONG G L,YAN H Y,LI Y S,et al.General Phase Matching Condition for Quantum Searching[J].arXiv:quant-ph/0107013.
[11]BHATTACHARYA N,VAN LINDEN VAN DEN HEUVELL H B,SPREEUW R J C.Implementation of Quantum Search Algorithm Using Classical Fourier Optics[J].Physical Review Letters,2002,88(13):137901.
[12]PUENTES G,MELA C L,LEDSMA S,et a1.Optical Simulation of Quantum AlgorithmsUsing Programmable Liquid-crystal Displays [J].Physical Review A,2004,69(4):42319-042319.
[13]LONG G L,YAN H Y,LI Y S,et al.Experimental NMR Realization of a Generalized Quantum Search Algorithm[J].Physics Letters A,2001,286(2/3):121-126.
[14]GROVER L K.Fixed-point Quantum Search[J].Physical Review Letters,2005,95(15):256-259.
[15]LI P C,LI S Y.Phase Matching in Grover's Algorithm[J].Physics Letters A,2007,366(1/2):42-46.
[16]LI P C,LI S Y.Phase Matching in Quantum Searching Algorithm with Weighted Targets [J].Chinese Journal of Computational Physics,2008,25(5):623-630.
[17]YOUNES A.Fixed Phase Quantum Search Algorithm[J].ar-Xiv:0704.1585,2007.
[18]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.
[19]ZHONG P C,B W S.Research on Quantum Searching Algo-rithms Based on Phase Shifts[J].Chinese Physics Letters,2008,25(8):2774-2777.
[20]LI X,LI P C.A Fixed-Phase Quantum Search Algorithm with More Flexible Behavior[J].Journal of Quantum Information Science,2012,2(2):28-34.
[21]MA B W,BAO W S,LI T,et al.A Four-Phase Improvement of Grover's Algorithm[J].Chinese Physics Letters,2017,34(7):33-37.
[22]BIRON D,BIHAM O,BIHAM E,et al.Generalized GroverSearch Algorithm for Arbitrary Initial Amplitude Distribution[J].Lecture Notes in Computer Science,1998,1509:140-147.
[23]BIHAM E,KENIGSBERG D.Grover's Quant-um Search Algorithm for an Arbitrary Initial Mixed State[J].Physical Review A,2002,66(6):062301.
[24]SHAPIRA D,SHIMONI Y,BIHAM O,et al.Algebraic Analysis of Quantum Search with Pureand Mixed States[J].Physical Review A,2005,71(4):42320-42320.
[25]GROVER L K,RADHAKRISHNAN J.Is Partial QuantumSearch of a Database Any Easier?[J].arXiv:quantph/0407122,2004.
[26]KOREPIN V E,GROVER L K.Simple Algorithm for PartialQuantum Search[J].Quantum Information Processing,2006,5(1):5-10.
[27]ZHOU R G.Multi-mode Partial Quantum Search Algorithm[J].Journal of Southwest Jiao tong University:Natural Science Edition,2008,46(4):193-195.
[28]YOUNES A,ROWE J,MILLER J.A Hybrid Quantum Search Engine:A Fast Quantum Algorithm for Multiple Matches[J].arXiv:quantph/0311171,2003.
[29]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.
[30]YOUNES A,ROWE J,MILLER J.Quantum Searching via Entanglement and Partial Diffusion[J].Physica D Nonlinear Phenomena,2008,237(8):1074-1078.
[31]BOYER M,BRASSARD G,HOYER P,et al.Tight Bounds on Quantum Search[J].WILEY-VCH Verlag Berlin GmbH,1998,46(4/5):493-505.
[32]BRASSARD G,HOYER P,TAPP A.Quantum Counting [C]//Proceedings of 25th International Colloquium Automata Language and Programming.Berlin:Springer-Verlag,1998(1443):820-831.
[33]SUZUKI Y,UNO S,RAYMOND R,et al.Amp-litude Estimation without Phase Estimation[J].arXiv:1904.10246,2019.
[34]ZHU W N,CHEN H W.Grover Algorithm for Iteration Number Adaptive[J].Chinese Journal of Electronics,2016,44(12):2975-2980.
[35]LIU J.An Optimum Algorithm for Quantum Search[J].arXiv:2010.03949,2020.
[36]AARONSON S,RALL P.Quantum Approxim- ate Counting,Simplified[J].arXiv:1908.10846,2020.
[37]SONG H,DAI K,WANG Z Y.AnImproved Quantum SearchAlgorithm[J].Computer Engineering and Science,2002,24(5):4-7.
[38]CHEN H G,LI B,SHEN Z K.Search Times Calculation of Approximate Full Probability Grover Algorithm[J].Computer Engineering and Applications,2004(3):58-59.
[39]ZHANG Y D,WEI G,WU L N.An Improved Grover Quantum Search Algorithm[J].Signal Processing,2009,25(2):256-259.
[40]XIE X M,DUAN L Z,QIU T R,et al.Improved QuantumSearch Algorithm and Its Application in Solving Nuclear Properties[J].Computer Engineering and Applications,2020(14):57-61.
[41]HE X Y,ZHANG J L,SUN X M.Quantum Search with Prior Knowledge[J].arXiv:2009.08721,2020.
[42]SUN X M,YAO A C.On the Quantum Query Complexity ofLocal Search in Two and Three Dimensions[J].Algorithmica,2009,55(3):576-600.
[43]JIN W L,CHEN X D.Phase Mismatch Quantum search algo-rithm[J].Acta Electronica Sinica,2012,40 (1):189-192.
[44]BAO W S,SONG Z,ZHONG P C,et al.Quantum Meet-in-the-middle Search Algorithm for Subsets and Problems[J].Chinese Journal of Electronics,2011,39(1):128-132.
[45]ZHANG K,KOREPIN V E.Depth Optimization of QuantumSearch Algorithms beyond Grover's Algorithm[J].arXiv:1908.04171,2020.
[46]PENG H,JING J.Research on Grover Routing Algorithm forWireless Self-organizing Quantum Communication Network [J].Journal of Zhejiang University of Technology,2014,42(6):612-615.
[47]MENG L M,SONG W B.MANET Routing Protocol Based on Grover Search Algorithm [J].China Communications:English Edition,2013(3):145-156.
[48]LIU Y G.Traffic Equalization Routing Algorithm for Wireless Mesh Networks Based on Grover Search [J].Computer Applications,2014(7):1956-1959.
[49]LIU Y G.Multi-constraint Routing Algorithm Based onGrover Search [J].Communications Technology,2015,48(5):594-597.
[50]DING W J,ZHOU K,ZHOU G M,et al.Research on Routing Algorithm of Wireless Sensor Network Based on Grover Fusion Theory [J].Journal of Sensing Technology,2016,29(9):1425-1429.
[51]BEJERANO Y,HAN S J,KUMAR A.Efficient Load-balancing Routing for Wireless Mesh Networks[J].Computer Networks,2007,51(10):2450-2466.
[52]HE J,CHEN J,CHAN S H G.Extending WLAN CoverageUsing Infrastructure less Access Points[C]//HPSR 2005:Proceedings of Workshop on High Performance Switching & Routing.Piscataway:IEEE,2005:162-166.
[53]VENTURA D,MARTINEZ T.Quantum associative memory[J].Information Sciences,2000,124(1/2/3/4):273-296.
[54]ANGUITA D,RIDELLA S,RIVIECCIO F,et al.Quantum Optimization for Training Support Vector Machines[J].Neural Networks,2003,16(5/6):763-770.
[55]REBENTROST P,MOHSENI M,LLOYD S.QuantumSupport Vector Machine for Big Data Classification[J].Physical Review Letters,2014,113(13):130503.
[56]LI Z,LIU X,XU N,et al.Experimental Realization of a Quantum Support Vector Machine[J].Physical Review Letters,2015,114(14):140504.
[57]WIEBE N,KAPOOR A,SVORE K M.Quantum PerceptronModels[J].arXiv:1602.04799,2016.
[58]RUAN Y,CHEN H W,LIU Z H,et al.Quantum Principal Component Analysis Algorithm[J].Journal of Computer Science,2014(3):666-676.
[59]WIEBE N,KAPOOR A,SVORE K M.Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning[J].Quantum Information & Computation,2014,15(3):318-358.
[60]LLOYD S,MOHSENI M,REBENTROST P.Quantum Algorithms for Supervised and Unsupervised Machine Learning[J].arXiv:1307.0411,2013.
[61]WIEBE N,KAPOOR A,SVORE K M.Quantum deep learning[J].arXiv:1412.3489,2014.
[62]AIMEUR E,BRASSARD G,GAMBS S.Quantum ClusteringAlgorithms[C]//Proceedings of the 24th International Confe-rence on Machine Learning.Corvallis,USA,2007:1-8.
[63]CHEN H W,GAO Y,ZHANG J.Quantum K-Nearest Neighbor algorithm [J].Journal of Southeast University (Natural Science edition),2015,45(4):647-651.
[64]GAILTA,OGNJEN M,VICTORIA B,et al.Number Partitioning with Grover's Algorithm in Central Spin Systems[J].ar-Xiv:2009.05549,2020.
[65]BRASSARD G,HOYER P,TAPP A.Quantum Algorithm for the Collision Problem[J].arXiv:quantph/9705002,1997.
[66]SERGI R,EMANUELE B,JOSE I L,et al.Quantum Search for Scaled Hash Function Preimages[J].arXiv:2009.00621,2020.
[67]DU F W,WANG H,MA Z,et al.Quantum Collision Search Algorithm Against New Fork-256[J].Journal of Electronics,2014(4):366-370.
[68]DIFFIE W,HELLMAN M E.Special Feature ExhaustiveCryptanalysis of the NBS Data Encryption Standard[J].Computer,2006,10(6):74-84.
[69]BELLARE M,KOHNO T.Hash Function Balance and Its Impact on Birthday Attacks[C]// Eurocrypt Conference.2004:401-418.
[70]SAARINEN M J O.A Meet-in-the-Middle Collision AttackAgainst the New FORK-256[J].Indocrypt,2007(2):10-17.
[71]ZHONG P C,BAO W S.Quantum Metathesis Search Algorithm of Triple DES [J].Science Bulletin,2009,54(19):3003-3007.
[72]YE F,YUAN J B.Key Search Quantum Circuit Design of AES Encryption Algorithm [J].Journal of Southwest Jiao tong University,2010(2):302-306.
[73]DUAN B J,YUAN J B,YANG J,et al.Research on Parallel Quantum Search Attack of Packet Encryption Algorithm [J].Small Microcomputer Systems,2011(9):1908-1912.
[74]CHEN Y H,JIA H H,JIANG L Y,et al.ECC Scanning Attack Based on GroverAlgorithm [J].Information Network Security,2016(2):28-32.
[75]JAI H,WANG C,GU J,et al.Correction of ECC Attack Error Bit Based on Grover Quantum Meet-in-the-middle Search Algorithm [J].Information Network Security,2016(6):28-34.
[76]WANG C,CAO L,JIA H,et al.ECC Voltage Burr Attack Algorithm Based on 0.1 Rotational Phase Grover algorithm [J].Journal of Communications,2017,38(8):1-8.
[77]WANG H,MA Z,MA C G,et al.An Efficient Quantum Meet-in-the-middle Attack against NTRU-2005[J].ChinSciBull,2013(58):3514-3518.
[78]XIONG Z,WANG J,WANG Y,et al.An Improved MITM Attack against NTRU[J].Int. J. Sec. App.,2012(6):269-274.
[79]WANG X,BAO W S,FU X Q.A Quantum Algorithm forSearching a Target Solution of Fixed Weight[J].Chinese ence Bulletin,2011,56(6):484-489.
[80]MU W J,YOU Z H,ZHAO M H,et al.Mining Web Data with Quantum Grover Search Algorithm[J].Computer Applications,2005,25(10):2310-2311,2317.
[81]LI H S.Research on Key Technologies of Quantum Image processing [D].Chengdu:University of Electronic Science and Technology of China,2014.
[82]ZHAO H Y,WANG X Q,MA Y.Big Data Security Authentication Scheme Combining Quantum Cryptography with Grover Search [J].Journal of Xiangtan University,2016,38(4):76-79.
[83]ZHU W N,LIU Z H.User Recognition Algorithm Based on Quantum Computing[J].Acta Electronica Sinica,2008,46(1):24-30.
[84]ANTHONY E,OLIVER K.Application of a Quantum SearchAlgorithm to High-Energy Physics Data at the Large Hadron Collider[J].arXiv:2010.00649,2020.
[85]SUN G D,SU S H,XU M Z.Quantum Computing Algorithm for Root Problem [J].Journal of Beijing University of Techno-logy,2015(3):366-371.
[86]ZHOU L Z,LI F.Signal Detection of Communication System Based on Grover Algorithm [J].Computer Engineering,2010,36(15):250-252.
[87]HAO L,LIU D,LONG G L.An N/4 Fixed-point Duality Quantum Search Algorithm [J].Science China,2010,53(9):1765-1768.
[88]AMIT S,DEBASRI S,AMLAN C.Circuit Design for K-coloring Problem and It's Implementation on Near-term Quantum Devices [J].arXiv:2009.06073,2020.
[89]VIKRAM M.Quantum String Comparison Method[J].arXiv:2005.08950,2020.
[90]SONG H C,LIU X N,WANG H,et al.Integer Decomposition Based on Grover Search Algorithm[J].Computer Science,2021,48(4):20-25.
[1] 黎嵘繁, 钟婷, 吴劲, 周帆, 匡平.
基于时空注意力克里金的边坡形变数据插值方法
Spatio-Temporal Attention-based Kriging for Land Deformation Data Interpolation
计算机科学, 2022, 49(8): 33-39. https://doi.org/10.11896/jsjkx.210600161
[2] Renata WONG.
早期量子算法在量子通信、量子纠错等领域的应用
Application of Early Quantum Algorithms in Quantum Communication,Error Correction and Other Fields
计算机科学, 2022, 49(6A): 645-648. https://doi.org/10.11896/jsjkx.210400214
[3] 么晓明, 丁世昌, 赵涛, 黄宏, 罗家德, 傅晓明.
大数据驱动的社会经济地位分析研究综述
Big Data-driven Based Socioeconomic Status Analysis:A Survey
计算机科学, 2022, 49(4): 80-87. https://doi.org/10.11896/jsjkx.211100014
[4] 孔钰婷, 谭富祥, 赵鑫, 张正航, 白璐, 钱育蓉.
基于差分隐私的K-means算法优化研究综述
Review of K-means Algorithm Optimization Based on Differential Privacy
计算机科学, 2022, 49(2): 162-173. https://doi.org/10.11896/jsjkx.201200008
[5] 马董, 李新源, 陈红梅, 肖清.
星型高影响的空间co-location模式挖掘
Mining Spatial co-location Patterns with Star High Influence
计算机科学, 2022, 49(1): 166-174. https://doi.org/10.11896/jsjkx.201000186
[6] 张亚迪, 孙悦, 刘锋, 朱二周.
结合密度参数与中心替换的改进K-means算法及新聚类有效性指标研究
Study on Density Parameter and Center-Replacement Combined K-means and New Clustering Validity Index
计算机科学, 2022, 49(1): 121-132. https://doi.org/10.11896/jsjkx.201100148
[7] 徐慧慧, 晏华.
基于相对危险度的儿童先心病风险因素分析算法
Relative Risk Degree Based Risk Factor Analysis Algorithm for Congenital Heart Disease in Children
计算机科学, 2021, 48(6): 210-214. https://doi.org/10.11896/jsjkx.200500082
[8] 宋慧超, 刘晓楠, 王洪, 尹美娟, 江舵.
基于Grover搜索算法的整数分解
Integer Decomposition Based on Grover Search Algorithm
计算机科学, 2021, 48(4): 20-25. https://doi.org/10.11896/jsjkx.200800117
[9] 张岩金, 白亮.
一种基于符号关系图的快速符号数据聚类算法
Fast Symbolic Data Clustering Algorithm Based on Symbolic Relation Graph
计算机科学, 2021, 48(4): 111-116. https://doi.org/10.11896/jsjkx.200800011
[10] 张寒烁, 杨冬菊.
基于关系图谱的科技数据分析算法
Technology Data Analysis Algorithm Based on Relational Graph
计算机科学, 2021, 48(3): 174-179. https://doi.org/10.11896/jsjkx.191200154
[11] 邹承明, 陈德.
高维大数据分析的无监督异常检测方法
Unsupervised Anomaly Detection Method for High-dimensional Big Data Analysis
计算机科学, 2021, 48(2): 121-127. https://doi.org/10.11896/jsjkx.191100141
[12] 刘新斌, 王丽珍, 周丽华.
MLCPM-UC:一种基于模式实例分布均匀系数的多级co-location模式挖掘算法
MLCPM-UC:A Multi-level Co-location Pattern Mining Algorithm Based on Uniform Coefficient of Pattern Instance Distribution
计算机科学, 2021, 48(11): 208-218. https://doi.org/10.11896/jsjkx.201000097
[13] 张煜, 陆亿红, 黄德才.
基于密度峰值的加权犹豫模糊聚类算法
Weighted Hesitant Fuzzy Clustering Based on Density Peaks
计算机科学, 2021, 48(1): 145-151. https://doi.org/10.11896/jsjkx.200400043
[14] 游兰, 韩雪薇, 何正伟, 肖丝雨, 何渡, 潘筱萌.
基于改进Seq2Seq的短时AIS轨迹序列预测模型
Improved Sequence-to-Sequence Model for Short-term Vessel Trajectory Prediction Using AIS Data Streams
计算机科学, 2020, 47(9): 169-174. https://doi.org/10.11896/jsjkx.190800060
[15] 罗文俊, 雷爽.
噪声信道下的盲量子计算
Blind Quantum Computation over Noise Channels
计算机科学, 2020, 47(7): 37-41. https://doi.org/10.11896/jsjkx.190600020
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!