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.
Source:
http://www.electronicsweekly.com/Articles/2013/03/20/55801/science-quantum-computer-could-tackle-prime-number-mystery.htm
