The University of Barcelona’s Jose Latorre and the Autonomous University of Madrid’s German Sierra say they have devised the first quantum algorithm to count prime numbers. The researchers say the algorithm could be used with an 80-qubit computer to break the record for primes. Such a computer would be bigger than any that exist today, but would be much smaller than the 1,000-bit computer needed for Shor’s quantum algorithm to beat the record for factorization. “The idea is simple, elegant, and surprisingly powerful,” says the Massachusetts Institute of Technology’s Seth Lloyd. “It would be a good thing to do with a small quantum computer, if you had one.” The Clay Mathematics Institute offers $1 million in prize money to solve a puzzle related to prime numbers, and the researchers’ quantum algorithm could be used to win the competition.
More info: New Scientist (03/18/13) Jacob Aron