news center

Quantum computer could solve prime number mystery

作者：蒙篆 时间：2018-02-06 02:01:13 人气： ℃

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 one can predict when the next one will pop up. One way to measure their distribution is 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 is worth $1 million in prize money from the Clay Mathematics Institute, no one has yet managed to produce one. Mathematicians instead find ways to count primes below ever bigger values of X and compare these to the Riemann prediction to see if any disagree. The record so far has been to count the primes below a septillion. It took three months to crunch the sums; for a number with an extra zero, it would take nine months. Now a team led by José Latorre of the University of Barcelona in Spain has devised the first quantum algorithm to count primes (arxiv.org/abs/1302.6245). 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. That’s bigger than any that exist today but much smaller than the 1000-bit beast required for the famous quantum algorithm, Shor’s,