Adaptive Phase Matching in Grover’s Algorithm
Panchi Li, Kaoping Song
DOI: 10.4236/jqis.2011.12006   PDF   HTML     5,095 Downloads   9,311 Views   Citations


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.

Share and Cite:

P. Li and K. Song, "Adaptive Phase Matching in Grover’s Algorithm," Journal of Quantum Information Science, Vol. 1 No. 2, 2011, pp. 43-49. doi: 10.4236/jqis.2011.12006.

Conflicts of Interest

The authors declare no conflicts of interest.


[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.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.