---
orphan: True
---

# CHSH game

```{card}
写于2025年1月23日
^^^

从领导那听来了这个 CHSH博弈，感觉颇有意思，记录之。
```

## 基础规则

```{tip} 
:class: margin
**什么是CHSH博弈？**

CHSH（Cbauser-Horne-Shimony-Hobt）博弈是量子非局域性研究中的经典案例，通过简单的规则揭示了经典物理与量子物理的深刻差异。
```

有两名选手 Alice 和 Bob， 他们分别收到输入$i,j \in \{0,1\}$，他们独立的输出$a,b \in \{0,1\}$。

如果满足$a \oplus b = i \land j$。其中 $\land$ 为 AND 运算，$\oplus$ 为 XOR 运算，则二人共同取得胜利.

````{note}

可以发现，因为 XOR 的真值表是

```{list-table} XOR真值表
---
width: 80%
name: xor
header-rows: 1
---

* - a
  - b
  - $a\oplus b$
* - 0
  - 0
  - 0
* - 0
  - 1
  - 1
* - 1
  - 0
  - 1
* - 1
  - 1
  - 0
```

可以看到，如果 Alice 和 Bob 两人随意的输出一组 $a,b$, 则结果为1或者0的概率均等，对于任何的输入，获胜概率只有 $50\%$.

然而，如果两人商量好一个策略，例如，考虑到 AND 的真值表是:

```{list-table} AND真值表
---
width: 80%
name: and
header-rows: 1
---

* - i
  - j
  - $i\land j$
* - 0
  - 0
  - 0
* - 0
  - 1
  - 0
* - 1
  - 0
  - 0
* - 1
  - 1
  - 1
```

有 $75\%$ 的概率为 0. 那么其实可以选择“无论如何两人都一起出 $a,b=0 \Rightarrow a\oplus b=0$”, 则可以保证有 75% 的概率获胜。

````

## 数学化

那么，有没有更强的获胜策略呢？只要我们保证在面对输出时不进行临时的商量[^1]。

[^1]: 这样就真没意思了，因为可以直接算出答案。

首先，将二进制变量$a, b \in \{0,1\}$映射为Spin变量$\pm 1$：

简单换算可以发现，胜利条件可统一写为：

$$
a \cdot b = (-1)^{i \land j}.
$$
定义期望值$E(i,j)$，即输入为$i, j$时$a \cdot b$的统计平均值。由于$a$和$b$仅取$\pm 1$，乘积$a b$也只能为$\pm 1$。 
设[^2]：

```{admonition} 深入思考：
---
class: seealso dropdown
---
这儿使用概率和期望做推导是有一些奇怪，不过考虑两个事实:

1. 如果我们局限于使用某种确定性的策略，我们想求解的东西是“获胜概率”，引入概率还是必要的。在一套策略之下，几个 $i,j$ 不同的 $P^{i,j}_{\pm}$ 之间是相互关联的，虽然他们只能等于固定的 $\pm1$，但仍然可以使用 `max` 函数。
2. 如果我们使用的是某种随机的策略，或者干脆用量子力学的方法来产生策略(这在后边会提到)，那么这类策略出现的结果当然是概率性的。概率论的应用或许本就如此深刻。

```

$$
P_{\pm}^{i,j} = P(ab = \pm 1 | i,j )
$$

期望值为概率与特征值的乘积和：

[^2]: 可以看到，如果我们随机选取 $a,b\in\{\pm 1\}$, 那么 $P_\pm=\frac{1}{2}$. 而如果我们无论如何都取 $a,b=1$ （注意这里已经是自旋变量了），则 $P_+ = 1, P_- = 0$.

$$
E(i,j) = (+1) \cdot P_{+} + (-1) \cdot P_{-} = P_{+} - P_{-}.
$$
结合概率归一化条件$P_{+} + P_{-} = 1$，解得：

$$
P_{+} = \frac{1 + E(i,j)}{2}, \quad P_{-} = \frac{1 - E(i,j)}{2}.
$$

胜利概率分两种情况：
1. **若$i \land j = 0$**：  
   要求$a b = +1$，此时：

   $$
   P_{\text{win}}(i,j) = P_{+} = \frac{1 + E(i,j)}{2}.
   $$
2. **若$i \land j = 1$**：  
   要求$a b = -1$，此时：

   $$
   P_{\text{win}}(i,j) = P_{-} = \frac{1 - E(i,j)}{2}.
   $$

所有输入$(i,j)$等概率出现（各$\frac{1}{4}$），总获胜概率为[^3]：

[^3]: 因此，我们调整策略，实际上就是修改在不同 $i,j$ 时候的 $P_{\text{win}}$. 例如之前提出的策略，虽然在三个情况下都是赢，但在最后一个情况下赢不了。

$$
P_{\text{win}} = \frac{1}{2} + \frac{1}{8} \left[ E(0,0) + E(0,1) + E(1,0) - E(1,1) \right]
$$
定义**CHSH表达式**为：

