Researchers develop quantum computer algorithm for counting prime numbers

March 26, 2013 by Bob Yirka, Phys.org 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: University professor discovers largest prime number to date

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

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

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

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

Recommended for you

Walking crystals may lead to new field of crystal robotics

February 23, 2018

Researchers have demonstrated that tiny micrometer-sized crystals—just barely visible to the human eye—can "walk" inchworm-style across the slide of a microscope. Other crystals are capable of different modes of locomotion ...

Researchers turn light upside down

February 23, 2018

Researchers from CIC nanoGUNE (San Sebastian, Spain) and collaborators have reported in Science the development of a so-called hyperbolic metasurface on which light propagates with completely reshaped wafefronts. This scientific ...

Recurrences in an isolated quantum many-body system

February 23, 2018

It is one of the most astonishing results of physics—when a complex system is left alone, it will return to its initial state with almost perfect precision. Gas particles, for example, chaotically swirling around in a container, ...

Seeing nanoscale details in mammalian cells

February 23, 2018

In 2014, W. E. Moerner, the Harry S. Mosher Professor of Chemistry at Stanford University, won the Nobel Prize in chemistry for co-developing a way of imaging shapes inside cells at very high resolution, called super-resolution ...

Hauling antiprotons around in a van

February 22, 2018

A team of researchers working on the antiProton Unstable Matter Annihilation (PUMA) project near CERN's particle laboratory, according to a report in Nature, plans to capture a billion antiprotons, put them in a shipping ...

3 comments

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

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.