Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Researchers develop quantum computer algorithm for counting prime
numbers

Replies: 1   Last Post: Mar 26, 2013 4:36 PM

 Messages: [ Previous | Next ]
 Sam Wormley Posts: 607 Registered: 12/18/09
Researchers develop quantum computer algorithm for counting prime
numbers

Posted: Mar 26, 2013 3:25 PM

Researchers develop quantum computer algorithm for counting prime numbers

> (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
> Euclid 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, mathematician Bernhard Riemann came up with a formula that
> can be used to ascertain, given a single number, how many prime
> numbers 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.
>