# Researchers develop quantum computer algorithm for counting prime numbers

##### March 26, 2013 by Bob Yirka report

(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 in their paper they've uploaded to the preprint server arXiv, their formula that uses spin states of quantum bits (qubits) to calculate the number of prime numbers below a given value.

Prime numbers are natural numbers that can only be divided evenly by themselves or 1—mathematcians have been wrestling since the time of to come up with a way to identify them, all to no avail. The only way to find one currently is to pick a number and see if it can be divided evenly. Because of that, few prime numbers were found until the advent of computers. Now, big computers can be run for months at a time to determine the next prime number past the one that is known.

In 1859, Bernhard Riemann came up with a formula that can be used to ascertain, given a single number, how many fall below it. The problem here however, is no one has been able to prove whether it is correct or not. Because it can't be proved true, researchers have been trying to prove it false by giving it numbers where all the primes below it have been identified. Thus far, such attempts have reached a number as high as 1024. Running the algorithm on a regular computer takes enormous amounts of time—trying X=1025, for example would likely take about nine months. In this new effort, the research duo from Spain has come up with an algorithm for doing the job on a quantum computer that takes advantage of the spin states of qubits.

The algorithm can't be run just yet however, because a quantum computer running it would have to be able to manipulate 80 qubits at a time, which is far bigger than anything that has been built thus far. Because quantum computers are still in their infancy, their designs are still , and because of that it's impossible to say for sure just how much faster such a computer could calculate Riemann's formula, but most would likely agree that the difference would be significant.

Explore further: The sum of digits of prime numbers is evenly distributed

Abstract
We propose a quantum circuit that creates a pure state corresponding to the quantum superposition of all prime numbers less than 2^n, where n is the number of qubits of the register. This Prime state can be built using Grover's algorithm, whose oracle is a quantum implementation of the classical Miller-Rabin primality test. The Prime state is highly entangled, and its entanglement measures encode number theoretical functions such as the distribution of twin primes or the Chebyshev bias. This algorithm can be further combined with the quantum Fourier transform to yield an estimate of the prime counting function, more efficiently than any classical algorithm and with an error below the bound that allows for the verification of the Riemann hypothesis. Arithmetic properties of prime numbers are then, in principle, amenable to experimental verifications on quantum systems.

via Newscientist

## Related Stories

#### The sum of digits of prime numbers is evenly distributed

May 12, 2010

(PhysOrg.com) -- On average, there are as many prime numbers for which the sum of decimal digits is even as prime numbers for which it is odd. This hypothesis, first made in 1968, has recently been proven by French researchers ...

#### Researchers conduct experimental implementation of quantum algorithm

January 12, 2012

(PhysOrg.com) -- Researchers at D-Wave Systems have carried out a calculation involving 84 qubits on an experimental quantum computer, giving some credence to the plausibility of true quantum computers being created that ...

#### Freezing liquids help to predict properties of prime numbers

May 3, 2012

(Phys.org) -- The same freezing which is responsible for transforming liquids into glasses can help to predict some patterns observed in prime numbers, according to a team of scientists from Queen Mary, University of London ...

#### Quantum computers could help search engines keep up with the Internet's growth

June 12, 2012

Most people don't think twice about how Internet search engines work. You type in a word or phrase, hit enter, and poof – a list of web pages pops up, organized by relevance.

#### Physicists demonstrate that 15=3x5 about half of the time

August 19, 2012

Computing prime factors may sound like an elementary math problem, but try it with a large number, say one that contains more than 600 digits, and the task becomes enormously challenging and impossibly time-consuming. Now, ...

#### University professor discovers largest prime number to date

February 6, 2013

(Phys.org)—Curtis Cooper, professor of math and computer science at the University of Central Missouri, has discovered the largest prime number to date, it's 257,885,161 – 1. It has 17 million digits and is also a Mersenne ...

## Recommended for you

#### Physicists propose first method to control a single quanta of energy

August 29, 2016

(Phys.org)—Physicists have proposed what they believe to be the first method to control the transport of energy at the level of single energy quanta (which are mostly phonons). They show that it's theoretically possible ...

#### Simple equation predicts force needed to push objects through granular and pasty materials

August 29, 2016

For those of you who take sandcastle building very seriously, listen up: MIT engineers now say you can trust a very simple equation to calculate the force required to push a shovel—and any other "intruder"— through sand. ...

#### Counting down to the new ampere

August 29, 2016

After it's all over, your lights will be just as bright, and your refrigerator just as cold. But very soon the ampere—the SI base unit of electrical current—will take on an entirely new identity, and NIST scientists are ...

#### Photographing sneezes at high speed may help find ways to reduce spread of disease

August 29, 2016

(Phys.org)—A team of researchers at MIT led by Lydia Bourouiba has discovered some new properties of sneeze clouds by photographing them with high speed cameras and then studying the footage. In their paper published in ...

#### Lab team uses pulsed ion beams to probe radiation defect dynamics in nuclear materials

August 29, 2016

Materials scientists at Lawrence Livermore National Laboratory (LLNL) have developed a novel experimental method to access the dynamic regime of radiation damage formation in nuclear and electronic materials.

#### Measuring tiny forces with light

August 25, 2016

Photons are bizarre: They have no mass, but they do have momentum. And that allows researchers to do counterintuitive things with photons, such as using light to push matter around.

##### Higgsbengaliboson
5 / 5 (1) Mar 26, 2013
Actually it came into news on 18th March that a new scientific quantum computing algorithm has been created which will solve the \$1 million prize set up by Clay Mathematics institute at Cambridge,Massachusetts.

Riemann hypothesis says below a number X we can calculate how many prime numbers are there where it's possible for every X.

Quantum computer is faster than classical computer because their bits occupy multiple numbers at a same time(i.e not 0 or 1).

Using Latorre algorithm,smashing the record of q-bit Quantum computer would require a 80 q-bit computer,bigger than any that exist today but smaller than 1000 bit required for the famous quantum algorithm,shor's to beat the record of factorisation.
##### vacuum-mechanics
1 / 5 (4) Mar 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 in their paper they've uploaded to the preprint server arXiv, their formula that uses spin states of quantum bits (qubits) to calculate the number of prime numbers below a given value.

It is interesting for this new idea about mathematic in quantum ream, anyway the problem is that nowadays we still could not understand the mystery basic foundation of quantum mechanics! Maybe this physical mechanism could help the matter.
http://www.vacuum...19〈=en
##### Whydening Gyre
1 / 5 (3) Mar 27, 2013
It's all in the numbers, gentlemen...