Check out this recent ArXiv paper in which 2 Spaniards, José Latorre and Germán Sierra, give an qubit circuit that produces a quantum superposition of all the prime numbers less than . They also show how further QC processing of this superposition of primes can be done to calculate the prime counting function . Their QC algorithm can calculate quadratically more efficiently than a classical computer. This permits a QC to probe for much higher values than a classical computer, if both computers have the same amount of time to calculate. Here is a decent, popular press article about their paper, courtesy of the website “I-Programmer”.
I am often asked for a practical example of the use of Grover’s algorithm. Well, this prime thingie is a very nice example, although it assumes some interest in Number Theory and familiarity with it.
Grover’s algorithm is near and dear to my heart, because I use it in my computer program called “Quibbs”(a QC circuit generator written in JAVA) . In Quibbs, I use my own, home-brewed, fixed-point version of Grover’s algorithm to sample any probability distribution inputted in the form of a classical Bayesian network.
Number Theory shows up infrequently in present day physical theories, but it does show up frequently in computer science algorithms and it has deep connections with group theory (Langlands program), and physicists are always interested in group theory. Hence, maybe in the future, physicists will use Number Theory much more often than they do today.