# Researchers develop quantum computer algorithm for counting prime numbers

##### Mar 26, 2013 by Bob Yirka

(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.

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

Journal reference: arXiv

## Related Stories

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

Feb 06, 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 prime (a prime number defined by the equation N=2n-1, ...

#### Researchers conduct experimental implementation of quantum algorithm

Jan 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 ...

#### 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 ...

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

Aug 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. ...

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

May 03, 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 ...

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

Jun 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.

## Recommended for you

#### Interview with Gerhard Rempe about the fascination of and prospects for quantum information technology

15 hours ago

Gerhard Rempe, Director at the Max Planck Institute of Quantum Optics in Garching, and his colleagues investigate the fundamentals of quantum information technology.

#### Progress in the fight against quantum dissipation

Apr 16, 2014

(Phys.org) —Scientists at Yale have confirmed a 50-year-old, previously untested theoretical prediction in physics and improved the energy storage time of a quantum switch by several orders of magnitude. ...

#### Micro-macro entangled 'cat states' could one day test quantum gravity

Apr 16, 2014

(Phys.org) —In Schrödinger's famous thought experiment, a cat's quantum state becomes entangled with the quantum state of a decaying nucleus, resulting in the odd situation that the cat is both alive and ...

#### A quantum logic gate between light and matter

Apr 10, 2014

Scientists at Max Planck Institute of Quantum Optics, Garching, Germany, successfully process quantum information with a system comprising an optical photon and a trapped atom.

#### Researchers bolster development of programmable quantum computers

Apr 10, 2014

(Phys.org) —University of Chicago researchers and their colleagues at University College London have performed a proof-of-concept experiment that will aid the future development of programmable quantum ...

##### 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...

## More news stories

#### Better thermal-imaging lens from waste sulfur

Sulfur left over from refining fossil fuels can be transformed into cheap, lightweight, plastic lenses for infrared devices, including night-vision goggles, a University of Arizona-led international team ...

#### Researchers find tin selenide shows promise for efficiently converting waste heat into electrical energy

(Phys.org) —A team of researchers working at Northwestern University has found that tin selenide (SnSe) has the highest Carnot efficiency for a thermoelectric cycle ever found, making it potentially a possible ...

#### After 13 years, progress in pitch-drop experiment (w/ video)

(Phys.org) —As Cyclone Ita hit northern Australia last weekend, a much slower collision occurred in the world's longest-running lab project, The University of Queensland's Pitch Drop Experiment.

#### Robotics goes micro-scale

(Phys.org) —The development of light-driven 'micro-robots' that can autonomously investigate and manipulate the nano-scale environment in a microscope comes a step closer, thanks to new research from the ...

#### Scientists observe quantum superconductor-metal transition and superconducting glass

An article published in Nature Physics on March 30, 2014, presents the results of the first experimental study of graphene-based quantum phase transition of the "superconductor-to-metal" type, i.e. transformation of the sy ...

#### Hackathon team's GoogolPlex gives Siri extra powers

(Phys.org) —Four freshmen at the University of Pennsylvania have taken Apple's personal assistant Siri to behave as a graduate-level executive assistant which, when asked, is capable of adjusting the temperature ...

#### Vitamin B3 might have been made in space, delivered to Earth by meteorites

Ancient Earth might have had an extraterrestrial supply of vitamin B3 delivered by carbon-rich meteorites, according to a new analysis by NASA-funded researchers. The result supports a theory that the origin ...

#### First potentially habitable Earth-sized planet confirmed: It may have liquid water

The first Earth-sized exoplanet orbiting within the habitable zone of another star has been confirmed by observations with both the W. M. Keck Observatory and the Gemini Observatory. The initial discovery, ...

#### Bright points in Sun's atmosphere mark patterns deep in its interior

Like a balloon bobbing along in the air while tied to a child's hand, a tracer has been found in the sun's atmosphere to help track the flow of material coursing underneath the sun's surface.

#### Deadly human pathogen Cryptococcus fully sequenced

Within each strand of DNA lies the blueprint for building an organism, along with the keys to its evolution and survival. These genetic instructions can give valuable insight into why pathogens like Cryptococcus ne ...