$$
\begin{split}
S &= E(0,0) + E(0,1) + E(1,0) - E(1,1) \\
&= a_0b_0 + a_0b_1 + a_1b_0 - a_1b_1
\end{split}
$$
则：

$$
P_{\text{win}} = \frac{1}{2} + \frac{S}{8}.
$$


## 经典策略

所以，如果要找到最佳的策略，我们实际上要 $\max(S)$

将$S$表达式重写为：

$$
S = a_0b_0 + a_0b_1 + a_1b_0 - a_1b_1 = a_0(b_0 + b_1) + a_1(b_0 - b_1).
$$
由于 $b_0, b_1 \in \{\pm 1\}$, 二者只能相等或不等，原式变为:

$$
S = \pm2 a_i
$$
所以，

$$
\max(S) = 2
$$
经典 CHSH 的最优策略确实就是使得胜率为 $\frac{3}{4}$ 的方法，当然，我们用的方法只是其中之一。


```{important}
也许这看上去是让人困惑的: 为什么不能 $100\%$ 赢呢？

原因是，不管如何，Alice 和 Bob 不知道对方拿到的是什么。真值表有四种情况，自己只能看见一半的信息，因此不能说 "$i,j=0,0$ 时我们就怎么出." 这种话。只能说" Alice 看见 0 时该出 1, Bob 看见 1 时该出 0"，这样是不能保证赢的。
```

## 量子 trick

设想一种小技巧: Alice 和 Bob 共享了一对 Bell 态的量子比特[^4].

[^4]: 现在是否觉得这两人的名字有点耳熟了? 

而两人手里拿着两个测量操作，Alice 拿着 $A_0, A_1 = Z, X$. 而 Bob 手里拿着 $B_0, B_1 = \frac{1}{\sqrt{2}}(Z+X), \frac{1}{\sqrt{2}}(Z-X)$. 这两人进去之后直接根据看见的 $i,j$ 情况进行 $A_i, B_j$ 测量，对测量出的结果 $a,b$ 再做 XOR, 他们的胜率能提高到 $85.3\%$!

### 严格推导

在解释这个令人惊奇的结果之前，我想先推导一下这个过程: 显然，除了经典上 $i,j$ 的随机性带来的概率差别以外，量子测量又带了了额外的概率，所以这里的式子肯定是更复杂的。

我们先定义 $a,b$ 即是单次测量后的结果，所以胜利条件是不变的:

$$
a \cdot b = (-1)^{i \land j}.
$$

后续的推导显然也不变，不涉及中间的测量过程，因此**CHSH表达式**仍不变[^5]:

$$
\begin{split}
S &= E(0,0) + E(0,1) + E(1,0) - E(1,1) \\
&= a_0b_0 + a_0b_1 + a_1b_0 - a_1b_1
\end{split}
$$

之前，只要策略一旦确定，$a_i, b_j$ 即为固定值，CHSH表达式以及获胜概率也为定值。而在这里，即使策略已经确定，由于 $a_i, b_j$ 是单次观测值，它们的乘积是不固定的。

根据[对易算符测量的先后顺序无关](/docs/量子计算/measurement/basic.md#对易的两个算符测量先后顺序无关)，不管这两人实际上谁先谁后测量，他们获得的一组 $a,b$ 都具有相同的分布，所以在 $i,j$ 确定时他们结果的"XOR"操作期望值即为:

```{hint}
:class: margin

一个有趣的事实是他们的本征值正好是 $\pm 1$, 而其共同本征值 $ab = a \oplus b$, 因此这里的化简非常顺畅。
```

$$
\begin{split}
E(i,j) &= \sum_{a,b\in\{\pm1\}} \mathbb{p}_{A_i^a, B_j^b}\times ab \\
&= \braket{\Psi|P_{A_i^a}\otimes P_{B_j^b}|\Psi}\times ab \\
&= \braket{\Psi|A_i \otimes B_j|\Psi}
\end{split}
$$

因而:

$$
S = \sum_{ij}\braket{\Psi|(-1)^{i\land j}A_i \otimes B_j|\Psi}
$$

将各个 $A_i, B_j$ 代入，于是解得

$$
P_\text{win} = \frac{1}{2} + \frac{\boxed{2\sqrt{2}}}{8} = 85.355\%
$$

```{admonition} 深入分析
:class: note

显然，游戏之所以不能有百分百的取胜策略，是因为 Alice 和 Bob 总是无法知道对方的信息。使用这种量子通信方法，尽管两个人没有实时的传递信息，但他们通过量子纠缠的对实现了对输入 $i,j$ 的关联，从而增大了获胜的概率。

这对量子计算也是有启示的：增大所受计算对象之间的联系，或许就能有超越现有经典计算策略的超级算法出现。

```

 <!-- --- -->

[^5]: 这里期望值的引入就非常合理了。