- 3,073
- 3
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.