Main Question or Discussion Point
Does Deutsch's quantum algorithm provide any profound classical insight into the density of primes?
...that's the impression I've always gotten. The factorization part of Shor's algorithm can be done on a classic computer, but it's when you get to the order-finding problem that Shor's algorithm takes advantage of the quantum technology (I don't remember where I read this, but once I do I'll look it up again and provide some more information).I don't know much about quantum computers, so I can't really say what they'll be able to tell us about the density of primes. I'd expect nothing that a classical computer couldn't do, just with less time.