XiaoMi-AI文件搜索系统
World File Search SystemTsirelson
编译型异或游戏价值的计算 Tsirelson 定理
非局部博弈是理解纠缠和在具有多个空间分离的量子设备的环境中构建量子协议的基础工具。在这项工作中，我们继续了 Kalai 等人 (STOC '23) 发起的研究，该研究是在经典验证器和单个加密受限的量子设备之间进行的编译非局部博弈。我们的主要结果是，Kalai 等人提出的编译器对于任何双人 XOR 游戏都是可靠的。Tsirelson 的一个著名定理表明，对于 XOR 游戏，量子值由半定程序精确给出，我们通过证明 SDP 上界对于编译的游戏成立，直到编译产生的错误可以忽略不计，从而获得了我们的结果。这回答了 Natarajan 和 Zhang (FOCS '23) 提出的问题，他们展示了 CHSH 游戏特定情况的可靠性。利用我们的技术，我们获得了几个额外的结果，包括（1）并行重复 XOR 游戏的编译值的严格界限、（2）任何编译的 XOR 游戏的运算符自测试语句，以及（3）任何 XOR 游戏的“良好”平方和证书，从中可以看出运算符的刚性。
第 6 讲 - 非局部博弈和 Tsirelson 定理
对于函数 f : X × Y →{ 0, 1 } 的某些选择。直观地说，对于每个问题对 ( x , y )，函数 f 指定 a 和 b 应该一致还是不一致才能成为获胜答案。请注意，对于每个问题对，两种可能性（即 a 和 b 一致或不一致的可能性）中恰好有一种会获胜，而另一种可能性则会失败。由于每个 XOR 游戏都由集合 X 和 Y、概率向量 π ∈ P ( X × Y ) 和函数 f : X × Y →{ 0, 1 } 唯一确定，因此，当方便时，我们将用四元组 ( X , Y , π , f ) 来标识相应的游戏 G。例如，CHSH 游戏是 XOR 游戏的一个例子，对应于四元组 ( { 0, 1 } , { 0, 1 } , π , f )，其中 π 是均匀概率向量，f ( x , y ) = x ∧ y 是 AND 函数。