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 Processing

Closed-form formula on quantum factorization effectiveness

P. Zawadzki

Published Jan 25, 2012• 1 citation
Publisher

Abstract

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.

DOI
10.1007/s11128-012-0360-4

Related papers

A FINE ESTIMATE OF QUANTUM FACTORIZATION SUCCESS PROBABILITY

P. Zawadzki

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.

International Journal of Quantum Information•Dec 1, 2010•5 citations

Numerical Estimation of Efficiency of the Algorithms Assisting Quantum Factorization

Piotr Zawadzki

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.

International Journal of Applied Research on Information Technology and Computing•Jan 1, 2011•0 citations

Numerical estimation of the quantum factorization effectiveness

P. Zawadzki

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.

Theoretical and Applied Informatics•Jan 1, 2010•3 citations

Integer Factorization by Quantum Measurements

Giuseppe Mussardo, Andrea Trombettoni

Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on ordinary classical computers. Their common feature is the use of genuine quantum properties such as entanglement and superposition of states. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a polynomial-time quantum algorithm for integer factorization, with far reaching potential applications in several fields, such as cryptography. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement. In this new scheme, the factorization of the integer $N$ is achieved in a number of steps equal to the number $k$ of its prime factors, -- e.g., if $N$ is the product of two primes, two quantum measurements are enough, regardless of the number of digits $n$ of the number $N$. Since $k$ is the lower bound to the number of operations one can do to factorize a general integer, one sees that a quantum mechanical setup can saturate such a bound.

arXiv:2309.10757•Sep 19, 2023•2 citations

Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers

Gerjuoy, E

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.

•Nov 25, 2004•50 citations

Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers

Edward Gerjuoy

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.

arXiv:quant-ph/0411184•American Journal of Physics•May 13, 2005•76 citations
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 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 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.
Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on ordinary classical computers. Their common feature is the use of genuine quantum properties such as entanglement and superposition of states. Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a polynomial-time quantum algorithm for integer factorization, with far reaching potential applications in several fields, such as cryptography. Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement. In this new scheme, the factorization of the integer NNN is achieved in a number of steps equal to the number kkk of its prime factors, -- e.g., if NNN is the product of two primes, two quantum measurements are enough, regardless of the number of digits nnn of the number NNN. Since kkk is the lower bound to the number of operations one can do to factorize a general integer, one sees that a quantum mechanical setup can saturate such a bound.
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 NNN 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.
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.