- #1

- 3,077

- 3

## Main Question or Discussion Point

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

- Thread starter Loren Booda
- Start date

- #1

- 3,077

- 3

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

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

- #3

- 3,077

- 3

- #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

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

- Last Post

- Replies
- 3

- Views
- 4K

- Last Post

- Replies
- 4

- Views
- 6K

- Replies
- 6

- Views
- 14K

- Last Post

- Replies
- 4

- Views
- 9K

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 12

- Views
- 3K

- Last Post

- Replies
- 2

- Views
- 7K

- Last Post

- Replies
- 13

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 5K

- Last Post

- Replies
- 1

- Views
- 3K