|
related topics |
{algorithm, log, probability} |
{let, theorem, proof} |
{cos, sin, state} |
{equation, function, exp} |
|
Sharp probability estimates for Shor's order-finding algorithm
P. S. Bourdon, H. T. Williams
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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0607148
- categories:
- quant-ph
- comments:
- 33 pages, 2 figures. Revised: minor errors corrected, exposition
improved, submitted version
- arxiv_id:
- quant-ph/0607148
- created:
- 2006-07-21
- updated:
- 2006-09-03
Full article ▸
|
|
related documents |
0410042v1 |
0304131v1 |
0010034v1 |
0403140v2 |
9907020v2 |
0207131v1 |
9903071v1 |
0511272v1 |
0505007v3 |
9802040v2 |
0302022v1 |
0201152v1 |
9905026v1 |
0008059v3 |
0504067v3 |
0210077v1 |
0206089v2 |
0612089v3 |
0303175v1 |
0408150v2 |
0610235v2 |
0212096v1 |
0609220v1 |
0510185v1 |
0504083v2 |
|