On the Quantum Simulation of the Factorization Problem

Research paper by Jose Luis Rosales, Vicente Martin

Indexed on: 19 Jan '16Published on: 19 Jan '16Published in: Quantum Physics


Feynman's prescription for a quantum computer was to find a Hamitonian for a system that could serve as a computer. Here we concentrate in a system to solve the problem of decomposing a large number $N$ into its prime factors. The spectrum of this computer is exactly calculated obtaining the factors of $N$ from the arithmetic function that represents the energy of the computer. As a corollary, in the semi-classical large $N$ limit, we compute a new prime counting asymptote $\pi(x|N)$, where $x$ is a candidate to factorize $N$, that has no counterpart in analytic number theory. This rises the conjecture that the quantum solution of factoring obtains prime numbers, thus reaching consistency with Euclid's unique factorization theorem: primes should be quantum numbers of a Feynman's factoring simulator.