Sharp probability estimates for Shor's order-finding algorithm
Paul Bourdon, H. T. Williams · 2007
Abstract: Let N be a positive integer, let b < N be a positive integer relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor’s original description of his order-finding algorithm. We prove that when Shor’s algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of r exceeds.7 whenever N ≥ 2 11 and r ≥ 40, and we establish that.7736 is an asymptotic lower bound for P. When N is not a power of an odd prime, Gerjuoy has shown that P exceeds 90 percent for N and r sufficiently large. We give easily checked conditions on N and r for this 90 percent threshold to hold, and we establish an asymptotic lower bound for P of 2Si(4π)/π ≈.9499 in this situation. More generally, for any nonnegative integer q, we show that when QC(q) is a quantum computer whose input register has q more qubits than does QC, and Shor’s algorithm is run on QC(q), then an asymptotic lower bound on P is 2Si(2 q+2 π)/π (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified. 1