4 ms·

Actually this is not possible for some definition of possible (mainly performance). Feynman showed that you get an exponential slowdown when simulating QM with

by iliis 13y ago

Actually this is not possible for some definition of possible (mainly performance). Feynman showed that you get an exponential slowdown when simulating QM with a classical computer: http://www.cs.berkeley.edu/~christos/classics/Feynman.pdf http://www.cs.berkeley.edu/~christos/classics/Feynman.pdf See also https://en.wikipedia.org/wiki/Universal_quantum_simulator https://en.wikipedia.org/wiki/Universal_quantum_simulator In this particular case I don't think a quantum computer is necessarily any help (so simulating it won't work either) but rather exploiting nonlocality (https://en.wikipedia.org/wiki/Quantum_nonlocality https://en.wikipedia.org/wiki/Quantum_nonlocality).

nawitus 13y ago
That's like saying "you can't calculate x on a cell phone because it's slower than on a desktop". Yes, there's an exponential slowdown, but that doesn't mean impossible.
- iliis 13y ago
  Yes, absolutely correct. Which is why I said for some definition of possible. 'Feasible' probably would have been the better choice. Keep in mind that we're talking exponential here! e^x blows up really really fast. Yes, it's not impossible to break 4092bit RSA but it is impossible for all practical purposes [AFAIK]. While it is technically possible to run Crysis on a Commodore it is useless when you have to wait a year to render a single frame.
- powrtoch 13y ago
  I think that this is a poor analogy. Saying that a problem suffers an "exponential slowdown" is making a statement about how the performance suffers relative to the size of the problem. As the amount of data to be processed increases, the time required increases exponentially. The type of slowdown you would get just from moving to a system with a weaker processor (like a cell phone) should be approximately linear. You might get worse-than-linear for certain types of RAM issues (more swapping, etc), but this wouldn't be the same as saying there's an exponential slowdown, and it's not a hard fact about the simulation algorithms themselves. Anyway, the point isn't that classical computers are just less powerful, the point is that they're so fundamentally different that calculating quantum phenomena can become actually impossible (as in, process will not finish before the heat death of the universe) relatively quickly as the size of the problem increases.
  - nawitus 13y ago
    >Anyway, the point isn't that classical computers are just less powerful, the point is that they're so fundamentally different that calculating quantum phenomena can become actually impossible (as in, process will not finish before the heat death of the universe) relatively quickly as the size of the problem increases. We don't know that, because not all algorithms have been invented. Furthermore, P=NP is an open problem.

by iliis 13y ago

nawitus 13y ago

That's like saying "you can't calculate x on a cell phone because it's slower than on a desktop". Yes, there's an exponential slowdown, but that doesn't mean impossible.

iliis 13y ago
Yes, absolutely correct. Which is why I said for some definition of possible. 'Feasible' probably would have been the better choice. Keep in mind that we're talking exponential here! e^x blows up really really fast. Yes, it's not impossible to break 4092bit RSA but it is impossible for all practical purposes [AFAIK]. While it is technically possible to run Crysis on a Commodore it is useless when you have to wait a year to render a single frame.
powrtoch 13y ago
I think that this is a poor analogy. Saying that a problem suffers an "exponential slowdown" is making a statement about how the performance suffers relative to the size of the problem. As the amount of data to be processed increases, the time required increases exponentially. The type of slowdown you would get just from moving to a system with a weaker processor (like a cell phone) should be approximately linear. You might get worse-than-linear for certain types of RAM issues (more swapping, etc), but this wouldn't be the same as saying there's an exponential slowdown, and it's not a hard fact about the simulation algorithms themselves. Anyway, the point isn't that classical computers are just less powerful, the point is that they're so fundamentally different that calculating quantum phenomena can become actually impossible (as in, process will not finish before the heat death of the universe) relatively quickly as the size of the problem increases.
- nawitus 13y ago
  >Anyway, the point isn't that classical computers are just less powerful, the point is that they're so fundamentally different that calculating quantum phenomena can become actually impossible (as in, process will not finish before the heat death of the universe) relatively quickly as the size of the problem increases. We don't know that, because not all algorithms have been invented. Furthermore, P=NP is an open problem.