论文标题
随机量子3XOR游戏的满意度阶段
Satisfiability Phase Transtion for Random Quantum 3XOR Games
论文作者
论文摘要
最近的结果表明，有可能确定适度的3XOR游戏是否具有完美的量子策略。我们以这些为基础，并提供明确的多项式时间算法，该算法构建了如此完美的策略或反驳其存在。这个新工具使我们能够从数字上研究随机生成的3XOR游戏的行为，这些游戏具有大量问题。 一个关键问题是：伪造游戏游戏（具有完美量子策略但没有完美的古典策略）有多普遍？我们的实验强烈表明，随机生成的游戏为假性人的概率远非1个，实际上它的界限低于0.15。 我们还发现有力的证据表明，随机生成的3XOR游戏同时经历了量子和经典的“相位过渡”，几乎可以肯定地肯定到几乎不完美，因为条款数量（$ m $）与问题数量（$ n $）的比率增加。这两个相变的位置似乎是$ m/n \约2.74 $重合。
Recent results showed it was possible to determine if a modest size 3XOR game has a perfect quantum strategy. We build on these and give an explicit polynomial time algorithm which constructs such a perfect strategy or refutes its existence. This new tool lets us numerically study the behavior of randomly generated 3XOR games with large numbers of questions. A key issue is: how common are pseudotelephathy games (games with perfect quantum strategies but no perfect classical strategies)? Our experiments strongly indicate that the probability of a randomly generated game being pseudotelpathic stays far from 1, indeed it is bounded below 0.15. We also find strong evidence that randomly generated 3XOR games undergo both a quantum and classical "phase transition", transitioning from almost certainly perfect to almost certainly imperfect as the ratio of number of clauses ($m$) to number of questions ($n$) increases. The locations of these two phase transitions appear to coincide at $m/n \approx 2.74$.
