Physics – Quantum Physics
Scientific paper
2006-07-21
Physics
Quantum Physics
33 pages, 2 figures. Revised: minor errors corrected, exposition improved, submitted version
Scientific paper
Let N be a (large positive integer, let b > 1 be an 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 0.7 whenever N exceeds 2^{11}-1 and r exceeds 39, and we establish that 0.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 (2/Pi) Si(4Pi), about .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 (2/Pi) Si(2^(q+2) Pi) (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.
Bourdon Paul S.
Williams Thomas H.
No associations
LandOfFree
Sharp probability estimates for Shor's order-finding algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sharp probability estimates for Shor's order-finding algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp probability estimates for Shor's order-finding algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-169380