We introduce a three-player nonlocal game, with a finite number of classical questions and answers, such that the optimal success probability of 1 in the game can only be achieved in the limit of strategies using arbitrarily high-dimensional entangled states. Precisely, there exists a constant 0<c≤1 such that to succeed with probability 1−ε in the game it is necessary to use an entangled state of at least Ω(ε−c) qubits, and it is sufficient to use a state of at most O(ε−1) qubits. The game is based on the coherent state exchange game of Leung et al.\ (CJTCS 2013). In our game, the task of the quantum verifier is delegated to a third player by a classical referee. Our results complement those of Slofstra (arXiv:1703.08618) and Dykema et al.\ (arXiv:1709.05032), who obtained two-player games with similar (though quantitatively weaker) properties based on the representation theory of finitely presented groups and C∗ -algebras respectively.
We introduce a three-player nonlocal game, with a finite number of classical questions and answers, such that the optimal success probability of 1 in the game can only be achieved in the limit of strategies using arbitrarily high-dimensional entangled states. Precisely, there exists a constant 0<c≤1 such that to succeed with probability 1−ε in the game it is necessary to use an entangled state of at least Ω(ε−c) qubits, and it is sufficient to use a state of at most O(ε−1) qubits. The game is based on the coherent state exchange game of Leung et al.\ (CJTCS 2013). In our game, the task of the quantum verifier is delegated to a third player by a classical referee. Our results complement those of Slofstra (arXiv:1703.08618) and Dykema et al.\ (arXiv:1709.05032), who obtained two-player games with similar (though quantitatively weaker) properties based on the representation theory of finitely presented groups and C∗ -algebras respectively.
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.
Quantum entanglement is known to provide a strong advantage in many two-party distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple two-party nonlocal game H, inspired by Lucien Hardy’s paradox. In our game each player has only two possible questions and can provide bit strings of any finite length as answer. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1 − O(d−c ) for some c ≥ 0.13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1 − Ω(d−2 ). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1 − Ω(d−2 ). Finally, we generalize our construction to derive similar results starting from any game G with two questions per player and finite answers sets in which quantum strategies have an advantage.
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).
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 ( Ji et al. MIP ∗ = RE, 2020; Ji et al. Quantum soundness of the classical low individual degree test, 2020) 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 (Ghazi et al. in: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), Los Alamitos, 2016; De et al. in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, 2018; Ghazi et al. Proceedings of the 33rd Computational Complexity Conference, 2018) and generalizes the analogous result for nonlocal games in Qin and Yao (SIAM J Comput 50(6):1800–1891, 2021). 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.
Several variants of nonlocal games have been considered in the study of quantum entanglement and nonlocality. This paper concerns two of these variants, called quantum-classical games and extended nonlocal games. We give a construction of an extended nonlocal game from any quantum-classical game that allows one to translate certain facts concerning quantum- classical games to extended nonlocal games. In particular, based on work of Regev and Vidick, we conclude that there exist extended nonlocal games for which no finite-dimensional entangled strategy can be optimal. While this conclusion is a direct consequence of recent work of Slofstra, who proved a stronger, analogous result for ordinary (non-extended) nonlocal games, the proof based on our construction is considerably simpler, and the construction itself might potentially have other applications in the study of entanglement and nonlocality.