Hacker News Reader

Comment by nawitus | Hacker News Reader

>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..

View on HN

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

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).

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.

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.

>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.

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.

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).

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

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

Reply on news.ycombinator.com