Quantum pseudo-telepathy

Quantum pseudo-telepathy is the fact that in certain Bayesian games with asymmetric information, players who have access to a shared physical system in an entangled quantum state, and who are able to execute strategies that are contingent upon measurements performed on the entangled physical system, are able to achieve higher expected payoffs in equilibrium than can be achieved in any mixed-strategy Nash equilibrium of the same game by players without access to the entangled quantum system.

This article uses quantum theoretical concepts and terminology. For a generally accessible introduction to quantum mechanics, see Introduction to quantum mechanics.

In their 1999 paper,[1] Gilles Brassard, Richard Cleve and Alain Tapp demonstrated that quantum pseudo-telepathy allows players in some games to achieve outcomes that would otherwise only be possible if participants were allowed to communicate during the game.

This phenomenon came to be referred to as quantum pseudo-telepathy,[2] with the prefix pseudo referring to the fact that quantum pseudo-telepathy does not involve the exchange of information between any parties. Instead, quantum pseudo-telepathy removes the need for parties to exchange information in some circumstances.

By removing the need to engage in communication to achieve mutually advantageous outcomes in some circumstances, quantum pseudo-telepathy could be useful if some participants in a game were separated by many light years, meaning that communication between them would take many years. This would be an example of a macroscopic implication of quantum non-locality.

Quantum pseudo-telepathy is generally used as a thought experiment to demonstrate the non-local characteristics of quantum mechanics. However, quantum pseudo-telepathy is a real-world phenomenon which can be verified experimentally. It is thus an especially striking example of an experimental confirmation of Bell inequality violations.

Games of asymmetric information

A Bayesian game is a game in which both players have imperfect information regarding the value of certain parameters. In a Bayesian game it is sometimes the case that for at least some players, the highest expected payoff achievable in a Nash equilibrium is lower than that which could have been achieved had there not have been imperfect information. Asymmetric information is a special case of imperfect information, in which different players differ in terms of the knowledge they possess regarding the value of certain parameters.

A common assumption in classical Bayesian games of asymmetric information is that all players are unaware of the values of certain crucial parameters before the game begins. Once the game begins, different players receive information regarding the value of different parameters. However, once the game begins, players are forbidden to communicate and are consequently unable to exchange the information they collectively possess regarding the game's parameters.

This assumption has a crucial implication: even if players are able to communicate and discuss strategies before the game begins, this will not enhance any player's expected payoff, because the crucial information regarding unknown parameters has not yet been 'revealed' to the game's participants. However, if the game were to be modified, so that players were permitted to communicate after the game has begun, once each player has received some information regarding the value of some of the unknown parameters, then it may be possible for the game's participants to achieve a Nash equilibrium which is Pareto optimal to any Nash equilibrium achievable in the absence of communication.

The crucial implication of quantum telepathy is that although communication before a Bayesian game of asymmetric information begins does not result in improved equilibrium payoffs, it can be proven that in some Bayesian games, allowing players to exchange entangled qubits before the game begins can allow players to achieve a Nash equilibrium which would only otherwise be achievable if in-game communication were permitted.

The Mermin–Peres magic square game

When attempting to construct a 3×3 table filled with the numbers +1 and −1, such that each row has an even number of negative entries and each column an odd number of negative entries, a conflict is bound to emerge.

An example of quantum pseudo-telepathy can be observed in the Mermin–Peres magic square game.

This game features two players, Alice and Bob.

At the very start of the game, Alice and Bob are separated. After they are separated, communication between them is not possible.

The game requires that Alice fill in one row, and Bob one column, of a 3x3 table with plus and minus signs.

Before the game begins, Alice does not know which row of the table she will be required to fill in. Similarly, Bob does not know which column he will be required to fill in.

After the two players are separated, Alice is randomly assigned one row of the table and asked to fill it with plus and minus signs. Similarly, Bob is randomly assigned one column of the table and asked to fill it with plus and minus signs.

