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.
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.
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.
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 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 field of quantum computing has witnessed remarkable advancements in recent years, particularly in its potential applications to solve computationally hard problems such as integer factorization. a comparative analysis of quantum computing algorithms for integer factorization, focusing on their theoretical foundations, computational complexity, and practical implications. We review prominent algorithms such as Shor's algorithm, which leverages quantum parallelism and period finding to efficiently factor large composite integers, and compare them with classical factorization algorithms like the General Number Field Sieve (GNFS). Through a comprehensive examination of algorithmic strategies, runtime complexities, and quantum circuit implementations, we assess the relative strengths and limitations of quantum computing approaches for integer factorization. Furthermore, we discuss potential challenges and future research directions in harnessing the power of quantum computing to address cryptographic security and algorithmic complexity in the era of post-quantum cryptography.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.