## Tuesday, 10 December 2013

### A nonlocal game

Consider the game where Alice and Bob are physically separated and their goal is to produce outputs that satisfy the winning conditions specified below. Alice and Bob receive $s,t \in \{0,1,2\}$ as input ($s$ to Alice and $t$ to Bob), at which point they are forbidden to communicate with each other. They each output a bit, $a$ for alice and $b$ for Bob. The winning conditions are

1. $a=b$ in the cases where $s=t$.
2. $a\neq b$ in the cases where $s\neq t$.
Consider the classical procedure in which Alice and Bob agree to output bits $a$ and $b$ upon receiving inputs $s$ and $t$, respectively, as described in the table displayed on the left below. Then observe the results of all possible game plays when Alice and Bob receive bits $(s,t)$ and output $(a,b)$ according to the table shown on the right:

It can therefore be seen that in all cases where Alice and Bob receive inputs $(s,t)$ such that $s=t$ they always produce outputs $(a,b)$ such that $a=b$, and therefore win with probability $1$ in this case. However, in the case when Alice and Bob receive inputs $(s,t)$ such that $s\neq t$, then they also produce outputs $(a,b)$ such that $a\neq b$ in only $4$ out of the $6$ cases, and produce outputs such that $a=b$ in the remaining $2$ cases. Hence, they only when $4$ out of $6$ times and so succeed in the case when $s\neq t$ with probability $2/3$.

Suppose now that Alice and Bob are playing the game with the same winning conditions, but this time they each possess one qubit of the Bell pair
$\ket{\beta}=\frac{1}{\sqrt{2}}(\ket{00}-\ket{11}),$
where say Alice has the first qubit of the register and Bob the second. Moreover, Alice and Bob are allowed to perform local operations and measurements on their parts of the Bell pair.  They can then base their output bits in the game, $a$ and $b$, depending on the measurement outcomes of their qubits.

