Computer Science ›› 2021, Vol. 48 ›› Issue (10): 315-323.doi: 10.11896/jsjkx.201100141

• Interdiscipline & Frontier • Previous Articles     Next Articles

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).

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

CLC Number: 

  • 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] LI Rong-fan, ZHONG Ting, WU Jin, ZHOU Fan, KUANG Ping. Spatio-Temporal Attention-based Kriging for Land Deformation Data Interpolation [J]. Computer Science, 2022, 49(8): 33-39.
[2] Renata WONG. Application of Early Quantum Algorithms in Quantum Communication,Error Correction and Other Fields [J]. Computer Science, 2022, 49(6A): 645-648.
[3] YAO Xiao-ming, DING Shi-chang, ZHAO Tao, HUANG Hong, LUO Jar-der, FU Xiao-ming. Big Data-driven Based Socioeconomic Status Analysis:A Survey [J]. Computer Science, 2022, 49(4): 80-87.
[4] KONG Yu-ting, TAN Fu-xiang, ZHAO Xin, ZHANG Zheng-hang, BAI Lu, QIAN Yu-rong. Review of K-means Algorithm Optimization Based on Differential Privacy [J]. Computer Science, 2022, 49(2): 162-173.
[5] ZHANG Ya-di, SUN Yue, LIU Feng, ZHU Er-zhou. Study on Density Parameter and Center-Replacement Combined K-means and New Clustering Validity Index [J]. Computer Science, 2022, 49(1): 121-132.
[6] MA Dong, LI Xin-yuan, CHEN Hong-mei, XIAO Qing. Mining Spatial co-location Patterns with Star High Influence [J]. Computer Science, 2022, 49(1): 166-174.
[7] XU Hui-hui, YAN Hua. Relative Risk Degree Based Risk Factor Analysis Algorithm for Congenital Heart Disease in Children [J]. Computer Science, 2021, 48(6): 210-214.
[8] SONG Hui-chao, LIU Xiao-nan, WANG Hong, YIN Mei-juan, JIANG Duo. Integer Decomposition Based on Grover Search Algorithm [J]. Computer Science, 2021, 48(4): 20-25.
[9] ZHANG Yan-jin, BAI Liang. Fast Symbolic Data Clustering Algorithm Based on Symbolic Relation Graph [J]. Computer Science, 2021, 48(4): 111-116.
[10] ZHANG Han-shuo, YANG Dong-ju. Technology Data Analysis Algorithm Based on Relational Graph [J]. Computer Science, 2021, 48(3): 174-179.
[11] ZOU Cheng-ming, CHEN De. Unsupervised Anomaly Detection Method for High-dimensional Big Data Analysis [J]. Computer Science, 2021, 48(2): 121-127.
[12] LIU Xin-bin, WANG Li-zhen, ZHOU Li-hua. MLCPM-UC:A Multi-level Co-location Pattern Mining Algorithm Based on Uniform Coefficient of Pattern Instance Distribution [J]. Computer Science, 2021, 48(11): 208-218.
[13] ZHANG Yu, LU Yi-hong, HUANG De-cai. Weighted Hesitant Fuzzy Clustering Based on Density Peaks [J]. Computer Science, 2021, 48(1): 145-151.
[14] YOU Lan, HAN Xue-wei, HE Zheng-wei, XIAO Si-yu, HE Du, PAN Xiao-meng. Improved Sequence-to-Sequence Model for Short-term Vessel Trajectory Prediction Using AIS Data Streams [J]. Computer Science, 2020, 47(9): 169-174.
[15] ZHANG Su-mei and ZHANG Bo-tao. Evaluation Model Construction Method Based on Quantum Dissipative Particle Swarm Optimization [J]. Computer Science, 2020, 47(6A): 84-88.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!