Quantum pseudo-telepathy

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, so they each have two particles. 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. A suitable correlated state consists of a pair of entangled 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_x 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 along her row, and −1 for Bob down his column. Of course, each completely new round requires a new entangled state, as different rows and columns are not compatible with each other.

In classical non-cooperative game theory a coordination game is any game with multiple Nash equilibrium. 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.

Classically, Alice, Bob, and Carol can employ a deterministic strategy that always end up with odd sum (e.g. Alice always output 1. Bob and Carol always output 0). The players win 75% of the time and only lose if the questions are ${\displaystyle (0,0,0)}$.

In fact, this is the best winning strategy classically. We can only satisfy a maximum of 3 out of 4 winning conditions. Let ${\displaystyle a_{0},a_{1}}$ be Alice's response to question 0 and 1 respectively, ${\displaystyle b_{0},b_{1}}$ be Bob's response to question 0, 1, and ${\displaystyle c_{0},c_{1}}$ be Carol's response to question 0, 1. We can write all constraints that satisfy winning conditions as

$${\displaystyle {\begin{aligned}&a_{0}+b_{0}+c_{0}=0\mod 2\\&a_{1}+b_{1}+c_{0}=1\mod 2\\&a_{1}+b_{0}+c_{1}=1\mod 2\\&a_{0}+b_{1}+c_{1}=1\mod 2\end{aligned}}}$$

Suppose that there is a classical strategy that satisfies all four winning conditions, all four conditions hold true. Through observation, each term appears twice on the left hand side. Hence, the left side sum = 0 mod 2. However, the right side sum = 1 mod 2. The contradiction shows that all four winning conditions cannot be simultaneously satisfied.

Now we have come to the interesting part where Alice, Bob, and Carol decided to adopt a quantum strategy. The three of them now share a tripartite entangled state ${\textstyle |{\psi }\rangle ={\frac {1}{\sqrt {2}}}(|000\rangle +|111\rangle )}$, known as the GHZ state.

If question 0 is received, the player makes a measurement in the X basis ${\textstyle \{|+\rangle ,|-\rangle \}}$. If question 1 is received, the player makes a measurement in the Y basis ${\textstyle \left\{{\frac {1}{\sqrt {2}}}(|0\rangle +i|1\rangle ),{\frac {1}{\sqrt {2}}}(|0\rangle -i|1\rangle )\right\}}$. In both cases, the players give answer 0 if the result of the measurement is the first state of the pair, and answer 1 if the result is the second state of the pair.

It is easy to check that with this strategy the players win the game with probability 1.