5 ms·

quantum computers are not just faster classical computers. Quantum algorithms have no classical counterpart. In fact the literal clock speed per quantum computa

quantum computers are not just faster classical computers. Quantum algorithms have no classical counterpart. In fact the literal clock speed per quantum computation may be slower but the computation will still get done faster overall.

Robotbeat 5y ago
But there’s no computation a quantum computer can do that a classical computer can’t. In that sense, it’s still a Turing machine. It can do some class of computation faster (in principle).
- throwaway3699 5y ago
  If we want to reach AGI within the lifetime of the universe, and quantum effects are required for consciousness [within the lifetime etc...], it stands to reason we'd need quantum computers.
  - tsimionescu 5y ago
    Yes, that is true, at least as far as we know today (it's not yet mathematically proven that quantum computers can't be efficiently simulated by probabilistic classical computers, even though we are almost certain of this).
- hau 5y ago
  Richard Feynman describes such computation, that produces incorrect results on classic computer and correct one on quantum in "Simulating Physics with Computers"[0]. He follows one physical experiment detailing every step from start to finish and how it converges to incorrect result on classical computer. [0] - https://doi.org/10.1007/BF02650179 https://doi.org/10.1007/BF02650179
  - tsimionescu 5y ago
    Thank you for the link! I have also found a free version for anyone else interested: http://physics.whu.edu.cn/dfiles/wenjian/1_00_QIC_Feynman.pdf http://physics.whu.edu.cn/dfiles/wenjian/1_00_QIC_Feynman.pd... However, Feynman does not claim what you say he claims. His whole article is about efficiently simulating QM on a classical computer, and he shows that is not possible given what we understand of quantum probability today, at least (he does this by explicitly asking for a computer which does not grow exponentially in size with the size of the physical system it wants to simulate). In modern CS terms, what he is discussing is whether the complexity classes BPP and BQP are equal or not (as far as we know today, just as he claims, BPP seems to be a smaller subset of BQP, but this is not proven). This is all perfectly in line with my claim, and is in fact explicitly there in Feynman's paper: a classical computer can perfectly simulate a quantum system/computer, but requires exponential time/space to do so (as far as we know).
    - meroes 5y ago
      Perfectly except for random number generation right? The randomness of QM can never be decoded or attacked. If we are talking about fudging/"simulating" randomness with classical pseudorandom number generators and relying on computational complexity prohibiting decoding the patterns, and quantum computers are theoretically able to speed up factorization of large numbers, don't we have a problem? Isn't there a point where we could say we can't really simulate powerful enough quantum computers because they can "decode" the patterns behind any psuedorandom computation so quickly? Like no one in the right mind would be using classical computers at that point except for anything except basic computation and word processing. We might as well say humans and pen and papers can simulate quantum computers. Quantum computer capabilities may outstrip classical computers nearly as much as they do humans with pen and paper. "Simulation" kind of loses it's meaning when taken far enough.
      - tsimionescu 5y ago
        Random numbers are random numbers. You can calculate the probabilities (the wave function amplitudes, which are deterministic); or you can use any source of random noise to reproduce the data, once you adjust for the difference between quantum and classical probability.

Robotbeat 5y ago

But there’s no computation a quantum computer can do that a classical computer can’t. In that sense, it’s still a Turing machine. It can do some class of computation faster (in principle).

throwaway3699 5y ago
If we want to reach AGI within the lifetime of the universe, and quantum effects are required for consciousness [within the lifetime etc...], it stands to reason we'd need quantum computers.
- tsimionescu 5y ago
  Yes, that is true, at least as far as we know today (it's not yet mathematically proven that quantum computers can't be efficiently simulated by probabilistic classical computers, even though we are almost certain of this).
hau 5y ago
Richard Feynman describes such computation, that produces incorrect results on classic computer and correct one on quantum in "Simulating Physics with Computers"[0]. He follows one physical experiment detailing every step from start to finish and how it converges to incorrect result on classical computer. [0] - https://doi.org/10.1007/BF02650179 https://doi.org/10.1007/BF02650179
- tsimionescu 5y ago
  Thank you for the link! I have also found a free version for anyone else interested: http://physics.whu.edu.cn/dfiles/wenjian/1_00_QIC_Feynman.pdf http://physics.whu.edu.cn/dfiles/wenjian/1_00_QIC_Feynman.pd... However, Feynman does not claim what you say he claims. His whole article is about efficiently simulating QM on a classical computer, and he shows that is not possible given what we understand of quantum probability today, at least (he does this by explicitly asking for a computer which does not grow exponentially in size with the size of the physical system it wants to simulate). In modern CS terms, what he is discussing is whether the complexity classes BPP and BQP are equal or not (as far as we know today, just as he claims, BPP seems to be a smaller subset of BQP, but this is not proven). This is all perfectly in line with my claim, and is in fact explicitly there in Feynman's paper: a classical computer can perfectly simulate a quantum system/computer, but requires exponential time/space to do so (as far as we know).
  - meroes 5y ago
    Perfectly except for random number generation right? The randomness of QM can never be decoded or attacked. If we are talking about fudging/"simulating" randomness with classical pseudorandom number generators and relying on computational complexity prohibiting decoding the patterns, and quantum computers are theoretically able to speed up factorization of large numbers, don't we have a problem? Isn't there a point where we could say we can't really simulate powerful enough quantum computers because they can "decode" the patterns behind any psuedorandom computation so quickly? Like no one in the right mind would be using classical computers at that point except for anything except basic computation and word processing. We might as well say humans and pen and papers can simulate quantum computers. Quantum computer capabilities may outstrip classical computers nearly as much as they do humans with pen and paper. "Simulation" kind of loses it's meaning when taken far enough.
    - tsimionescu 5y ago
      Random numbers are random numbers. You can calculate the probabilities (the wave function amplitudes, which are deterministic); or you can use any source of random noise to reproduce the data, once you adjust for the difference between quantum and classical probability.