Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Information and Computation

Probability estimates for Shor's algorithm

Paul Bourdon, H. T. Williams

Published Jul 1, 2007• 3 citations
Publisher

Abstract

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.

DOI
10.26421/qic7.5-6-7

Related papers

Sharp probability estimates for Shor's order-finding algorithm

Paul Bourdon, H. T. Williams

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.

arXiv:quant-ph/0607148•Quantum Information and Computation•Jul 21, 2006•12 citations

How to detect whether Shor’s algorithm succeeds against large integers without a quantum computer

Daniel Chicayban Bastos, Luis Antônio Brasil Kowada

Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.

Procedia Computer Science•Jan 1, 2021•6 citations

On the Success Probability of Quantum Order Finding

Martin Ekerå

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.

arXiv:2201.07791•ACM Transactions on Quantum Computing•Mar 28, 2024•6 citations

A Refinement of Shor's Algorithm

D. S. McAnally

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%.

arXiv:quant-ph/0112055•Dec 9, 2001•11 citations

Large-Scale Simulation of Shor's Quantum Factoring Algorithm

Dennis Willsch, Madita Willsch, Fengping Jin +2 more

Shor's factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today's quantum computers only permit a study of Shor's algorithm for very small numbers. Here we show how large GPU-based supercomputers can be used to assess the performance of Shor's algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor's original factoring algorithm. While theoretical bounds suggest success probabilities of only 3-4 %, we find average success probabilities above 50 %, due to a high frequency of "lucky" cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor's quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor's algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549755813701 = 712321 * 771781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.

arXiv:2308.05047•Aug 9, 2023•1 citation

Large-Scale Simulation of Shor’s Quantum Factoring Algorithm

Dennis Willsch, Madita Willsch, Fengping Jin +2 more

Shor’s factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today’s quantum computers only permit a study of Shor’s algorithm for very small numbers. Here, we show how large GPU-based supercomputers can be used to assess the performance of Shor’s algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor’s original factoring algorithm. While theoretical bounds suggest success probabilities of only 3–4%, we find average success probabilities above 50%, due to a high frequency of “lucky” cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor’s quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor’s algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549,755,813,701 = 712,321 × 771,781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.

Mathematics•Oct 9, 2023•31 citations
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 rrr exceeds .7.7.7 whenever N \ge 2^{11} and r\ge 40, and we establish that .7736.7736.7736 is an asymptotic lower bound for PPP. When NNN is not a power of an odd prime, Gerjuoy has shown that PPP exceeds 90 percent for NNN and rrr 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 PPP of 2\Si(4\pi)/\pi ~0.9499 in this situation. More generally, for any nonnegative integer qqq, we show that when QC(q) is a quantum computer whose input register has qqq 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.
Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.
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.
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%.
Shor's factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today's quantum computers only permit a study of Shor's algorithm for very small numbers. Here we show how large GPU-based supercomputers can be used to assess the performance of Shor's algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor's original factoring algorithm. While theoretical bounds suggest success probabilities of only 3-4 %, we find average success probabilities above 50 %, due to a high frequency of "lucky" cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor's quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor's algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549755813701 = 712321 * 771781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.
Shor’s factoring algorithm is one of the most anticipated applications of quantum computing. However, the limited capabilities of today’s quantum computers only permit a study of Shor’s algorithm for very small numbers. Here, we show how large GPU-based supercomputers can be used to assess the performance of Shor’s algorithm for numbers that are out of reach for current and near-term quantum hardware. First, we study Shor’s original factoring algorithm. While theoretical bounds suggest success probabilities of only 3–4%, we find average success probabilities above 50%, due to a high frequency of “lucky” cases, defined as successful factorizations despite unmet sufficient conditions. Second, we investigate a powerful post-processing procedure, by which the success probability can be brought arbitrarily close to one, with only a single run of Shor’s quantum algorithm. Finally, we study the effectiveness of this post-processing procedure in the presence of typical errors in quantum processing hardware. We find that the quantum factoring algorithm exhibits a particular form of universality and resilience against the different types of errors. The largest semiprime that we have factored by executing Shor’s algorithm on a GPU-based supercomputer, without exploiting prior knowledge of the solution, is 549,755,813,701 = 712,321 × 771,781. We put forward the challenge of factoring, without oversimplification, a non-trivial semiprime larger than this number on any quantum computing device.