@article {1316,
title = {Quantum computation and pseudo-telepathic games},
journal = {Philosophy of Science},
volume = {75},
year = {2010},
month = {2010/05/14},
pages = {458-472},
abstract = { A quantum algorithm succeeds not because the superposition principle allows
{\textquoteright}the computation of all values of a function at once{\textquoteright} via {\textquoteright}quantum
parallelism,{\textquoteright} 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 {\textquoteright}pseudo-telepathic{\textquoteright} 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{\textquoteright}
correlated responses in a game).
},
url = {http://arxiv.org/abs/1005.2449v1},
author = {Jeffrey Bub}
}