- #1

- 3,106

- 4

Does Deutsch's quantum algorithm provide any profound classical insight into the density of primes?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Loren Booda
- Start date

- #1

- 3,106

- 4

Does Deutsch's quantum algorithm provide any profound classical insight into the density of primes?

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

- #3

- 3,106

- 4

- #4

Zurtex

Science Advisor

Homework Helper

- 1,120

- 1

I don't think very often that Pi(n) is actually calculated by counting up primes, however you look as it that takes up a lot of processing power and storage space very quickly. But hey I don't know much on the subject.

- #5

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

Yes you don't check every number less than n for primality if you want to find pi(n) anymore. This would take at least O(n) operations even if you had a constant time primality test.

Much more efficient are variants of the Meissel-Lehmer method, which can find pi(n) in O(n^(2/3)) steps (divided by some terms involving log n) but don't give you a list of primes up to n.

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.

Much more efficient are variants of the Meissel-Lehmer method, which can find pi(n) in O(n^(2/3)) steps (divided by some terms involving log n) but don't give you a list of primes up to n.

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.

Last edited:

- #6

- 19

- 0

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.

...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).

Share: