We associate mirror games with the universal game algebra and use the *-representation to describe quantum commuting operator strategies. We provide an algebraic characterization of whether or not a mirror game has perfect commuting operator strategies. This new characterization uses a smaller algebra introduced by Paulsen and others for synchronous games and the noncommutative Nullstellensatz developed by Cimpric, Helton and collaborators. An algorithm based on noncommutative Gröbner basis computation and semidefinite programming is given for certifying that a given mirror game has no perfect commuting operator strategies.
We study a class of nonlocal games, called transitive games, for which the set of perfect strategies forms a semigroup. We establish several interesting correspondences of bisynchronous transitive games with the theory of compact quantum groups. In particular, we associate a quantum permutation group with each bisynchronous transitive game and vice versa. We prove that the existence of a C*-strategy, the existence of a quantum commuting strategy, and the existence of a classical strategy are all equivalent for bisynchronous transitive games. We then use some of these correspondences to establish necessary and sufficient conditions for some classes of correlations, that arise as perfect strategies of transitive games, to be nonlocal.
A perfect strategy is one that allows the mutually in-communicated players of a nonlocal game to win every trial of the game. Perfect strategies are basic tools for some fundamental results in quantum computation and crucial resources for some applications in quantum information. Here, we address the problem of producing qudit-qudit perfect quantum strategies with a small number of settings. For that, we exploit a recent result showing that any perfect quantum strategy induces a Kochen-Specker set. We identify a family of KS sets in even dimension
d≥6 that, for many dimensions, require the smallest number of orthogonal bases known:
d+1. This family was only defined for some
d. We first extend the family to infinitely many more dimensions. Then, we show the optimal way to use each of these sets to produce a bipartite perfect strategy with minimum input cardinality. As a result, we present a family of perfect quantum strategies in any
(2,d−1,d) Bell scenario, with
d=2kpm for
p prime,
m≥k≥0 (excluding
m=k=0),
d=8p for
p≥19,
d=kp for
p>((k−2)2k−2)2 whenever there exists a Hadamard matrix of order
k, other sporadic examples, as well as a recursive construction that produces perfect quantum strategies for infinitely many dimensions
d from any dimension
d′ with a perfect quantum strategy. We identify their associated Bell inequalities and prove that they are not tight, which provides a second counterexample to a conjecture of 2007.
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.
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.
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.