Quantum computer algorithm counts primes

New Scientist : A $1 million prize has been offered for a proof of the Riemann hypothesis: that there is a formula that can calculate the number of prime numbers less than a number X, and that the formula will work for all X. Because no one has figured out yet how to prove the hypothesis, mathematicians have been attempting instead to disprove it by counting primes below a given X and comparing the result with the prediction of Riemann’s formula . Currently, they have found that the hypothesis is true up to X = 10 ²⁴. But that calculation took three months of continuous computing time. To count the number of primes below 10 ²⁵ would take more than nine months. Two researchers in Spain, José Latorre of the University of Barcelona and Germán Sierra of the Autonomous University of Madrid, have now developed the first quantum computer algorithm that can count primes. Latorre’s algorithm requires an 80-qubit computer, however, which is much bigger than any current quantum computer. Nevertheless, when such computers are built, the quantum prime-counting algorithm will significantly speed up the calculations to evaluate the Riemann hypothesis.