参考：[STOC 2025] Distributed Quantum Advantage for Local Problems

# Iterated GHZ Game

我们考虑这样一个场景。

给定一个图，图中有一些 white node，代表了一些 players。
图中还有一些 black node，每个 black node 都代表了一场 GHZ game。
每个 white node 都连接且仅连接了$\Delta$ 个 black node，意为这些 players 参加了$\Delta$ 场 GHZ game；而每个 black node 都连接且仅连接了 3 个 white node，意为每场 GHZ game 都有 3 个 players 参加。

然后我们现在假设已经给定了一个染色：对每个 black node 染色为$1,2,...,\Delta$，使得每个 white node 连接的 black node 颜色各不相同。
black node 染色的意思是：该 black node 代表的 GHZ game 在第几轮进行。

现在游戏开始了。既然叫 iterated GHZ game，游戏总共有$\Delta$ 轮，每个 white node 在每一轮都需要输出 1 个 bit。
我们一轮一轮地进行：

• 第一轮时，只考虑那些染色$=1$ 的 black node $v$。和$v$ 相连的 3 个 white node 需要分别输出 1 个 bit $s_1,t_1,u_1$，满足 exactly one of $s_1,t_1,u_1$ is 1。注意，这 3 个 white node 在这一轮没有任何 input，因为这是第一轮。
• 第$n>1$ 轮时，只考虑那些染色$=n$ 的 black node $v$。和$v$ 相连的 3 个 white node 需要分别输出 1 个 bit $s_n,t_n,u_n$，满足

  $$\begin{aligned} & s_n\oplus t_n\oplus u_n=0 && \text{if }s_{n-1}+t_{n-1}+u_{n-1}=0, \\ & s_n\oplus t_n\oplus u_n=1 && \text{if }s_{n-1}+t_{n-1}+u_{n-1}=2, \\ & s_n\oplus t_n\oplus u_n\text{ 无所谓} && \text{if }s_{n-1}+t_{n-1}+u_{n-1}\in\{1,3\}. \\ \end{aligned}$$

  换句话说，这三个 white node 上一轮的 ouput 就是这一轮 GHZ game 的 input。注意，我们只考虑了上一轮的 output 是一个 valid 的 GHZ game input 的情况。

可以注意到，第一轮是比较特殊的，它不是一个 GHZ game。
为什么这样做？因为第一轮没有输入。如果我们非常简单地让所有 white node 第一轮输出都是 1，那么整个 iterated GHZ game 就变成 trivial 的了：不需要进行任何通讯，所有 white node 在每一轮都输出 1 即可。

同样，如果所有 white node 第一轮都输出 0，那么所有 white node 在每一轮都输出 0 也是一个 trivial 的解。

而现在的方案首先保证了必须要有通讯（这样才可能 exact one of $s_1,t_1,u_1$ is 1），然后后续的 GHZ game 的输入又无法确定输出是$011,000,001,010$ 之类的哪一个（因为染色 = 2 的 black node 可能连接不同的 white node），所以整个 iterated GHZ game 就不是 trivial 的了。

---

上述的 iterated GHZ game 在 quantum 下是 1-round 就可以解决的。这很简单，我们并行地进行如下操作：

• 对于染色$=1$ 的 black node，向它的 3 个 neighbor 分别发送信息，让 ID 最小的 node 设为 1，其他两个设为 0；
• 对于染色为$n>1$ 的 black node，制备一个 3-qubits GHZ 态，然后把 3 个 qubits 分别给它的三个 neighbor。同时要告诉它的 neighbors 这个态用于处理第$n$ 轮的 GHZ game；

在这样 1 轮通讯后，剩下的就只需要 local 地进行计算就行了，每个 white node 分别根据上一轮的 ouput 进行测量

上述的 iterated GHZ game 在经典下是$\varTheta(\Delta)$-round 可以解决的。这也很简单，只需要每一轮让参与者进行通讯并求解。

所以核心点在于：要证明，iterated GHZ game 在经典情况下至少要$\varOmega(\Delta)$-round 才能解决。

# LCL Problem in the black-white formalism

我们首先考虑一类问题，被称为 "locally checkable labeling" (LCL) 问题。
我们考虑一种它的特殊形式，即 LCL problem in the black-white formalism。

考虑一个二分图$G=(V,E)$，其中$V=W\cup B$ 是二分图的两个部分，第一部分被称为 White nodes，第二部分是 Black nodes。

那么一个 LCL problem in the black-white formlism 是一个 tuple $\Pi=(\Sigma_{in},\Sigma_{out},\mathcal{C}_w,\mathcal{C}_b)$，其中

• $\Sigma_{in},\Sigma_{out}$ 是两个 finite sets，包含了 labels；
• $\mathcal{C}_w,\mathcal{C}_b$ 是两个 sets of multisets，其中每个 multisets 中的元素都是来自于$\Sigma_{in}\times \Sigma_{out}$。

其中$\mathcal{C}_w,\mathcal{C}_b$ 理解为某种 constraints，即合法的 labeling 方式。形式化地，给定一个把所有 edge 都 labeling 的 assignment$i:E\to \Sigma_{in}$ 作为 input，一个 assignment $o:E\to \Sigma_{out}$ 被称为是一个 solution to $\Pi$ 如果它满足 while and black constraints，即：

• 对于每个 white node $w\in W$，假设$e_1,...,e_{d_w}$ 是与$w$ 相连的 edges，那么

$$\{ (i(e_1),o(e_1)),...,(i(e_{d_w}),o(e_{d_w})) \} \in \mathcal{C}_w;$$

• 对于每个 black node $b\in B$，假设$e_1,...,e_{d_b}$ 是与$b$ 相连的 edges，那么

$$\{ (i(e_1),o(e_1)),...,(i(e_{d_b}),o(e_{d_b})) \} \in \mathcal{C}_b.$$

# Port-numbering model

一个 port-numbered network 被形式化地定义为一个 triple $N=(V,P,p)$，其中

• $V$ 是 nodes 的集合；
• $P$ 是 ports 的集合，每个 node $v$ 的 port 是：$(v,1),(v,2),...,(v,d_v)$，其中$d_v$ 是$v$ 的 degree；
• $p:P\to P$ 是一个函数 specifying connections between ports，满足$p(p(x))=x$。

显然，在一个 port-numbered network 中，两个 nodes $u,v$ 相连当且仅当存在$u,v$ 的 ports $x_u,x_v$ 使得$p(x_u)=x_v$。

我们考虑这样一个 port-numbered network 上的同步分布式算法，其中每个 node 对应一个分布式结点。此外，结合之前的 LCL 问题，给定 input $i:E\to \Sigma_{in}$，我们希望最后每个 white 结点都可以 locally 地计算出它每个 port 对应的边的 output label，即$o:E\to \Sigma_{out}$。

LOCAL model 就是在此基础上，给每个结点一个唯一的 ID：$id(v)\in [n^c]$，其中$c$ 是一个常数。然后如果允许 randomization，那么我们默认需要成功概率至少在$1-1/n$。quantum-LOCAL model 是类似的，除了每个 node 可以对一个 local state 作任意操作，并且可以通过 quantum channel 传递信息。