Researchers develop quantum computer algorithm for counting prime numbers

Mar 26, 2013 by Bob Yirka report
Structure of the Quantum Primality Oracle based on the Miller-Rabin primality test. A series of unitary modules implement a quantum version of the modular exponentiation tests required by the classical test. The total number of tests m is smaller than n2. Credit: arXiv:1302.6245 [quant-ph]

(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: Physicists discuss quantum pigeonhole principle

More information: Quantum Computation of Prime Number Functions, arXiv:1302.6245 [quant-ph] arxiv.org/abs/1302.6245

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

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

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

Recommended for you

Physicists discuss quantum pigeonhole principle

Jul 26, 2014

The pigeonhole principle: "If you put three pigeons in two pigeonholes at least two of the pigeons end up in the same hole." So where's the argument? Physicists say there is an important argument. While the ...

Unleashing the power of quantum dot triplets

Jul 24, 2014

Quantum computers have yet to materialise. Yet, scientists are making progress in devising suitable means of making such computers faster. One such approach relies on quantum dots—a kind of artificial atom, ...

Exotic state of matter propels quantum computing theory

Jul 23, 2014

So far it exists mainly in theory, but if invented, the large-scale quantum computer would change computing forever. Rather than the classical data-encoding method using binary digits, a quantum computer would process information ...

Quantum leap in lasers brightens future for quantum computing

Jul 22, 2014

Dartmouth scientists and their colleagues have devised a breakthrough laser that uses a single artificial atom to generate and emit particles of light. The laser may play a crucial role in the development of quantum computers, ...

Boosting the force of empty space

Jul 22, 2014

Vacuum fluctuations may be among the most counter-intuitive phenomena of quantum physics. Theorists from the Weizmann Institute (Rehovot, Israel) and the Vienna University of Technology propose a way to amplify ...

User comments : 3

Adjust slider to filter visible comments by rank

Display comments: newest first

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