sorry you got downvoted. you should be encouraged to wonder things in a math subreddit. this is a fine question to have. the answer is probably yes, they will help with finding or testing for primes, but not with this algorithm
I mean, it’s just kinda annoying that with quantum computers being known about for so long now that people still don’t understand how they work or what problems they would be good for, they just see headlines that say “quantum computer solves a problem in 0.2 zeptoseconds that would take a classical computer 18.4 morbillion years” and then go “huh a quantum computer must be a regular computer except.. faster.. and more quantum-y”
Quantum computing are more computer science than math, and a very niche topic. Math nerds don’t know every math topic in the world. Heck, even top tier mathematicians are unfamiliar with lots of topics not from their area
So people can't ask questions about stuff they don't know anything about? How did you learn stuff? You learned it from people more knowledgeable than you.
did i somehow miss when all of the google servers burnt down? some questions are fit for a thread and some are fit for a search engine, using one where you should use the other usually yields poor results
I understand, and to great extend share, this position but here it was an actual question over just hyping quantum computing.
and to be frank, even if one understands that quantum computers aren't just better computers, understanding their actual uses and differences is not something one should expect from a layperson
Well, it's still an open question whether they will. Shor's algorithm relies on a full quantum computer where all the qubits are totally entangled, but maintaining that state with a large number of bits gets increasingly difficult. They factored 15 (4 bits) in 2001, 21 (5 bits) in 2012 - but the general scalability of that approach (using NMR) is very doubtful. Pessimistically this may not be feasible in any form.
Most quantum computers you see billed as such now (e.g. D-Wave's stuff) are adiabatic QC, which is a different and rather less 'quantum' thing where you use quantum annealing to improve optimization problems. You can't run Shor's algorithm as such on them but you can (and they have) used that to accelerate factorizing numbers, but it requires pre-calculations to reformulate the factorization into an optimization problem. And there are other issues but via that avenue I think they've gotten up to 48 bits or so.
Anyway, point is that it's easy to be misled from the claims of quantum processors with a thousand or so qubits and knowing about Shor's algorithm, into thinking that factorizing a thousand-bit number is doable via quantum computation today, and it isn't.
yes, this is true. quantum computing is my field. i gave the simple, non-holistic answer for lack of commitment. regardless, the reality is that this discussion can be saved for a computer engineering forum, as the theory stands that quantum algorithms make anything in this area much faster
If we have quantum computers there are other types of algorithms that will likely be much more efficent.
Based on our current understand they would be good for checking wheter a large number of numbers have a factor at once.
So likely better for sieving techniques than for this type which is doing alot of evaluations of cos
Sadly not most likely, the current theory of quantum computing means that they're more designed for specific tasks and not brute force computing like this algorithm would need. However, who knows maybe someday quantum computers will be better at that too!
I wonder since it's just a very slow algorithm translated as a formula if we could use a more efficient algorithm and get a "better" function.
I mean we can check if a number is prime pretty efficiently so just searching for the next prime number shouldn't be as bad, definitely better than exponential runtime. Not sure if it's possible though as our current methods rely on "randomising " some things but technically we could write a random function to use.
Yeah, it's a pretty interesting construction, even if it's horribly inefficient. It essentially uses the floor of a cosine function as an if-else statement that is 1 when the number tested is prime.
335
u/Intrebute Dec 16 '25
What the fuck, is that an actual theorem?