Where does $xy = a + b \pmod 2$ come from in the context of CHSH inequalities?

I have been looking into the great! video lecture of "CSHS Inequality" by Prof. Umesh V. Vazirani. There are a few things I have to clarify, hope someone will answer me.

Suppose Alice and Bob have measured some outcomes in their bases. I am not quite clear how this is linked to the statement $$xy = a + b \pmod 2$$. How are the outputs $$a$$ and $$b$$ of Alice and Bobs related to the basis of measurement output?

• Thanks for the update glS! Sep 22 '20 at 19:15

Alice has a choice of two bases in which to measure, we call her choice $$x$$. Bob also has a choice of two bases in which to measure, we call his choice $$y$$. When they measure we call Alice's measurement outcome $$a$$ and Bob's measurement outcome $$b$$. All $$a,b,x,y \in \{0,1\}$$.

Then Alice and Bob win if $$xy = a + b \mod 2$$. For example if Alice chooses to measure in her basis $$x=0$$ and Bob chooses to measure in his basis $$y=1$$ then they will win if their outcomes are the same, i.e. if $$a=b=0$$ or $$a=b=1$$. Conversely, they will lose if $$a\neq b \mod 2$$.

Note that the CHSH game is defined irrespective of quantum theory -- Alice and Bob can just choose their outputs $$a$$ and $$b$$ however they wish. However, if they do not* use a quantum strategy (and cannot communicate) they can never expect to win with probability greater than 0.75.

*Assuming quantum theory is a correct and complete description of reality.

Calculating the winning probability

Suppose Alice and Bob choose their inputs uniformly at random, i.e., $$p(x,y) = 1/4$$ for all $$x,y \in \{0,1\}$$. Also let $$V:\{0,1\}^4 \rightarrow \{0,1\}$$ be the function $$V(a,b,x,y) = \begin{cases} 1 & \quad \text{if }\,\,xy = a+b \!\!\mod 2 \\ 0 & \quad \text{otherwise} \end{cases}.$$ That is the function outputs $$1$$ if Alice and Bob win and $$0$$ if they lose.

Now you should try to convince yourself that the probability they win the CHSH game is $$p_{\mathrm{win}} = \sum_{abxy} p(x,y) p(a,b|x,y) V(a,b,x,y).$$ More explicitly we get \begin{aligned} p_{\mathrm{win}} &= \frac{1}{4}[p(0,0|0,0) + p(1,1|0,0) + p(0,0|0,1) + p(1,1|0,1) \\ & \quad \,\, + p(0,0|1,0) + p(1,1|1,0) + p(0,1|1,1) + p(1,0|1,1)]. \end{aligned}

So in order to calculate the probability they win we must compute the conditional probability distribution $$p(a,b|x,y)$$.

An optimal quantum strategy

Now in the Lecture you watched it looks like they presented a quantum system that can achieve the best winning probability $$\cos^2(\pi/8)$$. We use the states and measurements described in the video in order to compute the conditional probability distribution $$p(a,b|x,y)$$ for that particular quantum system. The state used is the maximally entangled state $$|\psi\rangle = \tfrac{1}{\sqrt{2}}|00\rangle + \tfrac{1}{\sqrt{2}} |11\rangle$$. The measurements may be represented by a collection of matrices $$A_{a|x}$$ and $$B_{b|y}$$. As measurement operators sum to the identity we have that for all $$x,y \in \{0,1\}$$, $$A_{1|x} = \mathbb{1} - A_{0|x}$$ and $$B_{1|y} = \mathbb{1} - B_{0|y}$$. Thus we only need to specify the operators for outcome $$0$$. For the strategy discussed in the lecture the operators are (in the computational basis) represented by the matrices $$A_{0|0} = \begin{pmatrix} 1&0 \\ 0&0 \end{pmatrix}, \quad A_{0|1} = \begin{pmatrix} 1/2&1/2 \\ 1/2&1/2 \end{pmatrix}, \\ B_{0|0} = \begin{pmatrix} \cos(\pi/8)^2 &\sin(\pi/4)/2 \\ \sin(\pi/4)/2& \sin(\pi/8)^2 \end{pmatrix}, \quad B_{0|1} = \begin{pmatrix} \cos(\pi/8)^2 & -\sin(\pi/4)/2 \\ -\sin(\pi/4)/2& \sin(\pi/8)^2 \end{pmatrix}.$$

Now we can calculate, using the Born rule, the conditional probabilities as $$p(a,b|x,y) = \langle \psi, (A_{a|x} \otimes B_{b|y}) \psi \rangle.$$ To demonstrate, \begin{aligned} p(0,0|0,0) &= \begin{pmatrix} \frac{1}{\sqrt2} & 0 & 0 & \frac{1}{\sqrt2} \end{pmatrix} \begin{pmatrix} \cos(\pi/8)^2 & \sin(\pi/4)/2 &0 &0 \\ \sin(\pi/4)/2 & \sin(\pi/8)^2 & 0 & 0 \\ 0 &0&0&0 \\ 0&0&0&0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ 0\\ 0\\ \frac{1}{\sqrt2} \end{pmatrix} \\ &= \begin{pmatrix} \frac{1}{\sqrt2} & 0 & 0 & \frac{1}{\sqrt2} \end{pmatrix} \begin{pmatrix} \frac{\cos(\pi/8)^2}{\sqrt{2}} \\ \frac{\sin(\pi/4)}{2\sqrt{2}} \\ 0 \\ 0 \end{pmatrix} \\ &= \frac{\cos(\pi/8)^2}{2}. \end{aligned}

I'll leave the rest but after computing the remaining $$p(a,b|x,y)$$ you should find that $$p_{\mathrm{win}} = \cos(\pi/8)^2$$.

• Thanks for the reply Rammus. According to the lecture, depending on x input, Alice make the measurements in 0 degrees, and pi/4 rotated basis. Similarly depending on y input, Bob measures in pi/8 and -pi/8 basis. In this case when Bob and Alice do the measurements in their respective basis, what is actually they are measuring and how it is related to the outputs '1' and '0's? Sep 22 '20 at 19:21
• @radar101 I've elaborated on my previous answer. Hope this helps you. Alice and Bob are measuring their respective halves of the maximally entangled state they share. For instance this could be one of two photons that have been entangled. The outcomes $1$ and $0$ are just labels. The measurements they perform all have two outcomes so we choose these labels but you should note that the probability they win does not depend on how we label the measurement outcomes. For example we could label the outcomes "horse" and "sheep" and we could still form meaningfully the CHSH game, Sep 22 '20 at 21:18
• @radar101 ... Although the winning condition would not be as nice to write down. In the end the CHSH game asks the two players to get outcomes that are the same when $(x,y)\neq (1,1)$ and get outcomes that are different if $(x,y) = (1,1)$. But note that because Alice and Bob only know their own input and not the others they cannot always choose outcomes that allow them to win. Sep 22 '20 at 21:23
• Hi Rammus, many thanks for the answer and effort you have made to explain it to me clearly. It was really helpful. Sep 23 '20 at 16:37
• No problem. Glad I could help. Sep 23 '20 at 17:25