Volume 3, Issue 2, March 2015, Page: 42-48
The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation
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
Received: Jul. 10, 2015;       Accepted: Jul. 18, 2015;       Published: Jul. 28, 2015
DOI: 10.11648/j.com.20150302.13      View  5213      Downloads  172
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.
Keywords
Grover Quantum Search Algorithm, Optimality, Time Complexity, Linux, QCL
To cite this article
Hong-Tao Zhang, Yong-Tao Dai, Ling-Ying Tu, Jun Shu, Hong-Mei Xiong, Yi-Fan Hu, The Proof of Quantum Search Algorithm Optimization and the Simulation of the Algorithm Implementation, Communications. Vol. 3, No. 2, 2015, pp. 42-48. doi: 10.11648/j.com.20150302.13
Reference
[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.
Browse journals by subject