First, we consider the problem of deciding whether a nonlocal game admits a perfect entangled strategy that uses projective measurements on a maximally entangled shared state. Via a polynomial-time Karp reduction, we show that independent set games are the hardest instances of this problem. Secondly, we show that if every independent set game whose entangled value is equal to one admits a perfect entangled strategy, then the same holds for all symmetric synchronous games. Finally, we identify combinatorial lower bounds on the classical and entangled values of synchronous games in terms of variants of the independence number of appropriate graphs. Our results suggest that independent set games might be representative of all nonlocal games when dealing with questions concerning perfect entangled strategies.
First, we consider the problem of deciding whether a nonlocal game admits a perfect entangled strategy that uses projective measurements on a maximally entangled shared state. Via a polynomial-time Karp reduction, we show that independent set games are the hardest instances of this problem. Secondly, we show that if every independent set game whose entangled value is equal to one admits a perfect entangled strategy, then the same holds for all symmetric synchronous games. Finally, we identify combinatorial lower bounds on the classical and entangled values of synchronous games in terms of variants of the independence number of appropriate graphs. Our results suggest that independent set games might be representative of all nonlocal games when dealing with questions concerning perfect entangled strategies.
One of the longstanding open problems in quantum nonlocality is to determine if maximally entangled states are complete for bipartite pseudo-telepathic games: namely, if every nonlocal game which admits a perfect entangled strategy admits such a strategy which uses a maximally entangled state. We exhibit a counterexample to this in the form of a bipartite nonlocal game with input sets of size 4 and 3 and output sets both of size 6. This game is part of a new class of nonlocal games, which we call inner product games, which could be of independent interest.
We consider a class of nonlocal games that are related to binary constraint systems (BCSs) in a manner similar to the games implicit in the work of Mermin [N.D. Mermin, "Simple unified form for the major no-hidden-variables theorems," Phys. Rev. Lett., 65(27):3373-3376, 1990], but generalized to n binary variables and m constraints. We show that, whenever there is a perfect entangled protocol for such a game, there exists a set of binary observables with commutations and products similar to those exhibited by Mermin. We also show how to derive upper bounds strictly below 1 for the the maximum entangled success probability of some BCS games. These results are partial progress towards a larger project to determine the computational complexity of deciding whether a given instance of a BCS game admits a perfect entangled strategy or not.
How much entanglement does near-optimal play of a two-player nonlocal game require? We give an explicit binary linear system game, with 1687 equations in 1993 variables and at most three variables in each equation, whose quantum value is one, and in which every strategy that wins with probability 1−ε needs entanglement entropy ε−1+o(1), hence local dimension exp(ε−1+o(1)). The same bound holds for the entanglement of formation of mixed strategies, and a strategy on a maximally entangled state of local dimension exp(Cε−1log(1/ε)) suffices, so the exponent is sharp. For explicit two-player games of quantum value one, the best previous lower bound was polynomial in 1/ε. The game comes from a finitely generated, elementary amenable group: a lamplighter whose lamps are Pauli pairs indexed by finite sets of points on the three rays on which Houghton's group acts. Exponentially many of these pairs share one central involution, yet the relation that any two of them commute can be derived from a fixed finite set of relations in a number of steps only quasi-polynomial in the number of points. Two tools may be of independent use. The first counts qubits from approximate Pauli relations measured in an arbitrary state, with the errors of different pairs adding in squares. The second identifies, in both directions and at the natural precision ε, the near-optimal strategies of a linear system game with approximate representations of its solution group measured in the players' actual state, so that no power of ε is lost by passing to a flat state. The same tools give sharp rates for two earlier examples: the CHSH(n) games need Θ(min(n,1/ε)) ebits, and the linear system game of Slofstra and Vidick needs local dimension Θ(ε−1/2).
We identify a structural mechanism by which perfect play in a nonlocal game requires and self-tests a specific non-maximally entangled state. To this end, we construct a Flagged Magic-Square game by extending the standard Magic-Square game with an additional ``flag'' outcome and two additional questions for each player. The game admits a perfect strategy using a state with Schmidt coefficients proportional to (1,2,2,2,2). We give a direct algebraic proof that maximally entangled strategies have winning probability bounded away from one, independently of dimension. Moreover, the game self-tests this state, providing an example of a two-party pseudo-telepathy game that certifies a specific non-maximally entangled state. Our construction illustrates how adding suitable constraints to a rigid measurement geometry can enforce specific Schmidt ratios and provides a modular route to further self-tests based on other rigid pseudo-telepathy games.
We establish a general game-to-channel reduction that transfers separations in the game model to one-shot zero-error communication over classical channels. Applied to the Flagged Magic-Square game, it yields a classical channel for which entanglement permits the zero-error transmission of ten messages in a single use, whereas any finite-dimensional maximally entangled resource permits at most nine. Thus, maximally entangled states are not a universally optimal entanglement resource for zero-error communication over classical noisy channels.
Abstract This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the players. The quantum value of a fully quantum nonlocal game is the supremum of the probability that they win the game, where the supremum is taken over all the possible entangled states shared between the players and all the valid quantum operations performed by the players. The seminal work MIP∗=RE~\cite{JNVWY'20,JNVWYuen'20} implies that it is undecidable to approximate the quantum value of a fully nonlocal game. This still holds even if the players are only allowed to share (arbitrarily many copies of) maximally entangled states. This paper investigates the case that the shared maximally entangled states are noisy. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value. This implies that it is decidable to approximate the quantum values of these games. Hence, the hardness of approximating the quantum value of a fully quantum nonlocal game is not robust against the noise in the shared states. This paper is built on the framework for the decidability of non-interactive simulations of joint distributions~\cite{7782969,doi:10.1137/1.9781611975031.174,Ghazi:2018:DRP:3235586.3235614} and generalizes the analogous result for nonlocal games in~\cite{qin2021nonlocal}. We extend the theory of Fourier analysis to the space of super-operators and prove several key results including an invariance principle and a dimension reduction for super-operators. These results are interesting in their own right and are believed to have further applications.
We provide a complete structural characterization of perfect quantum strategies for arbitrary quantum magic rectangle games. We derive necessary and sufficient conditions that jointly constrain the shared state and measurement operators, establishing a unified analytical framework for perfect nonlocal strategies in this setting. Our results show that all perfect quantum solution states (PQSS) must exhibit a specific algebraic--combinatorial structure, ruling out a priori assumptions about particular entangled resources and clarifying the full class of states compatible with perfect correlations. We further show that perfect quantum strategies do not exist for 2×n quantum magic rectangle games with odd n, and introduce a corresponding quantum magic rectangle inequality to characterize optimal non-perfect strategies. While our results are structural, they may provide a foundation for future developments in quantum information and quantum cryptography based on perfect nonlocal correlations.