Adaptive Phase Matching in Grover’s Algorithm

Panchi Li, Kaoping Song

.

DOI: 10.4236/jqis.2011.12006                

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.

Keywords

Quantum Computing, Quantum Searching, Grover’s Algorithm, Phase Matching, Adaptive Phase Shifting

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	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.
[3]	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
[4]	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<493::AID-PROP493>3.0.CO;2-P
[5]	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
[6]	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.
[7]	A. K. Pati, “Fast Quantum Search Algorithm and Bounds on It,” quant-ph/9807067, 1998, pp. 1-4.
[8]	Y. Ozhigov, “Speedup of Iterated Quantum Search by Parallel Performance,” quant-ph/9904039, 1999, pp. 1- 21.
[9]	R. Gingrich, C. P. Williams and N. Cerfm, “Generalized Quantum Search with Parallelism,” quant-ph/9904039, 1999, pp. 1-14.
[10]	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
[11]	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
[12]	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
[13]	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
[14]	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
[15]	E. Biham and D. Kenigsberg, “Grover’s Quantum Search Algorithm for an Ar-bitrary Initial Mixed State,” Physical Review A, Vol. 66, No. 6, 2002, pp. 1-4.
[16]	L. K. Grover, “Fixed-Point Quantum Search,” Physical Review Letters, Vol. 95, No. 15, 2005, pp. 1-4.
[17]	D. F. Li, X. R. Li, H. T. Huang and X. X. Li, “Fixed- Point Quantum Search for Different Phase Shifts,” quant- ph/0604062, 2006, pp. 1-8.
[18]	M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information,” Cambridge University Press, Cambridge, 2000, pp. 248-255.