Decoherence in Grover search algorithm

Grover search algorithm provides a quadratic speedup over all classical algorithms for unstructured data search. The origin of this quantum advantage has been explored and studied from various angles. In this work, we investigate this issue from the perspective of decoherence induced by the quantum channel associated to Grover search algorithm. We establish a complementary relation between coherence and success probability for the generalized Grover search algorithm with the register initialized in arbitrary pure state or pseudo-pure state. We provide an operational illustration of decoherence as success probability for the Grover search algorithm with unital noise and the register initialized in the maximal superposition state, which includes standard Grover search algorithm as a special case. To understand the dynamic of decoherence and its relation with success probability intuitively, we evaluate it for the Grover search algorithm with bit flip noise, phase flip noise, amplitude damping noise, and phase damping noise, and observe that both decoherence and success probability exhibit similar behaviors with the time of iterations.