A sharper probability estimate for Shor's algorithm
Paul Bourdon, H. T. Williams · arXiv (Cornell University) · 2006
Abstract: Let N be a (large) positive integer, and let b < N be a positive integer relatively prime to N whose order modulo N is large. Let QC be a quantum computer whose input register has the size specified in Shor’s original description of his order-finding algorithm. We show that when Shor’s algorithm is implemented on QC, then the probability of obtaining a divisor of the order of b modulo N exceeds 70 percent. Typically, this probability has been estimated to be bounded below by 40 percent. 1