3 ms·

>Next, by bringing quantum mechanics into the game, the researchers showed that players who can use quantum resources, such as entangled quantum particles, can

by nawitus 13y ago

>Next, by bringing quantum mechanics into the game, the researchers showed that players who can use quantum resources, such as entangled quantum particles, can outperform classical players. That is, quantum players achieve better performance than any classical player ever could. Classical players can build a classical computer which simulates quantum computers. Of course, I really should read the paper instead of zero-content press releases..

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.
darkmighty 13y ago
I think it's not in a computing context, but in a nonlocality context. Although I can't picture a way of using nonlocality in a useful manner without violating relativity (i.e. if their performance improves due to "instantaneous" interactions, their performance increase could be measured allowing superluminal transmission of information).
Strilanc 13y ago
They're not using computational advantages, they're using coordination advantages via entanglement. See: the quantum pseudo-telepathy article on wikipedia [1], which has an example of a game where players with entangled particles do better than classical players. 1: http://en.wikipedia.org/wiki/Quantum_pseudo-telepathy http://en.wikipedia.org/wiki/Quantum_pseudo-telepathy
- pureeville 13y ago
  Thanks for this. I was thinking to myself, where have I heard of this before?

by nawitus 13y ago

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.

darkmighty 13y ago

I think it's not in a computing context, but in a nonlocality context. Although I can't picture a way of using nonlocality in a useful manner without violating relativity (i.e. if their performance improves due to "instantaneous" interactions, their performance increase could be measured allowing superluminal transmission of information).

Strilanc 13y ago

They're not using computational advantages, they're using coordination advantages via entanglement. See: the quantum pseudo-telepathy article on wikipedia [1], which has an example of a game where players with entangled particles do better than classical players. 1: http://en.wikipedia.org/wiki/Quantum_pseudo-telepathy http://en.wikipedia.org/wiki/Quantum_pseudo-telepathy

pureeville 13y ago
Thanks for this. I was thinking to myself, where have I heard of this before?