5 ms·

Richard Feynman describes such computation, that produces incorrect results on classic computer and correct one on quantum in "Simulating Physics with Computers

by 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.
    - meroes 5y ago
      For an extreme example, there are finite patterns behind the lava lamps at Cloudfare or the chaos of Jupiter's storms. These are sufficiently random for any current need I can currently imagine though. But then I also see that "classical computers can never be built big enough to explore more than 400, actually more than, probably 100 qubits, 100 qubits doesn’t seem like very much. No classical computer can do the calculation of following what 100 qubits do" https://blog.ycombinator.com/leonard-susskind-on-richard-feynman-the-holographic-principle-and-unanswered-questions-in-physics/ https://blog.ycombinator.com/leonard-susskind-on-richard-fey... Are we really in no danger of quantum computers being able decipher patterns behind these traditional sources of noise? There is no pattern to quantum randomness. Aren't we going to have switch to truly random sources of noise eventually, instead of pseudorandom ones (anything non quantum)?
      - mikewarot 5y ago
        A lava lamp is a chaotic system. The same initial conditions, no matter how precisely measured, will not result in the same outcome, it will diverge. It is non-deterministic in the real world.
        meroes 5y ago
        Wait, let's be clear. In the real world a lava lamp is basically impossible predict as it evolves. And that is due to chaos. So far so good. But this chaos is deterministic. Chaos means highly sensitive to initial conditions and involves nonlinearity, but it is still entirely classical and deterministic. In the real world we do not measure things precise enough to keep track of a lava lamp's deterministic evolution, but it is there within the chaos. So I am wondering if a quantum computer, which Susskind says takes only 100 qubits to outperform any Turing Machine constructable ever, may one day do better at picking out the deterministic patterns behind the chaos of things like lava lamps. And if that happens, we may need more extreme versions of chaotic systems to keep secrets. And since quantum randomness is the only true randomness in the universe, forever indiscernable in principle; will one day all deterministic, chaotic means of adding "randomness" be replaced with quantum sources of randomness, due to how powerful quantum computers are? *Now you could say even the lava lamp involves quantum randomness because everything is ultimately quantum. But because it is so macroscopic, it behaves more classically the a smaller quantum system.
- hau 5y ago
  >"That's all. That's the difficulty. That's why quantum mechanics can't seem to be imitable by a local classical computer." I don't think argument is about efficiency. "a classical computer can perfectly simulate a quantum system/computer" is not explicitily there, it's an argument against that. It seems to me you're saying anything that's not strictly proving BQP > BPP supports something else.
  - tsimionescu 5y ago
    At the very beginning he says: > The rule of simulation that I would like to have is that the number of computer elements required to simulate a large physical system is only to be proportional to the space-time volume of the physical system. I don't want to have an explosion. That is, if you say I want to explain this much physics, I can do it exactly and I need a certain-sized computer. If doubling the volume of space and time means I'll need an exponentially larger computer, I consider that against the rules (I make up the rules, I'm allowed to do that). He emphasizes this again in the section about computing the probabilities: > We emphasize, if a description of an isolated part of nature with N variables requires a general function of N variables and if a computer stimulates this by actually computing or storing this function then doubling the size of nature (N->2N) would require an exponentially explosive growth in the size of the simulating computer. It is therefore impossible, according to the rules stated, to simulate by calculating the probability. [emphasis mine] So when he uses the term 'computer' he doesn't mean 'abstract Turing machine', he explicitly means 'realizable/efficient Turing machine'.

by hau 5y ago

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.
  - meroes 5y ago
    For an extreme example, there are finite patterns behind the lava lamps at Cloudfare or the chaos of Jupiter's storms. These are sufficiently random for any current need I can currently imagine though. But then I also see that "classical computers can never be built big enough to explore more than 400, actually more than, probably 100 qubits, 100 qubits doesn’t seem like very much. No classical computer can do the calculation of following what 100 qubits do" https://blog.ycombinator.com/leonard-susskind-on-richard-feynman-the-holographic-principle-and-unanswered-questions-in-physics/ https://blog.ycombinator.com/leonard-susskind-on-richard-fey... Are we really in no danger of quantum computers being able decipher patterns behind these traditional sources of noise? There is no pattern to quantum randomness. Aren't we going to have switch to truly random sources of noise eventually, instead of pseudorandom ones (anything non quantum)?
    - mikewarot 5y ago
      A lava lamp is a chaotic system. The same initial conditions, no matter how precisely measured, will not result in the same outcome, it will diverge. It is non-deterministic in the real world.
      - meroes 5y ago
        Wait, let's be clear. In the real world a lava lamp is basically impossible predict as it evolves. And that is due to chaos. So far so good. But this chaos is deterministic. Chaos means highly sensitive to initial conditions and involves nonlinearity, but it is still entirely classical and deterministic. In the real world we do not measure things precise enough to keep track of a lava lamp's deterministic evolution, but it is there within the chaos. So I am wondering if a quantum computer, which Susskind says takes only 100 qubits to outperform any Turing Machine constructable ever, may one day do better at picking out the deterministic patterns behind the chaos of things like lava lamps. And if that happens, we may need more extreme versions of chaotic systems to keep secrets. And since quantum randomness is the only true randomness in the universe, forever indiscernable in principle; will one day all deterministic, chaotic means of adding "randomness" be replaced with quantum sources of randomness, due to how powerful quantum computers are? *Now you could say even the lava lamp involves quantum randomness because everything is ultimately quantum. But because it is so macroscopic, it behaves more classically the a smaller quantum system.
hau 5y ago
>"That's all. That's the difficulty. That's why quantum mechanics can't seem to be imitable by a local classical computer." I don't think argument is about efficiency. "a classical computer can perfectly simulate a quantum system/computer" is not explicitily there, it's an argument against that. It seems to me you're saying anything that's not strictly proving BQP > BPP supports something else.
- tsimionescu 5y ago
  At the very beginning he says: > The rule of simulation that I would like to have is that the number of computer elements required to simulate a large physical system is only to be proportional to the space-time volume of the physical system. I don't want to have an explosion. That is, if you say I want to explain this much physics, I can do it exactly and I need a certain-sized computer. If doubling the volume of space and time means I'll need an exponentially larger computer, I consider that against the rules (I make up the rules, I'm allowed to do that). He emphasizes this again in the section about computing the probabilities: > We emphasize, if a description of an isolated part of nature with N variables requires a general function of N variables and if a computer stimulates this by actually computing or storing this function then doubling the size of nature (N->2N) would require an exponentially explosive growth in the size of the simulating computer. It is therefore impossible, according to the rules stated, to simulate by calculating the probability. [emphasis mine] So when he uses the term 'computer' he doesn't mean 'abstract Turing machine', he explicitly means 'realizable/efficient Turing machine'.