01335nas a2200133 4500008004100000245005200041210005100093260001500144300001200159490000700171520096900178100001701147856003701164 2010 eng d00aQuantum computation and pseudo-telepathic games0 aQuantum computation and pseudotelepathic games c2010/05/14 a458-4720 v753 a 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).
1 aBub, Jeffrey uhttp://arxiv.org/abs/1005.2449v1