The players are subject to the following requirement: Alice must fill in her row such that there is an even number of minus signs in that row. Furthermore, Bob must fill in his column such that there is an odd number of minus signs in that column.

Crucially, Alice does not know which column Bob has been asked to fill in. Similarly, Bob does not know which row Alice has been asked to fill in. Thus, this game is a Bayesian game with asymmetric imperfect information, since neither player has complete information about the game (imperfect information) and both players differ in terms of the information that they do possess (asymmetric information).

Depending on the actions taken by participants, one of two outcomes can occur in this game. Either both players win, or both players lose.

If Alice and Bob place the same sign in the cell shared by their row and column, they win the game. If they place opposite signs, they lose the game.

Note that both players place all their plus and minus signs simultaneously, and neither player can see where the other player has placed their signs until the game is finished.

It is easy to prove that in the classic formulation of this game, there is no strategy (Nash equilibrium or otherwise) which allows the players to win the game with probability greater than 8/9. If Alice and Bob meet before the game begins and exchange information, this will not impact the game in any way; the best the players can do is still win with probability 8/9.

The reason why the game can only be won with probability 8/9 is that a perfectly consistent table does not exist: it would be self-contradictory, with the sum of the minus signs in the table being even based on row sums, and being odd when using column sums, or vice versa. As a further illustration, if they use the partial table shown in the diagram (supplemented by a −1 for Alice and a +1 for Bob in the missing square) and the challenge rows and columns are selected at random, they will win 8/9 of the time. No classical strategy exists which can beat this victory rate (with random row and column selection).

If the game was modified to allow Alice and Bob to communicate after they discover which row/column they have been assigned, then there will exist a set of strategies allowing both players to win the game with probability 1. However, if quantum pseudo-telepathy were used, then Alice and Bob could both win the game without communicating.

Pseudo-telepathic strategies

Use of quantum pseudo-telepathy would enable Alice and Bob to win the game 100% of the time without any communication once the game has begun.

This requires Alice and Bob to possess two pairs of particles with entangled states. These particles must have been prepared before the start of the game. One particle of each pair is held by Alice and the other by Bob. When Alice and Bob learn which column and row they must fill, each uses that information to select which measurements they should make to their particles. The result of the measurements will appear to each of them to be random (and the observed partial probability distribution of either particle will be independent of the measurement performed by the other party), so no real "communication" takes place.

However, the process of measuring the particles imposes sufficient structure on the joint probability distribution of the results of the measurement such that if Alice and Bob choose their actions based on the results of their measurement, then there will exist a set of strategies and measurements allowing the game to be won with probability 1.

Note that Alice and Bob could be light years apart from one another, and the entangled particles will still enable them to coordinate their actions sufficiently well to win the game with certainty.

