One of the most significant achievements of quantum information processing is the construction of the probabilistic algorithm providing factoring of numbers in polynomial time. However, properties of the classic algorithms assisting an operation of the quantum device have not been well investigated and rough estimates of their effectiveness have been put forth. This paper presents results of the numerical simulation of the quantum factorization algorithm for composite numbers, which have been formed as a product of exactly two factors. It was shown that average factorization efficiency significantly exceeds the commonly used bound. The presented results also provided strong evidence that there exists an internal structure in probability distribution of successful factorization.
One of the most significant achievements of quantum information processing is the construction of the probabilistic algorithm providing factoring of numbers in polynomial time. However, properties of the classic algorithms assisting an operation of the quantum device have not been well investigated and rough estimates of their effectiveness have been put forth. This paper presents results of the numerical simulation of the quantum factorization algorithm for composite numbers, which have been formed as a product of exactly two factors. It was shown that average factorization efficiency significantly exceeds the commonly used bound. The presented results also provided strong evidence that there exists an internal structure in probability distribution of successful factorization.
The quantum algorithm for factorization is probably the most famous one in quantum computation. The algorithm succeeds only when some random number with an even order relative to the number to be factorized is fed as the input to the quantum order finding algorithm. It is well-known that numbers with even orders are found with probability not less than 1/2. In consequence, quantum device has to be used many times in the course of the factorization process to amplify the success probability. However, the above-mentioned limit is a rough estimate. Presented theoretical analysis and numerical simulation prove that the probability of finding a parameter with an even order is significantly higher for many composite numbers. It immediately follows that so far, presented analyses of factorization efficiency are highly underestimated in terms of required number of quantum device usage.
The quantum factorization effectiveness is limited both by inherent randomness of the quantum measurement and requirement of special selection of parameters controlling behavior of classic algorithms supporting quantum device operation. However, only coarse bounds on probability of successful parameters selection have been published so far. The proof of an exact expression on factorization efficiency constitutes the main contribution of the paper. The proved expression simply relates Shor’s algorithm efficiency to properties of the factors forming the composite number.
The quantum factorization is probably the most famous algorithm in quantum computation. The algorithm succeeds only when some random number with an even order relative to factorized composite integer is fed as the input to the quantum order finding algorithm. Moreover, post processing of the quantum measurement recovers the correct order only for some subset of possible values. It is well known that numbers with even orders are found with probability not less than 1=2. However, numerical simulation proves that probability of such event exhibits grouping on some discrete levels above that limit. Thus, one may conclude that usage of the lowest estimate leads to underestimation of the successful factorization probability. The understanding of the observed grouping requires further research in that field.
One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we mention about the fundamentals of Shor's quantum algorithm illustrating a concrete example.
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.
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.