论文标题
一端量子裁判的游戏的复杂性限制
Complexity limitations on one-turn quantum refereed games
论文作者
论文摘要
本文研究了量子裁判的游戏的复杂性理论方面，这些游戏是两个竞争玩家之间的抽象游戏，这些玩家将量子状态发送给裁判员，他们对这两个状态进行了有效实施的联合测量，以确定哪些球员获胜。复杂性类别$ \ mathrm {qrg}（1）$包含那些决策问题，其中一个玩家总是可以在Yes-Instances上以很高的概率获胜，而其他玩家总是可以在No-In-Instances上以很高的概率获胜，而不论对手的策略如何。此类琐碎地包含$ \ mathrm {qma} \ cup \ text {co - } \ mathrm {qma} $，并已知包含在$ \ mathrm {pspace} $中。我们证明了该类别的两个限制变体上的更强遏制。 Specifically, if one of the players is limited to sending a classical (probabilistic) state rather than a quantum state, the resulting complexity class $\mathrm{CQRG}(1)$ is contained in $\exists\cdot\mathrm{PP}$ (the nondeterministic polynomial-time operator applied to $\mathrm{PP}$);虽然如果两个玩家都发送量子状态，但裁判被迫首先测量其中一种状态，并将此测量的经典结果纳入对第二状态的测量，则由此产生的$ \ mathrm {mqrg}（1）$包含在$ \ cdot \ cdot \ cdot \ cdot \ cdot \ cl pp} $ {pp} $ {pp} $ {pp} $中，运算符应用于$ \ mathrm {pp} $）。
This paper studies complexity theoretic aspects of quantum refereed games, which are abstract games between two competing players that send quantum states to a referee, who performs an efficiently implementable joint measurement on the two states to determine which of the player wins. The complexity class $\mathrm{QRG}(1)$ contains those decision problems for which one of the players can always win with high probability on yes-instances and the other player can always win with high probability on no-instances, regardless of the opposing player's strategy. This class trivially contains $\mathrm{QMA} \cup \text{co-}\mathrm{QMA}$ and is known to be contained in $\mathrm{PSPACE}$. We prove stronger containments on two restricted variants of this class. Specifically, if one of the players is limited to sending a classical (probabilistic) state rather than a quantum state, the resulting complexity class $\mathrm{CQRG}(1)$ is contained in $\exists\cdot\mathrm{PP}$ (the nondeterministic polynomial-time operator applied to $\mathrm{PP}$); while if both players send quantum states but the referee is forced to measure one of the states first, and incorporates the classical outcome of this measurement into a measurement of the second state, the resulting class $\mathrm{MQRG}(1)$ is contained in $\mathrm{P}\cdot\mathrm{PP}$ (the unbounded-error probabilistic polynomial-time operator applied to $\mathrm{PP}$).
