Coherence and decoherence in generalized Shor's algorithm

Abstract

Quantum coherence constitutes a fundamental physical mechanism essential to the study of quantum algorithms. We study the coherence and decoherence in 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 the 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 the register $AB$ is initialized in a pseudo-pure state and the one when the register $A$ is initialized in an arbitrary pure state. Moreover, we study the coherence and decoherence in noisy Shor's algorithm and give the lower bound of the probability that we can calculate the order $r$.

arXiv comment24 pages, 2 figures