<p>I think your history is entirely right. Computer scientists are used to thinking about protocols as games, while physicists are not, and this is probably why these results weren't formulated as games until Cleve et al's paper (written by three computer scientists and one physicist, going by the doctoral degrees)</p>

CC BY-SA 4.0
2022-04-29T16:36:41.427Z
2022-04-29T16:36:41.427Z
Peter Shor 
<p>I have been going through <a href="https://dl.acm.org/doi/10.1145/2213977.2213984" rel="nofollow noreferrer">Certifiable quantum dice: or, true random number generation secure against quantum adversaries</a> by    Umesh Vazirani and Thomas Vidick. They have used entangled particles as shared resources for a quantum nonlocal game aka CHSH game. Because of the acronym CHSH I assumed that the game was proposed by Clauser et al. in their famous paper, <a href="https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.23.880" rel="nofollow noreferrer">Proposed Experiment to Test Local Hidden-Variable Theories</a>. But it looks they proposed only the famous inequality not the game. So, I am trying to trace the evolution of intuitions, ideas and results of the researchers which link the CHSH game with CHSH inequality.</p>
<p>The usual form of CHSH inequality is as follows.</p>
<p><span class="math-container">$$-2 \le S \le 2$$</span></p>
<p>where,
<span class="math-container">$$S = E(a, b) − E(a, b') + E(a', b) + E(a' b')$$</span></p>
<p>Here <span class="math-container">$a$</span> and <span class="math-container">$a'$</span> are detector settings on side <span class="math-container">$A$</span>, <span class="math-container">$b$</span> and <span class="math-container">$b'$</span> on side <span class="math-container">$B$</span>, the four combinations being tested in separate subexperiments. The terms <span class="math-container">$E(a, b)$</span> etc. are the quantum correlations of the particle pairs, where the quantum correlation is defined to be the expectation value of the product of the &quot;outcomes&quot; of the experiment, i.e. the statistical average of <span class="math-container">$A(a)·B(b)$</span>, where <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are the separate outcomes, using the coding <span class="math-container">$+1$</span> for the '<span class="math-container">$+$</span>' channel and <span class="math-container">$−1$</span> for the '<span class="math-container">$−$</span>' channel.</p>
<p>In the <a href="https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.23.880" rel="nofollow noreferrer">original paper</a> the inequality is Equation 1b which is as follows.</p>
<p><span class="math-container">$$|P(\alpha) - P(\alpha + \beta)| \le 2 - P(\gamma) -P(\beta + \gamma)$$</span></p>
<p>As mentioned on page 883 of the paper greatest violation occurs when <span class="math-container">$\alpha = 22.5^\circ$</span> , <span class="math-container">$\beta = 45^\circ$</span>, and <span class="math-container">$\gamma = 157.5^\circ$</span>.</p>
<p>But the paper doesn't describe a nonlocal game. Even the later survey, <a href="https://iopscience.iop.org/article/10.1088/0034-4885/41/12/002" rel="nofollow noreferrer">Bell's theorem. Experimental tests and implications</a>, by Clauser et al. also doesn't describe any nonlocal game.  So, my understanding is that the CHSH inequality is just a component of the CHSH game which was later defined by someone else.</p>
<p>After googling and tracing through the bibliographies of the papers for a while I found the paper, <a href="https://ieeexplore.ieee.org/document/1313847" rel="nofollow noreferrer">Consequences and limits of nonlocal strategies</a>, by Cleve et al. In section 3.1 they have defined the CHSH game formally. I assume this is the first formal description of the game.</p>
<p>CHSH game is just another nonlocal game with two provers. In a CHSH game the contribution of the CHSH inequality is in the strategy of the game. For the nonlocal game the players, Alice and Bob employ strategies in answering to the referee. The strategies are quantum. The possible answers are boolean values. The probability distribution over the answers are the probability distribution retrieved from the measurements performed by them on a shared Bell state. This probability distribution is defined by the CHSH inequality. It's optimality is given by the Tsirelson's equality defined in <a href="https://link.springer.com/article/10.1007/BF00417500" rel="nofollow noreferrer">Quantum generalizations of Bell's inequality </a> (4th condition of the theorem 1) by Tsirelson and <a href="http://www.tau.ac.il/%7Etsirel/download/khts85.html" rel="nofollow noreferrer">Quantum and quasi-classical analogs of Bell inequalities</a> by Khalfin and Tsirelson (Equation 2).</p>
<p>My question is : <strong>Am I able to trace the evolution of the ideas, intuitions and results between CHSH inequality and CHSH game correctly? Did I miss anything?</strong></p>

