# Quantum simulator offers faster route for prime factorization

##### April 10, 2018 by Lisa Zyga, Phys.org report

Factoring very large numbers into their prime "building blocks" is extremely difficult for classical computers, and this difficulty underlies the security of many cryptographic algorithms. While it's easy to factor the number 20 as the product of the primes 2 x 2 x 5, for example, factoring larger numbers becomes exponentially more difficult when using classical factoring algorithms.

In a new paper published in Physical Review A, physicists Jose Luis Rosales and Vicente Martin have developed a method that may make it much easier to factor very large numbers that are known to have exactly two prime factors. The new method determines the probability that any prime is one of the two prime factors of a given number. After determining these odds, the most likely prime factor candidates can be tested first, allowing for the prime factors to be identified much more quickly than before.

"The theory shows not only where the primes are located, but also the probability for a prime to be a factor of a given number," Rosales told Phys.org. "Of course, this has implications in cryptography because [the cryptosystem] RSA ignores this regularity."

One of the interesting things about the new method is that it doesn't use any kind of computer, either classical or . Instead it involves a physical quantum system—a ""—that, when encoded with the number to factor, exhibits a of energy values that is equivalent to the probability distribution of the prime factor candidates of the encoded number.

"Our aim is to develop a new quantum theory of the factorization problem using a quantum simulator," Rosales said. "Our approach has discovered a property with no classical analogy in number theory. Every pair of primes that solve the problem re-arrange themselves to form a regular pattern: the band spectrum of the quantum simulator."

The general idea behind the quantum simulator is something called the "factorization ensemble," which the researchers introduced previously. It is based on the idea that the primes are ordered from least to greatest (for example, 2 is the first prime, 3 is the second prime, and 101 is the 26th prime). It's also possible to take the square root of any number, and then compare the result to the closest prime. For example, the square root of 27 is a little more than 5, which is the third prime. By the definition of a factorization ensemble, this means that 27 belongs to the factorization ensemble of 3.

The physicists then showed that they could transform the factorization ensemble function into a function from quantum physics (the inverted harmonic-oscillator function). After many more steps, they eventually showed that the predicted energy spectrum of a quantum system corresponds to the distribution of primes in the factorization ensemble of a number. From this information, the researchers can determine the probability that a prime is a factor of that number. To test the validity of their method, the physicists tested certain numbers and compared their results to the actual distributions obtained using tables, and found very similar distributions.

The physicists theoretically demonstrated that the proposed quantum simulator can factor numbers that are many orders of magnitude larger than those that have been factored with quantum computers. In their paper, they report the results of using their method to determine the probability distribution of the prime factors of a number with 24 digits. Further, the method does this with far fewer resources than required by classical factoring algorithms.

"In quantum theory, the algorithmic complexity is only polynomial with the number of bits of the number to factorize," Rosales said. "As a matter of fact, our first results seem to confirm that the simulator requires only (log√N)3 quantum states to reproduce its spectrum of energies, a very encouraging result."

One final point of interest is that the new method has strong connections to the Riemann hypothesis, which, if true, would suggest that the prime numbers are distributed in a predictable way—in the same way as the distribution of the zeros of the Riemann-zeta function. Proving (or disproving) the Riemann hypothesis is one of the greatest unsolved problems in mathematics, and one of the Clay Mathematics Institute's Millennium Prize Problems.

"The primes should behave as quantum numbers if Hilbert-Polya's conjecture applies," Rosales said, referring to the long-standing approach to proving the Riemann hypothesis.

Going forward, the researchers are currently working on the experimental implementation of the quantum simulator by using two entangled particles in a Penning trap.

"The fully quantum treatment of the simulator would require quantum optical analysis of the interactions of photons with two (or more) entangled ions in a Penning trap," Rosales said. "This part of the program is yet in development. The aim is to build a quantum factoring experimentally. If successfully implemented, numbers many orders of magnitude bigger than those available for its quantum processing using Shor's algorithm will be factorized and, as a by-product, the Hilbert-Polya conjecture will be tested experimentally."

Explore further: Quantum physics offers new way to factor numbers

More information: Jose Luis Rosales and Vicente Martin. "Quantum simulation of the integer factorization problem: Bell states in a Penning trap." Physical Review A. DOI: 10.1103/PhysRevA.97.032325. Also at: arXiv:1704.03174 [quant-ph]

## Related Stories

#### Quantum physics offers new way to factor numbers

November 28, 2016

(Phys.org)—Any number can, in theory, be written as the product of prime numbers. For small numbers, this is easy (for example, the prime factors of 12 are 2, 2, and 3), but for large numbers, prime factorization becomes ...

#### New largest number factored on a quantum device is 56,153

November 28, 2014

(Phys.org)—Researchers have set a new record for the quantum factorization of the largest number to date, 56,153, smashing the previous record of 143 that was set in 2012. They have shown that the exact same room-temperature ...

#### Researchers develop quantum computer algorithm for counting prime numbers

March 26, 2013

(Phys.org) —Two math and physics researchers from the University's of Barcelona and Madrid respectively have developed an algorithm to count prime numbers using a quantum computer. José Latorre and Germán Sierra describe ...

#### A newly discovered prime number makes its debut

January 31, 2018

On December 26, 2017, J. Pace, G. Woltman, S. Kurowski, A. Blosser, and their co-authors announced the discovery of a new prime number: 2⁷⁷²³²⁹¹⁷-1. It's an excellent opportunity to take a small tour through the ...

#### Why prime numbers still fascinate mathematicians, 2,300 years later

April 3, 2018

On March 20, American-Canadian mathematician Robert Langlands received the Abel Prize, celebrating lifetime achievement in mathematics. Langlands' research demonstrated how concepts from geometry, algebra and analysis could ...

#### 143 is largest number yet to be factored by a quantum algorithm

April 11, 2012

(Phys.org) -- While factoring an integer is a simple problem when the integer is small, the complexity of factorization greatly increases as the integer increases. When the integer grows to more than 100,000 or so digits, ...

## Recommended for you

#### Scientists provide first-ever views of elusive energy explosion

November 15, 2018

Researchers at the University of New Hampshire have captured a difficult-to-view singular event involving "magnetic reconnection"—the process by which sparse particles and energy around Earth collide producing a quick but ...

#### Bursting bubbles launch bacteria from water to air

November 15, 2018

Wherever there's water, there's bound to be bubbles floating at the surface. From standing puddles, lakes, and streams, to swimming pools, hot tubs, public fountains, and toilets, bubbles are ubiquitous, indoors and out.

#### Terahertz laser pulses amplify optical phonons in solids

November 15, 2018

A study led by scientists of the Max Planck Institute for the Structure and Dynamics of Matter (MPSD) at the Center for Free-Electron Laser Science in Hamburg/Germany presents evidence of the amplification of optical phonons ...

#### Research uncovers the spontaneous polarization of novel ultrathin materials

November 15, 2018

Many materials exhibit new properties when in the form of thin films composed of just a few atomic layers. Most people are familiar with graphene, the two-dimensional form of graphite, but thin film versions of other materials ...

#### Designer emulsions

November 15, 2018

ETH material researchers are developing a method with which they can coat droplets with controlled interfacial composition and coverage on demand in an emulsion in order to stabilise them. In doing so they are fulfilling ...

#### Quantum science turns social

November 15, 2018

Researchers in a lab at Aarhus University have developed a versatile remote gaming interface that allowed external experts as well as hundreds of citizen scientists all over the world to optimize a quantum gas experiment ...