Coherence and decoherence in generalized Shor’s algorithm

Quantum coherence constitutes a fundamental physical mechanism essential to the study of quantum algorithms. We study coherence and decoherence in the generalized Shor’s algorithm where the register A is initialized in an arbitrary pure state, or the combined register AB is initialized in a pseudo-pure state, which encompasses the standard Shor’s algorithm as a special case. We derive both lower and upper bounds on the performance of the generalized Shor’s algorithm, and establish the relation between the probability of calculating the order r when register AB is initialized in a pseudo-pure state and that when register A is initialized in an arbitrary pure state. Moreover, we study coherence and decoherence in the noisy Shor’s algorithm and give a lower bound on the probability that we can calculate the order r.