Sharp probability estimates for Shor's order-finding algorithm
| dc.creator | Bourdon, P. S. | |
| dc.creator | Williams, H. T. | |
| dc.date | 2006-07-21 | |
| dc.date | 2006-09-04 | |
| dc.date.accessioned | 2026-07-07T07:22:57Z | |
| dc.date.available | 2026-07-07T07:22:57Z | |
| dc.description | 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. | |
| dc.description | 33 pages, 2 figures. Revised: minor errors corrected, exposition improved, submitted version | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0607148 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0607148 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/115844 | |
| dc.subject | Quantum Physics | |
| dc.title | Sharp probability estimates for Shor's order-finding algorithm | |
| dc.type | text |