CHSH game#
写于2025年1月23日
从领导那听来了这个 CHSH博弈，感觉颇有意思，记录之。
基础规则#
小技巧
什么是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 运算，则二人共同取得胜利.
备注
可以发现，因为 XOR 的真值表是
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 的真值表是:
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这样就真没意思了，因为可以直接算出答案。。
首先，将二进制变量\(a, b \in \{0,1\}\)映射为Spin变量\(\pm 1\)：
简单换算可以发现，胜利条件可统一写为：
定义期望值\(E(i,j)\)，即输入为\(i, j\)时\(a \cdot b\)的统计平均值。由于\(a\)和\(b\)仅取\(\pm 1\)，乘积\(a b\)也只能为\(\pm 1\)。 设2可以看到，如果我们随机选取 \(a,b\in\{\pm 1\}\), 那么 \(P_\pm=\frac{1}{2}\). 而如果我们无论如何都取 \(a,b=1\) （注意这里已经是自旋变量了），则 \(P_+ = 1, P_- = 0\).：
深入思考：
这儿使用概率和期望做推导是有一些奇怪，不过考虑两个事实:
如果我们局限于使用某种确定性的策略，我们想求解的东西是“获胜概率”，引入概率还是必要的。在一套策略之下，几个 \(i,j\) 不同的 \(P^{i,j}_{\pm}\) 之间是相互关联的，虽然他们只能等于固定的 \(\pm1\)，但仍然可以使用
max函数。如果我们使用的是某种随机的策略，或者干脆用量子力学的方法来产生策略(这在后边会提到)，那么这类策略出现的结果当然是概率性的。概率论的应用或许本就如此深刻。
期望值为概率与特征值的乘积和：
结合概率归一化条件\(P_{+} + P_{-} = 1\)，解得：
胜利概率分两种情况：
若\(i \land j = 0\)：
要求\(a b = +1\)，此时：\[ P_{\text{win}}(i,j) = P_{+} = \frac{1 + E(i,j)}{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因此，我们调整策略，实际上就是修改在不同 \(i,j\) 时候的 \(P_{\text{win}}\). 例如之前提出的策略，虽然在三个情况下都是赢，但在最后一个情况下赢不了。：
定义CHSH表达式为：
则：
经典策略#
所以，如果要找到最佳的策略，我们实际上要 \(\max(S)\)
将\(S\)表达式重写为：
由于 \(b_0, b_1 \in \{\pm 1\}\), 二者只能相等或不等，原式变为:
所以，
经典 CHSH 的最优策略确实就是使得胜率为 \(\frac{3}{4}\) 的方法，当然，我们用的方法只是其中之一。
重要
也许这看上去是让人困惑的: 为什么不能 \(100\%\) 赢呢？
原因是，不管如何，Alice 和 Bob 不知道对方拿到的是什么。真值表有四种情况，自己只能看见一半的信息，因此不能说 "\(i,j=0,0\) 时我们就怎么出." 这种话。只能说" Alice 看见 0 时该出 1, Bob 看见 1 时该出 0"，这样是不能保证赢的。
量子 trick#
设想一种小技巧: Alice 和 Bob 共享了一对 Bell 态的量子比特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\) 即是单次测量后的结果，所以胜利条件是不变的:
后续的推导显然也不变，不涉及中间的测量过程，因此CHSH表达式仍不变5这里期望值的引入就非常合理了。:
之前，只要策略一旦确定，\(a_i, b_j\) 即为固定值，CHSH表达式以及获胜概率也为定值。而在这里，即使策略已经确定，由于 \(a_i, b_j\) 是单次观测值，它们的乘积是不固定的。
根据对易算符测量的先后顺序无关，不管这两人实际上谁先谁后测量，他们获得的一组 \(a,b\) 都具有相同的分布，所以在 \(i,j\) 确定时他们结果的"XOR"操作期望值即为:
提示
一个有趣的事实是他们的本征值正好是 \(\pm 1\), 而其共同本征值 \(ab = a \oplus b\), 因此这里的化简非常顺畅。
因而:
将各个 \(A_i, B_j\) 代入，于是解得
深入分析
显然，游戏之所以不能有百分百的取胜策略，是因为 Alice 和 Bob 总是无法知道对方的信息。使用这种量子通信方法，尽管两个人没有实时的传递信息，但他们通过量子纠缠的对实现了对输入 \(i,j\) 的关联，从而增大了获胜的概率。
这对量子计算也是有启示的：增大所受计算对象之间的联系，或许就能有超越现有经典计算策略的超级算法出现。