GHZ Game

不假思索地抹去老物与自己存在的证据。

考虑这样一个 game，有三个人 Alice、Bob 和 Charlie。现在均匀随机地从$\{000,011,110,101\}$ 中选取一个串，并把三个 bit 分别给 Alice、Bob 和 Charlie。然后他们三个人在不互相通讯的情况下，分别输出一个 bit，记为$a,b,c$。如果满足

$$a\oplus b \oplus c = x \lor y \lor z,$$

就算赢得这个 game。很显然，除了$xyz=000$ 的情况外，都需要$a\oplus b\oplus c=1$。

经典情况下，获胜概率最多只有 3/4。为什么呢？我们不妨假设 Alice、Bob 和 Charlie 分别使用函数$f_A,f_B,f_C:\{0,1\}\to \{0,1\}$ 来决定输出的 bit。那么我们有

$$\begin{array}{c|c} \text{输入}x,y,z & \text{需要的输出} \\ \hline 0,0,0 & 0=f_A(0)\oplus f_B(0)\oplus f_C(0) \\ 0,1,1 & 1=f_A(0)\oplus f_B(1)\oplus f_C(1) \\ 1,0,1 & 1=f_A(1)\oplus f_B(0)\oplus f_C(1) \\ 1,1,0 & 1=f_A(1)\oplus f_B(1)\oplus f_C(0) \\ \end{array}$$

我们证明，无论采取怎样的策略（即不同的$f_A,f_B,f_C$），都不可能同时满足上面四个等式。

这很简单，我们把右侧后三个等式异或起来，就可以得到

$$f_A(0)\oplus f_B(0)\oplus f_C(0) = 1,$$

这和右侧第一个等式矛盾，所以不存在这样的$f_A,f_B,f_C$ 同时满足四个等式。

因此确定策略（$f_A,f_B,f_C$）后，至少有 1/4 的概率输掉这个 game。

---

但是量子情形不一样，我们允许 Alice、Bob 和 Charlie 在游戏开始前共享一个 GHZ 态

$$|\text{GHZ}\rangle = \frac{|000\rangle + |111\rangle}{\sqrt{2}}.$$

Alice、Bob 和 Charlie 采取同样的策略：如果输入是 0，那么对自己的 qubit 作 X-basis 测量；否则作 Y-basis 测量。如果策略结果是 + 1，那么输出 0；否则输出 1。

下面我们验证这个策略会以 100% 的概率赢得这个 game。

令$A,B,C=\pm 1$ 分别是策略的结果，那么根据策略，赢的情况$a\oplus b\oplus c=x\lor y\lor z$ 等价于

$$A\cdot B\cdot C = (-1)^{x\lor y \lor z}.$$

注意到，我们有如下恒等式

$$\begin{aligned} & X\otimes X\otimes X |\text{GHZ}\rangle = +|\text{GHZ}\rangle, \\ & X\otimes Y\otimes Y |\text{GHZ}\rangle = -|\text{GHZ}\rangle, \\ & Y\otimes X\otimes Y |\text{GHZ}\rangle = -|\text{GHZ}\rangle, \\ & Y\otimes Y\otimes X |\text{GHZ}\rangle = -|\text{GHZ}\rangle. \\ \end{aligned}$$

换句话说，输入是$000$ 时，$|\text{GHZ}\rangle$ 是$X\otimes X\otimes X$ 的本征值为$+1$ 的本征态；输入是$011,101,110$ 时，$|\text{GHZ}\rangle$ 是对应的 operator 的本征值为$-1$ 的本征态。

而$A\cdot B \cdot C$ 的值，正是测量上面三个 tensor 起来的 operator 的结果。

因此，$A\cdot B\cdot C=1$ 如果输入是$000$；否则$A\cdot B\cdot C=-1$。也就是说，这个策略总是赢得这个 game。