计算机科学 ›› 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: Grover algorithm, Quantum computing, Phase improvement, Key search, Data mining

中图分类号: 

  • 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] 徐慧慧, 晏华. 基于相对危险度的儿童先心病风险因素分析算法[J]. 计算机科学, 2021, 48(6): 210-214.
[2] 宋慧超, 刘晓楠, 王洪, 尹美娟, 江舵. 基于Grover搜索算法的整数分解[J]. 计算机科学, 2021, 48(4): 20-25.
[3] 张岩金, 白亮. 一种基于符号关系图的快速符号数据聚类算法[J]. 计算机科学, 2021, 48(4): 111-116.
[4] 张寒烁, 杨冬菊. 基于关系图谱的科技数据分析算法[J]. 计算机科学, 2021, 48(3): 174-179.
[5] 邹承明, 陈德. 高维大数据分析的无监督异常检测方法[J]. 计算机科学, 2021, 48(2): 121-127.
[6] 张煜, 陆亿红, 黄德才. 基于密度峰值的加权犹豫模糊聚类算法[J]. 计算机科学, 2021, 48(1): 145-151.
[7] 游兰, 韩雪薇, 何正伟, 肖丝雨, 何渡, 潘筱萌. 基于改进Seq2Seq的短时AIS轨迹序列预测模型[J]. 计算机科学, 2020, 47(9): 169-174.
[8] 罗文俊, 雷爽. 噪声信道下的盲量子计算[J]. 计算机科学, 2020, 47(7): 37-41.
[9] 张素梅, 张波涛. 一种基于量子耗散粒子群的评估模型构建方法[J]. 计算机科学, 2020, 47(6A): 84-88.
[10] 袁得嵛, 章逸钒, 高见, 孙海春. 基于用户特征提取的新浪微博异常用户检测方法[J]. 计算机科学, 2020, 47(6A): 364-368.
[11] 邓甜甜, 熊荫乔, 何贤浩. 一种基于时序性告警的新型聚类算法[J]. 计算机科学, 2020, 47(6A): 440-443.
[12] 李莉. 基于判断聚合的分布式数据挖掘分类算法研究[J]. 计算机科学, 2020, 47(6A): 450-456.
[13] 周恒, 王拥军, 王宝山, 燕健. 直觉主义视角下量子逻辑的进一步解释[J]. 计算机科学, 2020, 47(5): 1-6.
[14] 余航, 魏炜, 谭征, 刘惊雷. 基于信任系统的条件偏好协同度量框架[J]. 计算机科学, 2020, 47(4): 74-84.
[15] 丁武, 马媛, 杜诗蕾, 李海辰, 丁公博, 王超. 基于XGBoost算法的多元水文时间序列趋势相似性挖掘[J]. 计算机科学, 2020, 47(11A): 459-463.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 韩奎奎,谢在鹏,吕鑫. 一种基于改进遗传算法的雾计算任务调度策略[J]. 计算机科学, 2018, 45(4): 137 -142 .
[2] 贾伟,华庆一,张敏军,陈锐,姬翔,王博. 基于改进粒子群优化的移动界面模式聚类算法[J]. 计算机科学, 2018, 45(4): 220 -226 .
[3] 丁舒阳,黎冰,侍洪波. 基于改进的离散PSO算法的FJSP的研究[J]. 计算机科学, 2018, 45(4): 233 -239 .
[4] 崔建京,龙军,闵尔学,于洋,殷建平. 同态加密在加密机器学习中的应用研究综述[J]. 计算机科学, 2018, 45(4): 46 -52 .
[5] 司念文,王衡军,李伟,单义栋,谢鹏程. 基于注意力长短时记忆网络的中文词性标注模型[J]. 计算机科学, 2018, 45(4): 66 -70 .
[6] 杨沛安, 武杨, 苏莉娅, 刘宝旭. 网络空间威胁情报共享技术综述[J]. 计算机科学, 2018, 45(6): 9 -18 .
[7] 崔一辉, 宋伟, 彭智勇, 杨先娣. 基于差分隐私的多源数据关联规则挖掘方法[J]. 计算机科学, 2018, 45(6): 36 -40 .
[8] 张昱, 高克宁, 于戈. 一种融合节点属性信息的社会网络链接预测方法[J]. 计算机科学, 2018, 45(6): 41 -45 .
[9] 朱文强. 面向O2O服务的移动社交网络个性化可信群体识别模型[J]. 计算机科学, 2018, 45(6): 76 -83 .
[10] 吴建霞, 杨永立. 一种降低FBMC-OQAM系统PAPR的算法[J]. 计算机科学, 2018, 45(6): 89 -95 .