Consider the single qubit (unitary) rotation operations by some integer multiple $n$ of $\pi/3$ given by
$R_n=\left( \begin{array}{cc} \cos \left(\frac{\pi n}{3}\right) & -\sin \left(\frac{\pi n}{3}\right) \\ \sin \left(\frac{\pi n}{3}\right) & \cos \left(\frac{\pi n}{3}\right) \\ \end{array} \right).$
Given input bits $s$ and $t$ to Alice and Bob, respectively,  Alice will perform the rotation $R_s$ on her qubit of the Bell state and Bob will perform the rotation $R_{-t}$ in the `negative' direction on his qubit of the Bell state. Then for $r,s\in\{0,1,2\}$, the tensor product of their operations will be given in general by
$R_s\otimes R_{-t}=\left( \begin{array}{cccc} \cos \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right) & \cos \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right) & -\sin \left(\frac{\pi s}{3}\right)\cos \left(\frac{\pi t}{3}\right) & -\sin \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right) \\ -\cos \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right) & \cos \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right) & \sin \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right) & -\sin \left(\frac{\pi s}{3}\right)\cos \left(\frac{\pi t}{3}\right) \\ \sin \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right) & \sin \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right) & \cos \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right) & \cos \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right) \\ -\sin \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right) & \sin \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right) & -\cos \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right) & \cos \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right) \\ \end{array} \right),$
and the resulting state will be $(R_s\otimes R_{-t})\ket{\beta}$. At this point, Alice and Bob will then output bits $a$ and $b$ corresponding to their measurement outcomes upon measuring the state $(R_s\otimes R_{-t})\ket{\beta}$.

Now consider the resulting state in the various cases given inputs $s$ and $t$. In general, the state will be of the form
$(R_s\otimes R_{-t})\ket{\beta}=\left( \begin{array}{c} \frac{\sin \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right)}{\sqrt{2}}+\frac{\cos \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right)}{\sqrt{2}} \\ \frac{\sin \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right)}{\sqrt{2}}-\frac{\cos \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right)}{\sqrt{2}} \\ \frac{\sin \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right)}{\sqrt{2}}-\frac{\cos \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right)}{\sqrt{2}} \\ -\frac{\sin \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right)}{\sqrt{2}}-\frac{\cos \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right)}{\sqrt{2}} \\ \end{array} \right)$

If $s=t$, it can be seen that the resulting state is

$(R_s\otimes R_{-t})\ket{\beta}=\left( \begin{array}{c} \frac{\sin ^2\left(\frac{\pi s}{3}\right)}{\sqrt{2}}+\frac{\cos ^2\left(\frac{\pi s}{3}\right)}{\sqrt{2}} \\ 0 \\ 0 \\ -\frac{\sin ^2\left(\frac{\pi s}{3}\right)}{\sqrt{2}}-\frac{\cos ^2\left(\frac{\pi s}{3}\right)}{\sqrt{2}} \\ \end{array} \right)=\ket{\beta}.$
Therefore, upon measuring the state of their system, since $\ket{\beta}$ is an entangled state, the measurement outcome will either be $\ket{00}$ or $\ket{11}$ with equal probability. Regardless, they will both output either $a=b=0$ or $a=b=1$ and so their outputs always agree in the case when $s=t$.

In the case when $s\neq t$, the resulting state after Alice and Bob perform their rotations is of the form
$(R_s\otimes R_{-t})\ket{\beta}=\left( \begin{array}{c} \frac{\sin \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right)}{\sqrt{2}}+\frac{\cos \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right)}{\sqrt{2}} \\ \frac{\sin \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right)}{\sqrt{2}}-\frac{\cos \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right)}{\sqrt{2}} \\ \frac{\sin \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right)}{\sqrt{2}}-\frac{\cos \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right)}{\sqrt{2}} \\ -\frac{\sin \left(\frac{\pi s}{3}\right) \sin \left(\frac{\pi t}{3}\right)}{\sqrt{2}}-\frac{\cos \left(\frac{\pi s}{3}\right) \cos \left(\frac{\pi t}{3}\right)}{\sqrt{2}} \\ \end{array} \right).$
Expressing the six cases when $s\neq t$ more explicitly:
\begin{align*} (R_0\otimes R_{-1})\ket{\beta}&=\frac{1}{2\sqrt{2}}(\ket{00}-\sqrt{3}\ket{01}-\sqrt{3}\ket{10}-\ket{00})\\ (R_0\otimes R_{-2})\ket{\beta}&=\frac{1}{2\sqrt{2}}(-\ket{00}-\sqrt{3}\ket{01}-\sqrt{3}\ket{10}+\ket{00})\\ (R_1\otimes R_{-0})\ket{\beta}&=\frac{1}{2\sqrt{2}}(\ket{00}+\sqrt{3}\ket{01}+\sqrt{3}\ket{10}-\ket{00})\\ (R_1\otimes R_{-2})\ket{\beta}&=\frac{1}{2\sqrt{2}}(\ket{00}-\sqrt{3}\ket{01}-\sqrt{3}\ket{10}-\ket{00})\\ (R_2\otimes R_{-0})\ket{\beta}&=\frac{1}{2\sqrt{2}}(-\ket{00}+\sqrt{3}\ket{01}+\sqrt{3}\ket{10}+\ket{00})\\ (R_2\otimes R_{-1})\ket{\beta}&=\frac{1}{2\sqrt{2}}(\ket{00}+\sqrt{3}\ket{01}+\sqrt{3}\ket{10}-\ket{00}).\\ \end{align*}
For either of these cases, the probability that Alice and Bob will both measure either $\ket{00}$ or $\ket{11}$ is given by
$Pr(\ket{00} \ or \ \ket{11})=|\bra{00}(R_s\otimes R_{-t})\ket{\beta}|^2+|\bra{11}(R_s\otimes R_{-t})\ket{\beta}|^2=\frac{1}{8}+\frac{1}{8}=\frac{1}{4},$
and the probability that they will measure either $\ket{01}$ or $\ket{10}$ is given by
For either of these cases, the probability that Alice and Bob will both measure either $\ket{00}$ or $\ket{11}$ is given by
$Pr(\ket{01} \ or \ \ket{10})=|\bra{01}(R_s\otimes R_{-t})\ket{\beta}|^2+|\bra{10}(R_s\otimes R_{-t})\ket{\beta}|^2=\frac{3}{8}+\frac{3}{8}=\frac{3}{4}.$

Thus, in any of the cases when $s\neq t$, Alice and Bob will output different bits (either $a=0$ and $b=1$ or $a=1$ and $b=0$) with probability $3/4$, in which case they win the game. However, they lose the game in the case when $s\neq t$, when they both output the same bits (either $a=b=0$ or $a=b=1$) with probability $1/4$.