Research ArticleOpen AccessGoogle Scholar indexed
Adaptive Phase Matching in Grover’s Algorithm
- 1
- 2
Journal of Quantum Information Science·Volume 01 (2011)·Pages 43–49·Published 29 September 2011·DOI10.4236/jqis.2011.12006
Copy link · social · email
Abstract
When the Grover’s algorithm is applied to search an unordered database, the successful probability usually decreases with the increase of marked items. In order to solve this problem, an adaptive phase matching is proposed. With application of the new phase matching, when the fraction of marked items is greater , the successful probability is equal to 1 with at most two Grover iterations. The validity of the new phase matching is verified by a search example.
KeywordsQuantum ComputingQuantum SearchingGrover’s AlgorithmPhase MatchingAdaptive Phase Shifting
- P. W. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 20-22 November 1994, pp. 124-134. doi:10.1109/SFCS.1994.365700
- L. K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, 1996, pp. 212-221.
- L. K. Grover, “Quantum Mechanics Helps in Searching for a Needle in a Haystack,” Physical Review Letters, Vol. 79, No. 2, 1997, pp. 325-328. doi:10.1103/PhysRevLett.79.325
- M. Boyer, G. Brassard, P. H?yer and A. Tapp, “Tight Bounds on Quantum Searching,” Fortschritte Der Physik, Vol. 46, No. 4-5, 1998, pp. 493-505. doi:10.1002/(SICI)1521-3978(199806)46:4/5 3.0.CO;2-P
- C. Zalka, “Grover’s Quantum Searching Algorithm Is Optimal,” Physical Review A, Vol. 60, No. 4, 1999, pp. 2746-2751. doi:10.1103/PhysRevA.60.2746
- D. Biron, O. Biham, E. Biham, M. Grassl and D. A. Lidar, “Gen-eralized Grover Search Algorithm for Arbitrary Initial Amplitude Distribution,” quant-ph/9801066, 1998, pp. 1-8.
- A. K. Pati, “Fast Quantum Search Algorithm and Bounds on It,” quant-ph/9807067, 1998, pp. 1-4.
- Y. Ozhigov, “Speedup of Iterated Quantum Search by Parallel Performance,” quant-ph/9904039, 1999, pp. 1- 21.
- R. Gingrich, C. P. Williams and N. Cerfm, “Generalized Quantum Search with Parallelism,” quant-ph/9904039, 1999, pp. 1-14.
- L. K. Grover, “Quantum Computers Can Search Rapidly by Using Any Transformation,” Physical Review Letters, Vol. 80, No. 19, 1998, pp. 4329-4332. doi:10.1103/PhysRevLett.80.4329
- G. L. Long, Y. S. Li and W. L. Zhang, “Phase Matching in Quantum Searching,” Physics Letters A, Vol. 262, No. 1, 1999, pp. 27-34. doi:10.1016/S0375-9601(99)00631-3
- D. F. Li and X. X. Li, “More General Quantum Search Algorithm Q = –IγVIτU and the Precise Formula for the Amplitude and the Non-syssetric Effects of Different Rotating Angles,” Physics Letters A, Vol. 287, No. 5-6, 2001, pp. 304-316. doi:10.1016/S0375-9601(01)00498-4
- D. F. Li, X. X. Li and H. T. Huang, “Phase Condition for the Grover Algorithm,” Theoretical and Mathematical Physics, Vol. 144, No. 3, 2005, pp. 1279-1287. doi:10.1007/s11232-005-0159-x
- E. Biham, O. Biham and D. Birom, “Grover’s Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution,” Physical Review A, Vol. 60, No. 4, 1999, pp. 2742-2745. doi:10.1103/PhysRevA.60.2742