Analysis of generalized Grover quantum search algorithms using recursion equations

作者：Biham E^*; Biham O; Biron D; Grassl M; Lidar DA; Shapira D

来源：Physical Review A, 2001, 63(1): 012310.

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 slate upon measurement is the highest, as well as the value of this probability, P-max. Both T and P-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.

• 出版日期2001-1