4 ms·

“Any process can be modeled by a Turing machine” is not the same as “Every process must be isomorphic to a Turing machine, and therefore share the same limitati

“Any process can be modeled by a Turing machine” is not the same as “Every process must be isomorphic to a Turing machine, and therefore share the same limitations.” If I have a magic box that will instantly calculate the Nth digit of the busy beaver number of any size, that can be modeled by a Turning machine. AFAIK there is no constant time algorithm though, which is what our magic box does. So a Turing machine can’t match the performance of our magic box. But no where is it written that a Turing machine puts a an upper bound on performance! That’s what quantum computers are. They solve certain problems faster than a classical computer can. Classical computers can solve the same problems, just more slowly.

fluoridation 2y ago
They are in fact the same, since Turing machines are mathematical models. If you had such a magic box, capable of computing things without regard for their time complexity, we might need to revise our assumptions about whether Turing machines are in fact capable of universally modeling all forms of computation. But like I implied on the sibling comment, I'm expressing skepticism that quantum computation is actually physically realizable, to the extent that functions can be computed in fewer operations (i.e. more efficiently) than is predicted by classical computing.
- adastra22 2y ago
  Well you are free to believe whatever you want. But at this point disbelief in quantum computers is akin to flat earth denial. There are thousands of labs across the world who have performed entanglement experiments, and dozens of labs that have built working quantum computers specifically.
  - fluoridation 2y ago
    I didn't say I don't believe in quantum computers. What I said is I don't believe in quantum computing as a practical technology. Right now "quantum computers" are just research devices to study QC itself. Not a single one has ever computed anything of use to anyone that couldn't have been computed classically.
  - hnfong 2y ago
    That's a bit extreme. While QM and QC theory is well-established, there has been very few experiments that confirm that quantum computing actually works as theorized. There are quantum computers that are "working", but some of them (esp. the older ones) are just the kind of "quantum computers show that 15 = 3 * 15 (with high probability)". From what I read on Scott Aaronson's blog, very few of those experiments show "quantum supremacy" (i.e. classical computing physically cannot compute the results in reasonable time). This is why the Google Willow thing is considered a breakthrough. So basically empirical "proof" that quantum computing actually works as predicted in theory is rather recent stuff.
    - fluoridation 2y ago
      Honestly, I'm skeptical that this even demonstrates quantum supremacy. Like I said in a different comment in this thread, all they did was let the device run for some time on whatever nonsense was in its memory and let it reach some meaningless state. Since it would take a classical computer a long time to simulate the qubits at the physical level to reach the same result, that shows that the quantum computer is much better at executing itself. But that's stupid. By that same logic, electronic computers are faster than themselves, because it would take a long to simulate a computer at the physical level on another, identical computer. If the QC isn't doing any meaningful computation, if it's not actually executing an algorithm, then it's not possible to compare their respective efficiencies. Or rather it is possible, but the answer you get is meaningless. Let's make it fair. How long would it take a ~100 qubit quantum computer to simulate at the physical level a smartphone's SoC running for 1 second?
    - adastra22 2y ago
      Quantum computers are a direct consequence of quantum mechanics. Just like ropes and pulleys are a direct consequence of newtonian mechanics. If you think that quantum computers won't work, then either (1) all the theorists studying them for the past half century have somehow screwed up their basic maths, or (2) our understanding of quantum mechanics is wrong in ways that experiments have already ruled out.
      - fluoridation 2y ago

fluoridation 2y ago

They are in fact the same, since Turing machines are mathematical models. If you had such a magic box, capable of computing things without regard for their time complexity, we might need to revise our assumptions about whether Turing machines are in fact capable of universally modeling all forms of computation. But like I implied on the sibling comment, I'm expressing skepticism that quantum computation is actually physically realizable, to the extent that functions can be computed in fewer operations (i.e. more efficiently) than is predicted by classical computing.

adastra22 2y ago
Well you are free to believe whatever you want. But at this point disbelief in quantum computers is akin to flat earth denial. There are thousands of labs across the world who have performed entanglement experiments, and dozens of labs that have built working quantum computers specifically.
- fluoridation 2y ago
  I didn't say I don't believe in quantum computers. What I said is I don't believe in quantum computing as a practical technology. Right now "quantum computers" are just research devices to study QC itself. Not a single one has ever computed anything of use to anyone that couldn't have been computed classically.
- hnfong 2y ago
  That's a bit extreme. While QM and QC theory is well-established, there has been very few experiments that confirm that quantum computing actually works as theorized. There are quantum computers that are "working", but some of them (esp. the older ones) are just the kind of "quantum computers show that 15 = 3 * 15 (with high probability)". From what I read on Scott Aaronson's blog, very few of those experiments show "quantum supremacy" (i.e. classical computing physically cannot compute the results in reasonable time). This is why the Google Willow thing is considered a breakthrough. So basically empirical "proof" that quantum computing actually works as predicted in theory is rather recent stuff.
  - fluoridation 2y ago
    Honestly, I'm skeptical that this even demonstrates quantum supremacy. Like I said in a different comment in this thread, all they did was let the device run for some time on whatever nonsense was in its memory and let it reach some meaningless state. Since it would take a classical computer a long time to simulate the qubits at the physical level to reach the same result, that shows that the quantum computer is much better at executing itself. But that's stupid. By that same logic, electronic computers are faster than themselves, because it would take a long to simulate a computer at the physical level on another, identical computer. If the QC isn't doing any meaningful computation, if it's not actually executing an algorithm, then it's not possible to compare their respective efficiencies. Or rather it is possible, but the answer you get is meaningless. Let's make it fair. How long would it take a ~100 qubit quantum computer to simulate at the physical level a smartphone's SoC running for 1 second?
  - adastra22 2y ago
    Quantum computers are a direct consequence of quantum mechanics. Just like ropes and pulleys are a direct consequence of newtonian mechanics. If you think that quantum computers won't work, then either (1) all the theorists studying them for the past half century have somehow screwed up their basic maths, or (2) our understanding of quantum mechanics is wrong in ways that experiments have already ruled out.
    - fluoridation 2y ago