Researchers introduced new concepts and arithmetic functions that could play a significant role in the quantum factorization problem. The Factorization Ensemble is the main one; it allows us to bind the hamiltonian of a quantum factoring simulator.
Although the researchers have not yet built a quantum simulator, they show that the prime factors of large numbers would correspond to the energy values of the simulator. Measuring the energy values would then give the solutions to a given factoring problem, suggesting that factoring large numbers into primes may not be as difficult as currently thought.
“The work opens a new avenue to factor numbers, but we do not yet know about its power,” Rosales told Phys.org. “It is very striking to find a completely new way to factor that comes directly from quantum physics. It does not demonstrate that factoring numbers is easy, but finding new ways to factor certainly does not add to the strength of algorithms based on its assumed complexity.”
For now, the researchers do not know the technical complexity of building such a device, or whether it would even be possible to factor very large numbers.
“We have shown that a quantum simulator able to factor numbers exists and, in principle, it could be built,” Martin said. “Whether the simulator is feasible with current technology in a way that it can factor numbers of the same size as the ones used in cryptography remains to be seen, but the avenue is now open. The prospect of building such a device before a quantum computer is built is something to be pondered seriously.”
Besides the potential for practical applications, the results are also interesting on a more fundamental level.
“In our opinion, the contributions of the paper have two sides: in pure mathematics and in applied cryptography,” Rosales said.
One of the most mathematically interesting aspects of the new work is that it involves redefining the factorization problem by introducing a new arithmetic function that could then be mapped onto the physics of the quantum simulator and correspond to the energy values. In a sense, the researchers are rewriting the math problem in terms of physics.
“The manuscript tries to bridge number theory with quantum physics,” Rosales said, noting that researchers have been trying to do this for several decades. “Nowadays with the development of quantum information and computation and the discovery of Shor’s algorithm, the connection seems more intriguing and important than ever.”
In the long-term, this type of investigation could ultimately lead to a quantum number theory—a theory of numbers that is based on physical quantum systems.
Feynman’s prescription for a quantum simulator was to find a hamiltonian for a system that could serve as a computer. P’olya 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 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≪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.
Arxiv – Quantum Simulation of the Factorization Problem
To develop a quantum number theory, what we need is a quantum system (at least a theoretical one) to able to reproduce the prime numbers,” Martin said. “In the paper, our take was to try to obtain a system able to factorize a number into its primes. The method is ‘analogue’ in the sense that it is not like Shor’s algorithm, which is programmable in a quantum computer following the gate model. Instead, it is the measurement of a carefully set quantum system that provides the answer.
“To carry out this program, we need to first devise an arithmetic formulation of the factorization problem that is amenable to be quantized. We have to find an arithmetic function, eventually related to a Hamiltonian, and set up the quantum-mechanical problem such that its solution corresponds to the solution of the factorization problem. In the work we succeeded in carrying out these ideas. We found the correct arithmetic function, defined the factorization set to bind the Hamiltonian and obtained the solution of the quantum-mechanical problem. To the best of our knowledge, this has not been achieved before, although ours was not the first attempt.
“As it is always done in physics, to validate the results, we have to prove its predictive capabilities, so we did predictions with them: obtained a factorization algorithm that is completely new, with no similitude to any other factorization algorithm that we know of, and thoroughly checked the statistics of the solution against the prime number theorem.
“The results left us really astounded. To demonstrate this, in the paper we show how the spectrum reproduces the prime counting function and is almost identical to the Riemann’s. This is obtained as a direct consequence of the quantum mechanical theory and has no counterpart in number theory. Carrying this to the extreme, this could be even considered the physics underlying the Riemann hypothesis [one of the most important open problems in number theory] in the sense that the Hamiltonian is naturally bounded, without any further assumptions.”
The researchers explain that, in this paper, they just hinted that the results have deeper mathematical implications, and they plan to further investigate these possibilities in the future. They are also looking into what it would take to build a quantum simulator.
Read more at: http://phys.org/news/2016-11-quantum-physics-factor.html#jCp
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.