Each round of this game uses up one entangled state. Playing N rounds requires that N entangled states (2N independent Bell pairs, see below) be shared in advance. This is because each round needs 2-bits of information to be measured (the third entry is determined by the first two, so measuring it isn't necessary), which destroys the entanglement. There is no way to reuse old measurements from earlier games.

The trick is for Alice and Bob to share an entangled quantum state and to use specific measurements on their components of the entangled state to derive the table entries[3]. A suitable correlated state consists of an entangled pair of Bell states:

${\displaystyle \left|\varphi \right\rangle ={\frac {1}{\sqrt {2}}}{\bigg (}\left|+\right\rangle _{a}\otimes \left|+\right\rangle _{b}+\left|-\right\rangle _{a}\otimes \left|-\right\rangle _{b}{\bigg )}\otimes {\frac {1}{\sqrt {2}}}{\bigg (}\left|+\right\rangle _{c}\otimes \left|+\right\rangle _{d}+\left|-\right\rangle _{c}\otimes \left|-\right\rangle _{d}{\bigg )}}$

here ${\displaystyle \left|+\right\rangle }$ and ${\displaystyle \left|-\right\rangle }$ are eigenstates of the Pauli operator S_z with eigenvalues +1 and −1, respectively, whilst the subscripts a, b, c, and d identify the components of each Bell state, with a and c going to Alice, and b and d going to Bob. The symbol ${\displaystyle \otimes }$ represents a tensor product.

Observables for these components can be written as products of the Pauli spin matrices:

${\displaystyle S_{x}={\begin{bmatrix}0&1\\1&0\end{bmatrix}},S_{y}={\begin{bmatrix}0&-i\\i&0\end{bmatrix}},S_{z}={\begin{bmatrix}1&0\\0&-1\end{bmatrix}}}$

Products of these Pauli spin operators can be used to fill the 3×3 table such that each row and each column contains a mutually commuting set of observables with eigenvalues +1 and −1, and with the product of the observables in each row being the identity operator, and the product of observables in each column equating to minus the identity operator. This is a so-called Mermin–Peres magic square. It is shown in below table.

${\displaystyle +I\otimes S_{z}}$	${\displaystyle +S_{z}\otimes I}$	${\displaystyle +S_{z}\otimes S_{z}}$
${\displaystyle +S_{x}\otimes I}$	${\displaystyle +I\otimes S_{x}}$	${\displaystyle +S_{x}\otimes S_{x}}$
${\displaystyle -S_{x}\otimes S_{z}}$	${\displaystyle -S_{z}\otimes S_{x}}$	${\displaystyle +S_{y}\otimes S_{y}}$

Effectively, while it is not possible to construct a 3×3 table with entries +1 and −1 such that the product of the elements in each row equals +1 and the product of elements in each column equals −1, it is possible to do so with the richer algebraic structure based on spin matrices.

The play proceeds by having each player make one measurement on their part of the entangled state per round of play. Each of Alice's measurements will give her the values for a row, and each of Bob's measurements will give him the values for a column. It is possible to do that because all observables in a given row or column commute, so there exists a basis in which they can be measured simultaneously. For Alice's first row she needs to measure both her particles in the ${\displaystyle S_{z}}$ basis, for the second row she needs to measure them in the ${\displaystyle S_{x}}$ basis, and for the third row she needs to measure them in an entangled basis. For Bob's first column he needs to measure his first particle in the ${\displaystyle S_{x}}$ basis and the second in the ${\displaystyle S_{z}}$ basis, for second column he needs to measure his first particle in the ${\displaystyle S_{z}}$ basis and the second in the ${\displaystyle S_{x}}$ basis, and for his third column he needs to measure both his particles in a different entangled basis, the Bell basis. As long as the table above is used, the measurement results are guaranteed to always multiply out to +1 for Alice, and −1 for Bob, thus winning the round. Of course, each new round requires a new entangled state, as different rows and columns are not compatible with each other.

Coordination games

In classical non-cooperative game theory a coordination game is any game with multiple Nash equilibria. The literature regarding pseudo-telepathy occasionally refers to games such as the Mermin–Peres game as coordination games. On one hand, this is technically correct, because the classic variant of the Mermin–Peres game does feature multiple Nash equilibria.

However, quantum pseudo-telepathy does not provide any solution to the coordination problems which characterize coordination games. Quantum pseudo-telepathy's utility lies in resolving problems with asymmetric information in Bayesian games where communication is prohibited.

For example, implementing pseudo-telepathic strategies in the Mermin–Peres game can remove the need of Bob and Alice to exchange information. However, pseudo-telepathic strategies do not resolve coordination problems. Specifically, even after implementing pseudo-telepathic strategies, Bob and Alice will only win the game with probability one if they both coordinate their pseudo-telepathic strategies in a manner isomorphic to that described above.

Current research

It has been demonstrated[4] that the above-described game is the simplest two-player game of its type in which quantum pseudo-telepathy allows a win with probability one. Other games in which quantum pseudo-telepathy occurs have been studied, including larger magic square games,[5] graph colouring games[6] giving rise to the notion of quantum chromatic number,[7] and multiplayer games involving more than two participants.[8] Recent studies tackle the question of the robustness of the effect against noise due to imperfect measurements on the coherent quantum state.[9] Recent work has shown an exponential enhancement in the communication cost of nonlinear distributed computation, due to entanglement, when the communication channel itself is restricted to be linear.[10]

See also

• Quantum refereed game
• GHZ state – an entangled 3-particle state.
• EPR paradox
• Kochen–Specker theorem
• Quantum information science
• Qubit
• Tsirelson's bound
• Wheeler–Feynman absorber theory

Notes

1. Brassard, Gilles; Cleve, Richard; Tapp, Alain (1999). "Cost of Exactly Simulating Quantum Entanglement with Classical Communication". Physical Review Letters. 83 (9): 1874–1877. arXiv:quant-ph/9901035. Bibcode:1999PhRvL..83.1874B. doi:10.1103/PhysRevLett.83.1874.
2. Brassard, Gilles; Broadbent, Anne; Tapp, Alain (2003). "Multi-party Pseudo-Telepathy". Algorithms and Data Structures. Lecture Notes in Computer Science. 2748. pp. 1–11. arXiv:quant-ph/0306042. doi:10.1007/978-3-540-45078-8_1. ISBN 978-3-540-40545-0.
3. Aravind, P.K. (2004). "Quantum mysteries revisited again" (PDF). American Journal of Physics. 72 (10): 1303–1307. arXiv:quant-ph/0206070. Bibcode:2004AmJPh..72.1303A. CiteSeerX 10.1.1.121.9157. doi:10.1119/1.1773173.
4. Gisin, N.; Methot, A. A.; Scarani, V. (2007). "Pseudo-telepathy: Input cardinality and Bell-type inequalities". International Journal of Quantum Information. 5 (4): 525–534. arXiv:quant-ph/0610175. doi:10.1142/S021974990700289X.
5. Kunkri, Samir; Kar, Guruprasad; Ghosh, Sibasish; Roy, Anirban (2006). "Winning strategies for pseudo-telepathy games using single non-local box". arXiv:quant-ph/0602064.
6. Avis, D.; Hasegawa, Jun; Kikuchi, Yosuke; Sasaki, Yuuya (2006). "A Quantum Protocol to Win the Graph Colouring Game on All Hadamard Graphs". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 89 (5): 1378–1381. arXiv:quant-ph/0509047. Bibcode:2006IEITF..89.1378A. doi:10.1093/ietfec/e89-a.5.1378.
7. Cameron, Peter J.; Montanaro, Ashley; Newman, Michael W.; Severini, Simone; Winter, Andreas (2007). "On the quantum chromatic number of a graph". Electronic Journal of Combinatorics. 14 (1). arXiv:quant-ph/0608016. doi:10.37236/999.
8. Brassard, Gilles; Broadbent, Anne; Tapp, Alain (2005). "Recasting Mermin's multi-player game into the framework of pseudo-telepathy". Quantum Information and Computation. 5 (7): 538–550. arXiv:quant-ph/0408052. Bibcode:2004quant.ph..8052B.
9. Gawron, Piotr; Miszczak, Jarosław; Sładkowski, JAN (2008). "Noise Effects in Quantum Magic Squares Game". International Journal of Quantum Information. 06: 667–673. arXiv:0801.4848v1. Bibcode:2008arXiv0801.4848G. doi:10.1142/S0219749908003931.
10. Marblestone, Adam Henry; Devoret, Michel (2010). "Exponential quantum enhancement for distributed addition with local nonlinearity". Quantum Information Processing. 9: 47–59. arXiv:0907.3465. doi:10.1007/s11128-009-0126-9.

External links

• Understanding and simulating quantum pseudo-telepathy