Integer Factorization by Quantum Measurements
- URL: http://arxiv.org/abs/2309.10757v1
- Date: Tue, 19 Sep 2023 17:00:01 GMT
- Title: Integer Factorization by Quantum Measurements
- Authors: Giuseppe Mussardo and Andrea Trombettoni
- Abstract summary: Quantum algorithms are at the heart of the ongoing efforts to use quantum mechanics to solve computational problems unsolvable on classical computers.
Among the known quantum algorithms, a special role is played by the Shor algorithm, i.e. a quantum-time algorithm for integer factorization.
Here we present a different algorithm for integer factorization based on another genuine quantum property: quantum measurement.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
Err
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.