news center

Quantum computer could solve prime number mystery

作者：蔺舅 时间：2019-03-13 04:14:11 人气： ℃

By Jacob Aron 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. 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 More on these topics: