4 ms·

That’s not how it works . Grovers algorithm takes O(sqrt(n)) using a quantum computer . Values in a quantum computer are superpositions but when measured they

That’s not how it works . Grovers algorithm takes O(sqrt(n)) using a quantum computer . Values in a quantum computer are superpositions but when measured they will return only one result. They don’t have an infinite amount of time and or space .

unnouinceput 7y ago
We are today on quantum computing where we were in 18th century when Ada was creating the 1st computer program. Sure, Grover's algorithm is good for current state of quantum computing but when it will reach to be a current norm just like the Silicon based one is today then is entire state altogether. By that time Grover's algorithm will take it's place in history but will not be used in practice. From wiki: Perform the following "Grover iteration" r(N) times. Iteration? That means one state of the computation is waiting for a previous one to be completed. That, to me, sounds like not a true parallelization algorithm, hence randomsort still wins.
- saagarjha 7y ago
  I suggest you read up on how superposition works in quantum computers–they not just computers with an infinite number of cores :/
  - unnouinceput 7y ago
    No, they are not. Also 128 billion is a big enough number that if you'd say to a 18th century scientist who was working with punch cards computers that in the future one with 128 billion punch cards would exists he would've replied something along the lines, just like you, that there are not enough trees on Earth to create 128 billion cards for a single computer, let alone billion of them that they are more common than horses in 18th century. And yet, here we are, with computers that have 128 GB RAM, like the one I use to reply to you. So how about you let me dream big instead, eh?
    - nullc 7y ago
      If you are going to come up with purely conjectural advantages with no basis in known science, why bother attributing them to one thing (like quantum computing) and not any other thing? Like why are you not arguing that C++24 will make all algorithms O(1)? There is as much reason to believe that as there is to believe that quantum computing will do so. Or maybe graphene memresistors will form timelike loops and allow computers that give you results before you ask the question? Maybe! Again, no more reason to think that won't happen than some kind of purely conjectural magic from quantum computation. Maybe the development of green energy such as solar panels will lead to the development of nano-scale self assemblers, allow us to turn the entire moon into ultra efficient computronium powered by sinking the moon's residual heat of formation into deep space, making the asymptotic complexity of most algorithms on many problems largely irrelevant. Maybe! Or maybe the insight might actually come from a school kid that trips over a rock and gets a vision after hitting their head. Better start putting pebbles out in front of schools, because you never know! :) Isn't getting a sqrt() speedup for everything and an exponential speed up for a few things good enough for you? If we really understand the idea of quantum computing so poorly that that we've massively underestimated it, isn't it even more likely that our misunderstanding has made us massively overestimate it?

unnouinceput 7y ago

We are today on quantum computing where we were in 18th century when Ada was creating the 1st computer program. Sure, Grover's algorithm is good for current state of quantum computing but when it will reach to be a current norm just like the Silicon based one is today then is entire state altogether. By that time Grover's algorithm will take it's place in history but will not be used in practice. From wiki: Perform the following "Grover iteration" r(N) times. Iteration? That means one state of the computation is waiting for a previous one to be completed. That, to me, sounds like not a true parallelization algorithm, hence randomsort still wins.

saagarjha 7y ago
I suggest you read up on how superposition works in quantum computers–they not just computers with an infinite number of cores :/
- unnouinceput 7y ago
  No, they are not. Also 128 billion is a big enough number that if you'd say to a 18th century scientist who was working with punch cards computers that in the future one with 128 billion punch cards would exists he would've replied something along the lines, just like you, that there are not enough trees on Earth to create 128 billion cards for a single computer, let alone billion of them that they are more common than horses in 18th century. And yet, here we are, with computers that have 128 GB RAM, like the one I use to reply to you. So how about you let me dream big instead, eh?
  - nullc 7y ago
    If you are going to come up with purely conjectural advantages with no basis in known science, why bother attributing them to one thing (like quantum computing) and not any other thing? Like why are you not arguing that C++24 will make all algorithms O(1)? There is as much reason to believe that as there is to believe that quantum computing will do so. Or maybe graphene memresistors will form timelike loops and allow computers that give you results before you ask the question? Maybe! Again, no more reason to think that won't happen than some kind of purely conjectural magic from quantum computation. Maybe the development of green energy such as solar panels will lead to the development of nano-scale self assemblers, allow us to turn the entire moon into ultra efficient computronium powered by sinking the moon's residual heat of formation into deep space, making the asymptotic complexity of most algorithms on many problems largely irrelevant. Maybe! Or maybe the insight might actually come from a school kid that trips over a rock and gets a vision after hitting their head. Better start putting pebbles out in front of schools, because you never know! :) Isn't getting a sqrt() speedup for everything and an exponential speed up for a few things good enough for you? If we really understand the idea of quantum computing so poorly that that we've massively underestimated it, isn't it even more likely that our misunderstanding has made us massively overestimate it?