<quantum-computing><gt.game-theory><quantum-information><pcp><interactive-proofs>
From CHSH inequality to CHSH game
Omar Shehab
# From CHSH inequality to CHSH game

(Asked by: username_0 on 2013-11-11)

I have been going through [Certifiable quantum dice: or, true random number generation secure against quantum adversaries](https://dl.acm.org/doi/10.1145/2213977.2213984) by Umesh Vazirani and Thomas Vidick. They have used entangled particles as shared resources for a quantum nonlocal game aka CHSH game. Because of the acronym CHSH I assumed that the game was proposed by Clauser et al. in their famous paper, [Proposed Experiment to Test Local Hidden-Variable Theories](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.23.880). But it looks they proposed only the famous inequality not the game. So, I am trying to trace the evolution of intuitions, ideas and results of the researchers which link the CHSH game with CHSH inequality.

The usual form of CHSH inequality is as follows.

$$-2 \le S \le 2$$

where,
$$S = E(a, b) − E(a, b') + E(a', b) + E(a' b')$$

Here $a$ and $a'$ are detector settings on side $A$, $b$ and $b'$ on side $B$, the four combinations being tested in separate subexperiments. The terms $E(a, b)$ etc. are the quantum correlations of the particle pairs, where the quantum correlation is defined to be the expectation value of the product of the "outcomes" of the experiment, i.e. the statistical average of $A(a)·B(b)$, where $A$ and $B$ are the separate outcomes, using the coding $+1$ for the '$+$' channel and $−1$ for the '$−$' channel.

In the [original paper](https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.23.880) the inequality is Equation 1b which is as follows.

$$|P(\alpha) - P(\alpha + \beta)| \le 2 - P(\gamma) -P(\beta + \gamma)$$

As mentioned on page 883 of the paper greatest violation occurs when $\alpha = 22.5^\circ$ , $\beta = 45^\circ$, and $\gamma = 157.5^\circ$.

But the paper doesn't describe a nonlocal game. Even the later survey, [Bell's theorem. Experimental tests and implications](https://iopscience.iop.org/article/10.1088/0034-4885/41/12/002), by Clauser et al. also doesn't describe any nonlocal game. So, my understanding is that the CHSH inequality is just a component of the CHSH game which was later defined by someone else.

After googling and tracing through the bibliographies of the papers for a while I found the paper, [Consequences and limits of nonlocal strategies](https://ieeexplore.ieee.org/document/1313847), by Cleve et al. In section 3.1 they have defined the CHSH game formally. I assume this is the first formal description of the game.

CHSH game is just another nonlocal game with two provers. In a CHSH game the contribution of the CHSH inequality is in the strategy of the game. For the nonlocal game the players, Alice and Bob employ strategies in answering to the referee. The strategies are quantum. The possible answers are boolean values. The probability distribution over the answers are the probability distribution retrieved from the measurements performed by them on a shared Bell state. This probability distribution is defined by the CHSH inequality. It's optimality is given by the Tsirelson's equality defined in [Quantum generalizations of Bell's inequality](https://link.springer.com/article/10.1007/BF00417500)  (4th condition of the theorem 1) by Tsirelson and [Quantum and quasi-classical analogs of Bell inequalities](http://www.tau.ac.il/%7Etsirel/download/khts85.html) by Khalfin and Tsirelson (Equation 2).

My question is : **Am I able to trace the evolution of the ideas, intuitions and results between CHSH inequality and CHSH game correctly? Did I miss anything?**

**Tags:** quantum-computing, gt.game-theory, quantum-information, pcp, interactive-proofs

---

## 1 answers

### Answer by username_1 on 2022-04-29. Score: 4 | Accepted answer

I think your history is entirely right. Computer scientists are used to thinking about protocols as games, while physicists are not, and this is probably why these results weren't formulated as games until Cleve et al's paper (written by three computer scientists and one physicist, going by the doctoral degrees)


---

