Deutsch's algorithm and p(n)

  • #1
3,077
3

Main Question or Discussion Point

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

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
I don't see any relationship at all between Deutsch's algorithm and the prime counting function -- maybe there is more than one Deutsch's algorithm? The one I found was for a quantum computer to tell if a function from {0, 1} to {0, 1} was constant or not, with only one application of the function.
 
  • #3
3,077
3
My mistake! Shor's algorithm, with a working quantum computer, would have the ability to factor numbers exponentially faster than classical computers. Present encryption, reliant upon prime numbers, would then become obsolete. Mathematically, could quantum mechanics and Shor's algorithm together facilitate a formulaic shortcut for the counting of primes?
 
  • #4
Zurtex
Science Advisor
Homework Helper
1,120
1
Assuming that the Generalized Riemann hypothesis is true then the Miller-Rabin primality test has a runtime of O(log(n)4).

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

Related Threads on Deutsch's algorithm and p(n)

  • 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
Replies
12
Views
3K
Replies
2
Views
7K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
1
Views
3K
Top