Analysis of generalized Grover quantum search algorithms using recursion equations
Eli Biham, Ofer Biham, David Biron, Markus Grassl, Daniel A. Lidar, Daniel Shapira · Physical Review A · 2000
The recursion equation analysis of Grover's quantum search algorithm presented by Biham et al. [Phys. Rev. A 60, 2742 (1999)] is generalized. It is applied to the large class of Grover-type algorithms in which the Hadamard transform is replaced by any other unitary transformation and the phase inversion is replaced by a rotation by an arbitrary angle. The time evolution of the amplitudes of the marked and unmarked states, for any initial complex amplitude distribution, is expressed using first-order linear difference equations. These equations are solved exactly. The solution provides the number of iterations T after which the probability of finding a marked state upon measurement is the highest, as well as the value of this probability, ${P}_{\mathrm{max}}.$ Both T and ${P}_{\mathrm{max}}$ are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments.