论文标题
解决多人游戏的量子跨古典优势
Quantum-over-classical Advantage in Solving Multiplayer Games
论文作者
论文摘要
我们研究了量子算法在计算游戏理论中的适用性，并概括了与减法游戏有关的一些结果，这些结果有时被称为单高的NIM游戏。 在量子游戏理论中，减法游戏的子集成为了第一个明确定义的零和组合游戏类别，具有量子和经典复杂性之间可证明的分离。对于较窄的减法游戏子集，已知一种精确的量子sublinear算法超过了所有确定性算法，用于查找概率$ 1 $的解决方案。 通常，仅针对两个玩家定义了NIM和减法游戏。我们将一些已知的结果扩展到三个或更多玩家的游戏，同时保持相同的经典和量子复杂性：$θ\ left（n^2 \ right）$和$ \ tilde {o} \ left（n^{1.5} \ right）$。
We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum combinatorial games with provable separation between quantum and classical complexity of solving them. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms for finding solutions with probability $1$. Typically, both Nim and Subtraction games are defined for only two players. We extend some known results to games for three or more players, while maintaining the same classical and quantum complexities: $Θ\left(n^2\right)$ and $\tilde{O}\left(n^{1.5}\right)$ respectively.
