论文标题
3XOR游戏具有完美的通勤操作员策略具有完美的张量产品策略，并且在多项式时间内是可决定的
3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
论文作者
论文摘要
我们考虑具有完美通勤操作员策略的3XOR游戏。鉴于任何3XOR游戏，我们可以在多项式时间内确定游戏的完美通勤操作员策略的存在。以前，这个问题是不可决定的。我们的证明会导致建筑，显示3XOR游戏具有完美的通勤操作员策略，如果FF具有完美的张量产品策略，则使用3量子（8维）GHz状态。这表明，对于完美的3XOR游戏，量子策略比经典策略的优势（由量子古典偏置比率定义）是有限的。这与一般的3XOR情况相反，在该情况下，最佳量子策略可能需要高维状态，并且量子优势无束缚。 为了证明这些结果，我们首先在确定XOR游戏的价值与在一类正确的角度的Coxeter组上解决子组成员问题的实例之间显示等效性。然后，我们在证明本文的大部分时间中证明了与3XOR游戏相对应的实例可以在多项式时间内解决。
We consider 3XOR games with perfect commuting operator strategies. Given any 3XOR game, we show existence of a perfect commuting operator strategy for the game can be decided in polynomial time. Previously this problem was not known to be decidable. Our proof leads to a construction, showing a 3XOR game has a perfect commuting operator strategy iff it has a perfect tensor product strategy using a 3 qubit (8 dimensional) GHZ state. This shows that for perfect 3XOR games the advantage of a quantum strategy over a classical strategy (defined by the quantum-classical bias ratio) is bounded. This is in contrast to the general 3XOR case where the optimal quantum strategies can require high dimensional states and there is no bound on the quantum advantage. To prove these results, we first show equivalence between deciding the value of an XOR game and solving an instance of the subgroup membership problem on a class of right angled Coxeter groups. We then show, in a proof that consumes most of this paper, that the instances of this problem corresponding to 3XOR games can be solved in polynomial time.
