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