We describe a two-player non-local game, with a fixed small number of questions and answers, such that an ϵ -close to optimal strategy requires an entangled state of dimension 2 Ω ( ϵ − 1 / 8 ) . Our non-local game is inspired by the three-player non-local game of Ji, Leung and Vidick \cite{ji2018three}. It reduces the number of players from three to two, as well as the question and answer set sizes. Moreover, it provides an (arguably) elementary proof of the non-closure of the set of quantum correlations, based on embezzlement and self-testing. In contrast, previous proofs \cite{slofstra2019set, dykema2017non, musat2018non} involved representation theoretic machinery for finitely-presented groups and C ∗ -algebras.
We describe a two-player non-local game, with a fixed small number of questions and answers, such that an ϵ -close to optimal strategy requires an entangled state of dimension 2 Ω ( ϵ − 1 / 8 ) . Our non-local game is inspired by the three-player non-local game of Ji, Leung and Vidick \cite{ji2018three}. It reduces the number of players from three to two, as well as the question and answer set sizes. Moreover, it provides an (arguably) elementary proof of the non-closure of the set of quantum correlations, based on embezzlement and self-testing. In contrast, previous proofs \cite{slofstra2019set, dykema2017non, musat2018non} involved representation theoretic machinery for finitely-presented groups and C ∗ -algebras.
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 show that the optimal commuting operator correlation for a variant of Coladangelo's two-player generalized nonlocal game, based on the embezzlement of entanglement, is a commuting operator self-test. Our result gives the first correlation self-test for an exact entanglement embezzlement protocol in the commuting operator framework. Because the unique optimal correlation necessitates the exact embezzlement of entanglement, the correlation is unrealizable using quantum tensor-product models, even if the local spaces are allowed to be infinite dimensional. As such, our result provides an example of a commuting operator self-test where the Hilbert space shared by the two parties cannot be factored into a tensor-product of local spaces that is compatible with the local measurement operators. Our main proof technique relies on Harris' unique abstract state characterization of exact embezzlement of entanglement involving Cuntz algebras.
We reduce Lalonde's pseudo-telepathy inner product game from six to five dimensions, keeping its four Alice questions and three Bob questions and reducing each answer alphabet to five. We prove that the reduced game self-tests its nonmaximally entangled state and all 35 measurement effects. The self-test is also robust: for a strategy winning with probability at least 1−ε we obtain dext≤min{1,221ε}, where dext=1−Ξ and Ξ is the optimal squared fidelity with the reference state under local extraction channels. A compactness argument then gives simultaneous qualitative robustness for all measurement actions on the state under common local isometries. As a consequence of the self-test, no maximally entangled state of any finite dimension can win the game perfectly.
In a recent landmark result [Ji et al., arXiv:2001.04383 (2020)], it was shown that approximating the value of a two-player game is undecidable when the players are allowed to share quantum states of unbounded dimension. In this paper, we study the computational complexity of two-player games when the dimension of the quantum systems is bounded by T. More specifically, we give a semidefinite program of size exp(𝒪(T^{12}(log²(AT)+log(Q)log(AT))/ε²)) to compute additive ε-approximations on the value of two-player free games with T× T-dimensional quantum entanglement, where A and Q denote the number of answers and questions of the game, respectively. For fixed dimension T, this scales polynomially in Q and quasi-polynomially in A, thereby improving on previously known approximation algorithms for which worst-case run-time guarantees are at best exponential in Q and A. For the proof, we make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints that we derive via quantum entropy inequalities.
We exhibit non-closedness at perfect play for normal injective hosts: an explicit finite two-player game with 0/1 scoring has a perfect commuting-operator correlation approached by finite-dimensional quantum correlations, while no perfect strategy has a normal marginal on an injective von Neumann algebra of either player. The game has 561 Alice questions, 157 Bob questions, 3,696 sampled pairs and at most 20 answers per question. Perfect play is realized on a matrix amplification of the Bellaterra critical-KMS factor of type III with parameter 1/2. After restricting to the support of the chosen normal marginal, every perfect strategy yields a modular Cuntz pair and six self-similar relations that force the canonical trace on the free product of three groups of order two. The resulting noninjective group von Neumann algebra is an expected subalgebra of that support corner, with a faithful normal state-preserving expectation. A two-sided POVM lift through a matrix ultraproduct proves approximation by finite systems. Consequently correlations admitting normal injective hosts are not closed. Under the explicit hypotheses of Halvorson's Proposition 2.31, locally normal quantum-field-theory strategies cannot win exactly. We also formulate a KMS-face criterion for complete modular presentations. Exact arithmetic certificates check every supported losing event; the forcing proof applies to arbitrary normal strategies.