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. > > Read more at: > http://phys.org/news/2013-03-quantum-algorithm-prime.html#jCp