Quantum Simulation of the Factorization Problem

Abstract

Feynman's prescription for a quantum simulator was to find a hamitonian for a system that could serve as a computer. Pólya and Hilbert conjecture was to demonstrate Riemann's hypothesis through the spectral decomposition of hermitian operators. Here we study the problem of decomposing a number into its prime factors, $N=xy$, using such a simulator. First, we derive the hamiltonian of the physical system that simulate a new arithmetic function, formulated for the factorization problem, that represents the energy of the computer. This function rests alone on the primes below $\sqrt{N}$. We exactly solve the spectrum of the quantum system without resorting to any external ad-hoc conditions, also showing that it obtains, for $x\ll \sqrt{N}$, a prediction of the prime counting function that is almost identical to Riemann's $R(x)$ function. It has no counterpart in analytic number theory and its derivation is a consequence of the quantum theory of the simulator alone.

10 pages, 12 figures. Accepted for publication in Physical Review Letters

References in corpus (1)

• Physics of the Riemann Hypothesis

Cited by in corpus (1)

• Quantum simulation of the integer factorization problem: Bell states in a Penning trap