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

Hong-Tao Zhang; Yong-Tao Dai; Ling-Ying Tu; Jun Shu; Hong-Mei Xiong; Yi-Fan Hu

doi:doi:10.11648/j.com.20150302.13

| Peer-Reviewed

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

Hong-Tao Zhang, Yong-Tao Dai, Ling-Ying Tu, Jun Shu, Hong-Mei Xiong, Yi-Fan Hu

Published in Communications (Volume 3, Issue 2)

Received: 10 July 2015 Accepted: 18 July 2015 Published: 28 July 2015

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Hong-Tao Zhang

Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China; Department of Communication, School of electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China
Yong-Tao Dai

Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China; Department of Communication, School of electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China
Ling-Ying Tu

Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China;Department of Electronic Information Engineering, School of electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China
Jun Shu

Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China; Department of Automation, School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China
Hong-Mei Xiong

Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China; Department of Communication, School of electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China
Yi-Fan Hu

Nanoelectron Technology and Micro-system Laboratory, Hubei University of Technology, Wuhan, China; Department of Communication, School of electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China

Download PDF

Sections

Plain Text BibTeX RIS

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