Quantum computer could solve prime number mystery

A million-dollar puzzle relating to prime numbers could be tackled using only a mid-sized quantum computer.

There is a race to find ever bigger primes, but no way to predict when the next one will pop up. One option is to measure their distribution via a formula that calculates how many exist below a number, X. The Riemann hypothesis says this is possible for every X. But though a proof for this is worth $1 million in prize money from the Clay Mathematics Institute in Cambridge, Massachusetts, no one has yet managed to produce one.

Instead mathematicians find ways to count primes below ever bigger values of X and compare these to the Riemann prediction to see if any disagree ? if they do, this would disprove Riemann.

The record so far has been to count the primes below a septillion. It took Dave Platt of the University of Bristol, UK, three months to crunch the sums. For a number with an extra zero, it would take nine months. "At some point you have to say, is anybody going to have the motivation to go higher?" he says.

'Surprisingly powerful'

Now Jos? Latorre of the University of Barcelona in Spain, along with Germ?n Sierra of the Autonomous University of Madrid, has devised the first quantum algorithm to count primes. Quantum computers should be faster than ordinary ones because their bits occupy multiple states at once, not just a 1 or a 0. But the largest ones built have just a handful of "qubits", so this speed gain has not been practically realised.

Using the Latorre algorithm, smashing the record for primes would require an 80 qubit computer, bigger than any that exist today but much smaller than the 1000 bit beast required for the famous quantum algorithm, Shor's, to beat the record for factorisation.

"The idea is simple, elegant and surprisingly powerful," says Seth Lloyd of the Massachusetts Institute of Technology. "It would be a good thing to do with a small quantum computer, if you had one."

Journal reference: arxiv.org/abs/1302.6245

If you would like to reuse any content from New Scientist, either in print or online, please contact the syndication department first for permission. New Scientist does not own rights to photos, but there are a variety of licensing options available for use of articles and graphics we own the copyright to.

Have your say

Only subscribers may leave comments on this article. Please log in.

Only personal subscribers may leave comments on this article

Subscribe now to comment.

All comments should respect the New Scientist House Rules. If you think a particular comment breaks these rules then please use the "Report" link in that comment to report it to us.

If you are having a technical problem posting a comment, please contact technical support.

Source: http://feeds.newscientist.com/c/749/f/10897/s/29b3e8c4/l/0L0Snewscientist0N0Carticle0Cdn232890Equantum0Ecomputer0Ecould0Esolve0Eprime0Enumber0Emystery0Bhtml0Dcmpid0FRSS0QNSNS0Q20A120EGLOBAL0Qonline0Enews/story01.htm

polar bear plunge lovelace antioch the grey review demi moore 911 call ipo jim rome