Journal of Quantum Informatio n Science, 2011, 1, 4349 doi:10.4236/jqis.2011.12006 Published Online September 2011 (http://www.SciRP.org/journal/jqis) Copyright © 2011 SciRes. JQIS Adaptive Phase Matching in Grover’s Algorithm Panchi Li1*, Kaoping Song2 1School of Computer & Information Technology, Northeast Petroleum University, Daqing, China 2School of Petroleum Engineering, Northeast Petroleum University, Daqing, China Email: *lipanchi@vip.sina.com Received June 28, 2011; revised August 16, 2011; accepted August 26, 2011 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 358 , 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 1. Introduction Shor’s prime factoring algorithm and Grover’s quantum search algorithm are two of the great quantum algorithms [1,2]. Grover’s search algorithm provides a dramatic example of the potential speedup offered by quantum computers [2,3]. The problem addressed by Grover’s algorithm can be viewed as trying to find a marked ele ment in an unsorted database of size N. To solve this problem, a classical computer would need, on average, 2N database queries and N queries in the worst case. Using Grover’s algorithm, a quantum computer can ac complish the same task using merely NO queries. The importance of Grover’s result stems from the fact that it proves the enhanced power of quantum computers compared to classical ones for a whole class of oracle based problems, for which the bound on the efficiency of classical algorithms is known. At present, Grover’s quan tum search algorithm has been greatly noticed and has become a challenging research field. However, the Grover’s algorithm also has some limitations. When the fraction of marked items is greater than a quarter of the total items in the database, the success probability will rapidly decrease, and when the fraction of marked items is greater than half of the total items in the database, the algorithm will be disabled. Up to now, many efforts in improving Grover’s origi nal algorithm have been done. Boyer et al. have given analytical expressions for the amplitude of the states in Grover’s search algorithm and tight bounds on the algo rithm [4]. Zalka has improved these tight bounds and showed that Grover’s algorithm is optimal [5]. Biron et al. generalized Grover’s algorithm to an arbitrarily dis tributed initial state [6]. Pati recast the algorithm in geo metric language and studied the bounds on the algorithm [7]. Ozhigov showed that quantum search can be further speeded up by a factor of 2 by parallelism [8]. Gin grich et al. also generalized Grover’s algorithm with par allelism with improvement [9]. The Grover’s original algorithm consists of inversion of the amplitude in the desired state and inversionaboutaverage operation [2]. In [10], Grover presented a general algorithm: Q UIU , where U is any unitary operation, U is the adjoint of U, 2II , 2II , is an initial state and is a desired state. When UU H , where H is the WalshHadamard trans formation, and 0 , the general algorithm becomes the original algorithm. Long extended Grover’s algo rithm [11]. In Long’s algorithm, and are ex pressed as 1II e i and i 1 Ie , respectively. When π , Long’s algo mes Grover’s original algorithm. Li et al. pro posed that U in Long’s algorithm can be replaced by any unitary operation V [12,13]. Biham generalized the Grover’s algorithm to deal with an arbitrary pure initial state and an arbitrary mixed initial state [14,15]. In [16], Grover presented the new algorithm by replacing the selective inversions by selective phase shifts of rithm beco π3.
P. C. LI ET AL. 44 al sJust like classicearch algorithms the algorithm has a fixed point in statespace toward which it preferentially converges. Li et al. studied the changes of the approxi mation error in the fixedpoint search algorithm obtained by replacing equal phase shifts of π3 by different phahifts [17]. se s The methods mentioned above cannot solve the prob lem that the algorithm efficiencies decrease as the marked items increase. In this paper, we study the phase matching in Grover’s algorithm, and propose an adaptive matching, namely, f , where is the fraction of marked items, and f is the polynomial for . With application of the new phase matching, when is a rational number in range 358 to 1/4, the probability of getting correct results is equal to 1 with two Grover iterations, and when is greater than 1/4, the probability of getting correct results is equal to 1 with only one Grover iteration. This paper is organized as follows: In Section 2, we introduce Grover’s algorithm and its drawbacks. Section 3 is used to propose an adaptive phase matching with the higher success probability. Section 4 gives an example to verify the validity of new phase matching. Section 5 summarizes the whole paper. 2. Grover’s Algorithm and Its Problem 2.1. Grover’s Algorithm Summary Suppose we wish to search through a search space of N elements. Rather than search the elements directly, we concentrate on the index to those elements, which is just a number in range 0 to . For convenience we as sume , so the index can be stored in n qubits, and that the search problem has exactly M solutions, with 1N 2n N 1 N . The algorithm begins with the state 0n . The Walshhadamard transform is used to put the state 0n in the equal superposition state, 1 1N 0x N (1) The Grover quantum search algorithm then consists of repeated application of a quantum subroutine, know as the Grover iteration or Grover operator, which we denote G. The Grover iteration may be broken up into four steps. 1) Apply the oracle O. The oracle is a unitary operator defined by its action on the computational basis O qxqfx (2) where is the index register, denotes addition modulo 2, and the oracle qubit q is a single qubit which is flipped if , and is unchanged other wise. 1fx 2) Applying the WalshHadamard transformn . 3) Perform a conditional phase shift, with every com putational basis state except 0 receiving a phase shift of –1, 0 1x x . 4) Applying the WalshHadamard transformn . It is useful to note that the combined effect of steps 2, 3, and 4 is 20 02 nn IH I (3) where is the equally weighted superposition of states, (1). Thus the Grover iteration, G, may be written as 2GI O. Let N , and CI(x) denote the integer closest to the real number x, where by convention we round halves down. Then repeating the Grover iteration arc cos CI 2arcsin R (4) times rotates to within an angle arc sinπ4 of a superposition of marked states [18]. Observation of the state in the computational basis then yields a solution to the search problem with probability at least onehalf. 2.2. Grover’s Algorithm Success Probability In fact, the Grover iteration can be regarded as a rotation in the twodimensional space spanned by the starting vector and the state consisting of a uniform super position of solutions to the search problem. Let represent a normalized states of a sum over all which are not solutions to the search problem, and represent a normalized states of a sum over all which are solutions to the search problem. Simple algebra shows that the initial state may be reexpresses as cos sintt (5) where arc sint . After R Grover iterations, the initial state is taken to cos21arc sin sin21arcsin R GR R (6) Hence, the success probability is sin 221arcsinPR (7) The curve of P is shown in Figure 1. 2.3. The Drawback of Grover’s Algorithm It is easy to deduce from Equation (4) and Equation (7) Copyright © 2011 SciRes. JQIS
45 P. C. LI ET AL. Figure 1. The success probability of Grover’s algorithm. that when 35 80.14645, P decreases rap idly. When 0.146451 4, P inceases rapidly. When r 14 12, P decreases rapidly. When 12, 0R, P there is , and the algorithm is disabled. Hence, the Grover's algorithm is no longer useful when 14 . The reason for the problem is that the two phase rota tions in Grover iteration are fully equivalent in both am plitude and direction, namely . According to Ref. [18], the result of such phase rotations is that, for the one Grover iteration, the phase of the π increases 2arcsin radians, and that rotating through at least arc cos radians takes the to . When 35 ,1 8 , there are only 1 1 4 and 2 35 8 make R an inte ger, namely, 1 1 1 arccos 1, 2arcsin R 2 2 2 arccos 2 2arcsin R . 3. The Adaptive Phase Matching for Grover’s Algorithm 3.1. The Adaptive Phase Matching The two phase shift operators in the Grover’s algorithm may be generally expressed as follows 1 1e M i mm m UI (8) 1e e i V i I (9) In the Grover’s original algorithm, there is π . According to the postulates of quantum mechanics [18], the evolution of a closed quantum system is described by a unitary transformation. So as far as the unitarity of op erators described by Equation (8) and Equation (9) is concerned, we have the following conclusions. Theorem 1 The operators described by Equation (8) and Equation (9) are unitary. Proof 1 U1e M i m I 11 2 1 2e e 1e1e MM ii mm M ii m UU I Hence, the operator described by Eqaution (8) is uni tary. 1 1e e 1e 1e ee2 M ii m ii ii VI VV I Hence, the operator described by Equation (9) is uni tary. For the matching of and , we propose an adap tive phase matching described by Theorem 2. Theorem 2 1) When 14 1 and 21 arc cos2 , the success probability 1P can be obtained after only one iteration. 2) When 35 1 84 and 35 arc cos14 , the success probability 1 can be obtained after only two iterations. Proof 1) For described by Equation (1), applying one Grover iteration gives 13 1 jk UVA xB x N where 1 0 eee NM i ii j MN M 1 0 ee1 Miii k BNM Me Let ee1pNM Me iii , the success probability P is equal to 2 3.Mp When N, Copyright © 2011 SciRes. JQIS
P. C. LI ET AL. 46 using some simple algebra gives 32 812 4 32 32 8124cos48 5. cos When 212 , namely, arc cos212 ， 2 32 32 max 32 812 4 485 1 43 4 PP . From cos 1 , the range 14 1 may be ob tained. 2) Reapplying one Grover iteration to 1 gives 21 5 1 jk UVA xB x N where 1 0 1 0 22 1e e 11e1e 1e e 11e1e eee eeee NM ii j ii Mii k i i ii ii ii ANC NMCM D BND i DNM C CM NM DNM M D Let 1e e11e 1 ii i i pNDM NMe C the success probability P is equal to 2 5 Mp N. Where , use some simple algebra gives 5445433 54322 5432 5432 16 16cos64 11248cos 9624018844cos 6420823210012cos 1664925613 . P where 35 cos1 4 , max 1PP . From cos 1 , the range 358 1 may be obtained. Taking into account the only iteration is needed when 14 1 , hence, the range for takes the form 358 1 4, and the adaptive phase matching takes the form arc cos1354 . □ According to thorem 2, applying the adaptive phase matching, the Equation (8) and Equation (9) can be re expressed as follows 1 1e M i m UI (10) V1e e iI i (11) On the basis of the adaptive phase matching, the suc cess probability curve is shown in Figure 2. 3.2. The Algorithm Description Based on the Adaptive Phase Matching According to , we divide the search process into three cases. 1) When 035 8, the original phase matching is applied. 2) When 358 1 4 create the phase of , the adaptive phase matching is applied. The search process can be described as follows: Step 1 Applying Equation (10) to the marked states rotate arc cos4354 radians, namely, 1U . Step 2 Applying Equation (11) to rotate the system superposition state 1 to 1 , namely, 11 V 1 VU . Step 3 Reapplying Equation (10) to 1 , namely, 2 1 U . Step 4 Reapplying Equation (11) to 2 , namely, 2 21 VVU . Step 5 Measuring 2 . 3) When 14 1 , the adaptive phase matching is applied. The search process can be described as fol lows: Figure 2. Comparison of success probability curves between Grover’s original algorithm and improved ones, where 1arc cos212, 2arc cos1354. Copyright © 2011 SciRes. JQIS
P. C. LI ET AL. 47 Step 1 Applying Equation (10) to create the phase o the marked states rotate f arc cos212 Te 2. The mbers anes. Serial bers Marked states radians, namely, 1U . Step 2 Applying Equation superposition stat (11) to rotate the system e 1 to 1, namely, 11 V VU . Step 3 Measuring 1 . 4. Searching Example ss whose serial numbers are range 0 to 31. 1) The search targets are the students There are 32 students in a cla in whose serial number satisfies CI533 ,nk where 0, 1,, 18k. The target serial numbers and marked states are shown in Table 1 . 2) are the serial number satisfies 92,nk where 0, 1,2,3k. The target serial numbers and marked states are shown in Table 2. wo searches, 32n The search targets In these t students whose , using 5 qubits can store all serial numbers. The initial state of the is ex erial numbers and marked states. pressed as follows Table 1. The target s k Serial numbers Marked states 0 1 00001 1 3 00011 2 4 00100 3 6 00110 4 8 01000 5 9 01001 6 11 01011 7 13 01101 8 14 01110 9 16 10000 abltarget serial nud marked stat k num 0 2 00010 01011 1 11 2 20 10100 3 29 11101 101 31 42 1) In this search, 19 32MN . According to eorem 2, applyingth arc cos212 arc cos3 19 correct to this search, the probability of getting results is equal to 1 only one Grover iteration. Th described as foe search process can bellows 10 18 10010 11 19 10011 12 21 10101 13 23 10111 14 24 11000 15 26 11010 16 28 11100 17 29 11101 18 31 11111 1 11 , 1, 1 e,1,e,e,1,e,1,e,e,1,e, 32 1,e,e,1,e,1,e,e,1,e 1e e ,,,,,,,,,,, 1 32 32 i iiiiiii ii i ii i ii I I ababba b abb a ,,,,, ,,,,,,,,,,,,,,, babba babbababbababbab where 1 1e 1,e,1,e,e ,1,e ,1,e,e M i mm m iiiii 19 ee60, ii a 19e 13e26 ii b 51232 32 1919 i . The probability of finding the marked states is given as follows 2 22 151232 32 19 1. 19 19 32 32 P matching, as For the original phase 19 320.5 , gure 1 is P the success probability, according to Fi . ds rapidly In fact, here, the success probability descen after applying a Grover iteration, which is described as follows 1 1 2 M mm m I 1, 1,1, 1, 1,1, 1,1, 1, 1,1, 1 1,1,1,1,1,1,1,1,1,1,1, 32 1, 1,1,1, 1,1, 1, 1,1,1 Copyright © 2011 SciRes. JQIS
P. C. LI ET AL. 48 11 2 ,,,,,,,,,,,,,,,, 1 , ,, ,,,,,,,, ,,,,, 32 32 I ababbababbababba babbababbababbab where 2) In this search, 11a , 5b. 18MN . According to theo rem 2, applying arc cos255 arc cos255 getting correct results is to this search, the probability of equal to 1 after only two Grover iterations. The search process can be described as follows 1 i 1 11 1e ,,,,,,,,,,,,,,,, 1 ,,,,,,,,,, 32 32 M mm ii I aabaaaaaaaabaaaa aaaabaaaaaa ,,,,,aabaa where 1, 1,e, 1, 1, 1, 1, 1, 1, 1, 1,e, 1, 1, 1, 1, 1 321, 1, 1, 1,e, 1, 1, 1, 1, 1, 1, 1, 1,e, 1, 1, 1e e m ii ii I 4e e24 ii a , 28 2e4e ii b . 21 1 1e ,,,,,,,,,,,,,,,, 1 ,,,,,,,,,,,,,,, 32 32 M i mm m I aacaaaaaaaacaaaa aaaacaaaaaaaacaa where , 4e e24 ii a 2 28 2e14 ii ce . 22 2 1ee ,,,,,,,,,,,,,,,, 1 ,,,,,,,,,,,,,,, 32 320 ii ddf ddddddddf dddd ddddf ddddddddf dd I where 22 16 ee320 ee3520 ii ii d , 2ii ii 2 16e448e 134112e2016 5124545120544.i The probability of finding the marked states is given as follows 4ef 22 22 2 512 445451 205441 32 32 P For the original phase matching, π , the mber of iterations is nu arc cosarc cos1 8 R 2 2arcsin(1 8) 2arcsin The search process can be described as follows 1 1 1, 1, 1, 1 mm m 2 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1 32 M I 11 2 1, 1,5, 1,1, 1,1, 1, 1,1, 1,5, 1,1, 1,1, 1 1, 1,1, 1,5, 1,1, 1, 1,1, 1,1, 1,5, 232 1, 1 I 21 1 2 1, 1,5, 1, 1, 1, 1, 1, 1, 1, 1,5, 1, 1, 1, 1, 1 1, 1, 1, 1,5, 1, 1, 1, 1, 1, 1,1, 1,5, 1, 1 232 M mm m I 22 2 ,,,,,,,,,,,,,,,, 1 ,,,,,,,,,,,,,,, 432 I aabaaaaaaaabaaaa aaaabaaaaaaaabaa 1,a 11b . where 2 11 4 0.9453125. 432 P 5. Conclusions An adaptive phase matching in Grover's algorithm is d. Witpplication of the new phase matching, fraction ofarked items is greater than proposeh a when the m 35 equal 8, the probability of getting correct results is to 1 after at most two Grover iterations. The valid y of the new phase matching is verified by two search esearch Foundations of Heilongjiang Provin rant No. 11551015). . References it examples. 6. Acknowledgements This paper was supported by National Natural Science Foundation of China (Grant No. 61170132), Chinese Po stdoctoral Science Foundation (Grant Nos.20090460864 and 201003405), Heilongjiang Province Postdoctoral Science Foundation of China (Grant No. LBHZ09289), Scientific R cial Education Department (G 7 [1] P. W. Shor, “Algorithms for Quantum Computation: Dis crete Logarithms and Factoring,” Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 2022 November 1994, pp. 124134. doi:10.1109/SFCS.1994.365700 [2] L. K. Grover, “A Fast Quantum Mechanical Algorithm Copyright © 2011 SciRes. JQIS
P. C. LI ET AL. Copyright © 2011 SciRes. JQIS 49 ACM Symposium on the Theory of Computing, 1996, pp. ] L. K. Grover, “Quantum Mechanics Helps in Searching for Database Search,” Proceedings of the 28th Annual 212221. [3 for a Needle in a Haystack,” Physical Review Letters, Vol. 79, No. 2, 1997, pp. 325328. doi:10.1103/PhysRevLett.79.325 [4] M. Boyer, G. Brassard, P. HØyer and A. Tapp Bounds on Quantum Searching,” , “Tight Fortschritte Der Physik, Vol. 46, No. 45, 1998, pp. 493505. doi:10.1002/(SICI)15213978(199806)46:4/5<493::AID PROP493>3.0.CO;2P [5] C. Zalka, “Grover’s Quantum Searching Algorithm Is Optimal,” Physical Review A, Vol. 60, No. 4, 1999, pp. 27462751. doi:10.1103/PhysRevA.60.2746 [6] D. Biron, O. Biham, E. Biham, “Generalized Grover Search Algorithm M. Grassl and D. A. Lidar for Arbitrar rithm and Bounds of Iterated Quantum Search by Generalized sing Any Transformation,” Physical Review Le , y Ini tial Amplitude Distribution,” quantph/9801066, 1998, pp. 18. [7] A. K. Pati, “Fast Quantum Search Algo on It,” quantph/9807067, 1998, pp. 14. [8] Y. Ozhigov, “Speedup Parallel Performance,” quantph/9904039, 1999, pp. 1 21. [9] R. Gingrich, C. P. Williams and N. Cerfm, “ Quantum Search with Parallelism,” quantph/9904039, 1999, pp. 114. [10] L. K. Grover, “Quantum Computers Can Search Rapidly by Utters, Vol. 80, No. 19, 1998, pp. 43294332. 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. 2734. doi:10.1016/S03759601(99)006313 [12] D. F. Li and X. X. Li, “More General Quantu Algorithm Q = –IVIU and the Pr m Search ecise Formula for the γ τ Amplitude and the Nonsyssetric Effects of Different Rotating Angles,” Physics Letters A, Vol. 287, No. 56, 2001, pp. 304316. doi:10.1016/S03759601(01)004984 [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. 12791287. doi:10.1007/s112320050159x Grover’s Quantum [14] E. Biham, O. Biham and D. Birom, “ Search Algorithm for an Arbitrary Initial Amplitude Dis tribution,” Physical Review A, Vol. 60, No. 4, 1999, pp. 27422745. doi:10.1103/PhysRevA.60.2742 [15] E. Biham and D. Kenigsberg, “Grover’s Quantum Search . Press, Algorithm for an Arbitrary Initial Mixed State,” Physical Review A, Vol. 66, No. 6, 2002, pp. 14. [16] L. K. Grover, “FixedPoint Quantum Search,” Physical Review Letters, Vol. 95, No. 15, 2005, pp. 14 [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. 18. [18] M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information,” Cambridge University Cambridge, 2000, pp. 248255.
