Quantum computation and pseudo-telepathic games

TitleQuantum computation and pseudo-telepathic games
Publication TypeJournal Article
Year of Publication2010
AuthorsBub, J
JournalPhilosophy of Science
Date Published2010/05/14

A quantum algorithm succeeds not because the superposition principle allows
'the computation of all values of a function at once' via 'quantum
parallelism,' but rather because the structure of a quantum state space allows
new sorts of correlations associated with entanglement, with new possibilities
for information-processing transformations between correlations, that are not
possible in a classical state space. I illustrate this with an elementary
example of a problem for which a quantum algorithm is more efficient than any
classical algorithm. I also introduce the notion of 'pseudo-telepathic' games
and show how the difference between classical and quantum correlations plays a
similar role here for games that can be won by quantum players exploiting
entanglement, but not by classical players whose only allowed common resource
consists of shared strings of random numbers (common causes of the players'
correlated responses in a game).

Short TitlePhilosophy of Science 75