k applications of the Grover operator results in the rotation of the state /s ) by an angle k0, as illustrated in Fig. 19.8. The probability p(w) of finding the state G*|s) in /w), and, hence, of measuring the eigenvalue Nw with the observable S2, is Quantum database search algorithms G3/s) (G2/S) Figure 19.8 Effect of successive applications (here from k= 1 to k=3) of the Grover operator G onto the initial state s), showing incremental rotations by angle O in the direction of state /w). given by (19.47) The probability p(w) reaches a maximum for (19.48) (19.49) From the definition in Eq. (19.45), sin 0/2 = 1/ N , which for large N yields the approximation O 2 2/VN and, hence, the maximum number of iterations kmax: (19.50) Clearly, the Grover search algorithm must be stopped after reaching the number of iterations k = kmax, corresponding to the probability p(w) 2 1. Figure 19.9 shows plots of the probability p(w), a function of the number k of Grover iterations, from quantum database sizes N = 26=6 64toN=214=16384.Thanks to the VN dependence of kmax, it is seen that quantum databases as large as N 2 16 000 can successfully be searched with only Kmax ~ 100 Grover iterations, which represents a computation complexity in O(NN), to compare with O(N) in the classical case. Now that we are convinced of the benefits of the Grover algorithm, the next step is to analyze its quantum-circuit implementation. Consider first how the quantum database can be generated. In Section 19.2, concerning the Deutsch-Jozsa algorithm, we have 19.4 Grover quantum database search algorithm 1.024 2.048 4.096 8.192 16.384 number of measurements k Figure 19.9 Probability p(w) of finding the state in /w/ (or of measuring the eigenvalue 2w) as a function of the number k of Grover iterations, from quantum database sizes N = 26 = 64 (leftmost curve) to N = 2 14 = 16 384 (rightmost curve). established and used in Eq. (19.7) the property according to which (19.51) where Hon is the n-tensor application of the Hadamard gate H. For instance, we have, f