) are illustrated in Fig. 19.7. We observe from the figure that G has rotated /s ) into a state 1/1/1), which is closer to the target state /w), hence a projection being increased by a factor 3 - 4/N (which is greater than unity if N > 2). Should a measurement in the state 1/1/1 be made through the observable S2, the probability of measuring dw would be (19.43) the upper limit on the right-hand side being obtained for large values of N. This result shows that in a single Grover iteration, the probability of finding the searched item through a single-shot measurement has been increased by about tenfold with respect to the classical case. It is now tempting to iterate the Grover operation as many times as required to rotate the system state closer to the target state /w), thus, increasing the probability of successfully measuring No to the required accuracy. For this, we must establish an iterative formula that defines the state 1/vk) after k Grover iterations, and the corresponding success probability. For the purpose of deriving the iteration formula, let us redefine the original eigenstate superposition in Eq. (19.34) by sorting out the /w) state from the series. Define first the 19.4 Grover quantum database search algorithm 41==s 1/1/2 4)=Us) Figure 19.7 Effect of the unitary operators U w and G = UsUw on initial state s), showing rotation by angles O and O' = O (respectively) corresponding to new states 1/s ) = Uw/s) and = (respectively). The cosine-projections of states |s) and 1/1/1 over the reference state /w) of the search algorithm are also indicated. state |u) spanning the hyperspace orthogonal to /w) according to (19.44) We can then write /s ) according to the superposition of its two orthogonal component states lu), /w): (19.45) where O is the rotation angle previously defined through cos O = 1 - 2/N (it is easily checked that cos 0/2=1 - 1/N). It is then an elementary (albeit nontrivial) exercise to show that k Grover iterations result in the state Gks)=(GG..G)k timess) (19.46) This result shows that 