A refinement of Shor's Algorithm for determining order is introduced, which determines a divisor of the order after any one run of a quantum computer with almost absolute certainty. The information garnered from each run is accumulated to determine the order, and for any k greater than 1, there is a guaranteed minimum positive probability that the order will be determined after at most k runs. The probability of determination of the order after at most k runs exponentially approaches a value negligibly less than one, so that the accumulated information determines the order with almost absolute certainty. The probability of determining the order after at most two runs is more than 60%, and the probability of determining the order after at most four runs is more than 90%.
Let N be a (large) positive integer, let b be an integer satisfying 1< b < N that is 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. In this paper, we analyze the probability that a single run of the quantum component of the algorithm yields useful information---a nontrivial divisor of the order sought. 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 \ge 2^{11} and r\ge 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 2\Si(4\pi)/\pi ~0.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\Si(2^{q+2}\pi)/\pi (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.
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.
We prove a lower bound on the probability of Shor’s order-finding algorithm successfully recovering the order r in a single run. The bound implies that by performing two limited searches in the classical post-processing part of the algorithm, a high success probability can be guaranteed, for any r , without re-running the quantum part or increasing the exponent length compared to Shor. Asymptotically, in the limit as r tends to infinity, the probability of successfully recovering r in a single run tends to one. Already for moderate r , a high success probability exceeding e.g. 1 - 10 -4 can be guaranteed. As corollaries, we prove analogous results for the probability of completely factoring any integer N in a single run of the order-finding algorithm.
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) the precise sense in which a quantum computer employing Shor's algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer can. It is made apparent that factoring
N generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm, the quantum part of which is to estimate
s/r, where
r is the ``order" and
s is some natural number that less than
r. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of
s/r.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly
L/2 qubits for factoring an
L-bit integer and reduces the circuit depth of each computer.
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.