| Peer-Reviewed

The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation

Received: 10 July 2015     Accepted: 18 July 2015     Published: 28 July 2015
Views:       Downloads:
Abstract

This paper illustrated the optimality of Grover quantum search algorithm, and simulated the number of iterations and the specific implementation steps of quantum search algorithm with QCL in Linux operating systems, then validated the time complexity of Grover's quantum searching algorithm is O(√(N)) while the algorithm's time complexity on classical computers is O(N). The Grover quantum search algorithm were shown to improve the performance significantly in the random database search problem. This conclusion was drawn from the simulation in the Linux operating systems adopted to quantum computation language. The present study highlighted the importance of high efficiency of the Grover quantum search algorithm to achieve the best possible performance in such cases. The existence of such efficiency is an outstanding advantage of quantum search algorithm over the conventional approach.

Published in Communications (Volume 3, Issue 2)
DOI 10.11648/j.com.20150302.13
Page(s) 42-48
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2015. Published by Science Publishing Group

Keywords

Grover Quantum Search Algorithm, Optimality, Time Complexity, Linux, QCL

References
[1] L. Grover. In Proc. 28th Annual ACM Symposium on the Theory of Computation, pages 212–219, ACMPress, NewYork, 1996.
[2] L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack.Phys.Rev. Lett, 79(2):325, 1997. arXive e-print quant-ph/9706033.
[3] Sun Li, Lu Chun-hong. NMR Simulation of 3-qubit Grover Quantum Search Algorithm, Master's degree, Jiangnan University, 2007.
[4] MA Hong-yuan, WANG Hong-fu,ZHANG Shou. Implementation of the Grover Quantum Search Algorithm in Thermal Cavity[J],Journal of Yanbian University,2008,34(1):27-30.
[5] Ye A L, Guo G C. Scheme for Implementing Quantum Dense Coding in Cavity QED[ J]. Phy s Rev A, 2005, 71:034304.
[6] ZHANG Yu-dong,WEI Geng,WU Le-nan. An Improved Grover Quantum Searching Algorithm[J], Signal processing,2009,Vol25.No.2:256-259.
[7] V. Protopopescu, J. Barhen. Solving a class of continuous global optimization problems using quantum algorithms[J].Physics Letters A,2002,296(2002):9-14.
[8] HAN Guang-pu.The Improvement of Quantum Grover Algorithm and Its Application to Image Retrieval, Master's degree, Nanjing University of Posts and Telecommunications,2013.
[9] Christoph Durr,Peter Hoyer.A quantum algorithm for finding the minimum.Quantum Physics,1999,1.
[10] Avatar Tulsi. Quantum search algorithm tailored to clause satisfaction problems[J].Quantum Physics,2015.
[11] SU Xiao-qin,GUO Guang-can.Quantum communication and quamtum computation[J].Chinese Journal Of Quantum Electronics 2004,6:31-34.
[12] Kwiat P G, Mitchell J R,Schwindt P D D,et al. Grover’s search algorithm:an optical approach[J].J.Mod.Optic,2007,47(2-3):257-266.
[13] Grover L K. Quantum computers can search rapidly by using almost any transformation[J]. Physical Review Letters, 1998,80(19): 4329-4332.
[14] Grover L K. Fixed-point quantum search[J]. Ohys. Rev. Lett, 2005, 95(150501)1-4.
[15] Grover L K.: Rapid sampling through quantum computing. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), pp. 618–626 (2000).
[16] Boyer M, Brassard G, Hoyer P, Tapp A. Tight bounds on quantum searching. In: Proceedings of the Workshop on Physics of Computation: PhysComp’96. IEEE Computer Society Press, 1996.
[17] Nielson MA, Chuang IL. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000.
[18] B.őmer. A procedural formalism for quantum computing. Master’s thesis, Department of Theoretical Physics, Technical University of Vienna,1998.
[19] B.őmer. Structured Quantum Programming, PhD thesis, Technical University of Vienna, 2003.
Cite This Article
  • APA Style

    Hong-Tao Zhang, Yong-Tao Dai, Ling-Ying Tu, Jun Shu, Hong-Mei Xiong, et al. (2015). The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation. Communications, 3(2), 42-48. https://doi.org/10.11648/j.com.20150302.13

    Copy | Download

    ACS Style

    Hong-Tao Zhang; Yong-Tao Dai; Ling-Ying Tu; Jun Shu; Hong-Mei Xiong, et al. The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation. Communications. 2015, 3(2), 42-48. doi: 10.11648/j.com.20150302.13

    Copy | Download

    AMA Style

    Hong-Tao Zhang, Yong-Tao Dai, Ling-Ying Tu, Jun Shu, Hong-Mei Xiong, et al. The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation. Communications. 2015;3(2):42-48. doi: 10.11648/j.com.20150302.13

    Copy | Download

  • @article{10.11648/j.com.20150302.13,
      author = {Hong-Tao Zhang and Yong-Tao Dai and Ling-Ying Tu and Jun Shu and Hong-Mei Xiong and Yi-Fan Hu},
      title = {The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation},
      journal = {Communications},
      volume = {3},
      number = {2},
      pages = {42-48},
      doi = {10.11648/j.com.20150302.13},
      url = {https://doi.org/10.11648/j.com.20150302.13},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.com.20150302.13},
      abstract = {This paper illustrated the optimality of Grover quantum search algorithm, and simulated the number of iterations and the specific implementation steps of quantum search algorithm with QCL in Linux operating systems, then validated the time complexity of Grover's quantum searching algorithm is O(√(N)) while the algorithm's time complexity on classical computers is O(N). The Grover quantum search algorithm were shown to improve the performance significantly in the random database search problem. This conclusion was drawn from the simulation in the Linux operating systems adopted to quantum computation language. The present study highlighted the importance of high efficiency of the Grover quantum search algorithm to achieve the best possible performance in such cases. The existence of such efficiency is an outstanding advantage of quantum search algorithm over the conventional approach.},
     year = {2015}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation
    AU  - Hong-Tao Zhang
    AU  - Yong-Tao Dai
    AU  - Ling-Ying Tu
    AU  - Jun Shu
    AU  - Hong-Mei Xiong
    AU  - Yi-Fan Hu
    Y1  - 2015/07/28
    PY  - 2015
    N1  - https://doi.org/10.11648/j.com.20150302.13
    DO  - 10.11648/j.com.20150302.13
    T2  - Communications
    JF  - Communications
    JO  - Communications
    SP  - 42
    EP  - 48
    PB  - Science Publishing Group
    SN  - 2328-5923
    UR  - https://doi.org/10.11648/j.com.20150302.13
    AB  - This paper illustrated the optimality of Grover quantum search algorithm, and simulated the number of iterations and the specific implementation steps of quantum search algorithm with QCL in Linux operating systems, then validated the time complexity of Grover's quantum searching algorithm is O(√(N)) while the algorithm's time complexity on classical computers is O(N). The Grover quantum search algorithm were shown to improve the performance significantly in the random database search problem. This conclusion was drawn from the simulation in the Linux operating systems adopted to quantum computation language. The present study highlighted the importance of high efficiency of the Grover quantum search algorithm to achieve the best possible performance in such cases. The existence of such efficiency is an outstanding advantage of quantum search algorithm over the conventional approach.
    VL  - 3
    IS  - 2
    ER  - 

    Copy | Download

Author Information
  • Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China

  • Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China

  • Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China

  • Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China

  • Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China

  • Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China

  • Sections