dorsal/arxiv
View SchemaSharp probability estimates for Shor's order-finding algorithm
| Authors | P. S. Bourdon, H. T. Williams |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0607148 |
| URL | https://arxiv.org/abs/quant-ph/0607148 |
Abstract
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.
{
"annotation_id": "be4a035f-8949-4bb6-af4a-c134df98be8c",
"date_created": "2026-03-02T18:02:27.552000Z",
"date_modified": "2026-03-02T18:02:27.552000Z",
"file_hash": "d1d0de2e0cd4d691edda80667ed01491f2fac81f2a602841793a6a793fdb4aef",
"private": false,
"record": {
"abstract": "Let N be a (large positive integer, let b \u003e 1 be an integer relatively prime\nto N, and let r be the order of b modulo N. Finally, let QC be a quantum\ncomputer whose input register has the size specified in Shor\u0027s original\ndescription of his order-finding algorithm. We prove that when Shor\u0027s algorithm\nis implemented on QC, then the probability P of obtaining a (nontrivial)\ndivisor of r exceeds 0.7 whenever N exceeds 2^{11}-1 and r exceeds 39, and we\nestablish that 0.7736 is an asymptotic lower bound for P. When N is not a power\nof an odd prime, Gerjuoy has shown that P exceeds 90 percent for N and r\nsufficiently large. We give easily checked conditions on N and r for this 90\npercent threshold to hold, and we establish an asymptotic lower bound for P of\n(2/Pi) Si(4Pi), about .9499, in this situation. More generally, for any\nnonnegative integer q, we show that when QC(q) is a quantum computer whose\ninput register has q more qubits than does QC, and Shor\u0027s algorithm is run on\nQC(q), then an asymptotic lower bound on P is (2/Pi) Si(2^(q+2) Pi) (if N is\nnot a power of an odd prime). Our arguments are elementary and our lower bounds\non P are carefully justified.",
"arxiv_id": "quant-ph/0607148",
"authors": [
"P. S. Bourdon",
"H. T. Williams"
],
"categories": [
"quant-ph"
],
"title": "Sharp probability estimates for Shor\u0027s order-finding algorithm",
"url": "https://arxiv.org/abs/quant-ph/0607148"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "28baa756-92d6-451e-aff4-c4b1b6d5cd95",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}