In this work we focus on two classes of games: xor nonlocal games and xor* sequential games with monopartite resources. xor games have been widely studied in the literature of nonlocal games, and we introduce xor* games as their natural counterpart within the class of games where a resource system is subjected to a sequence of controlled operations and a final measurement. Examples of xor* games are $2\ensuremath{\rightarrow}1$ quantum random access codes (QRAC) and the chsh* game introduced by Henaut et al. [Phys. Rev. A 98, 060302 (2018)]. We prove, using the diagrammatic language of process theories, that under certain assumptions these two classes of games can be related via an explicit theorem that connects their optimal strategies, and so their classical (Bell) and quantum (Tsirelson) bounds. We also show that two of such assumptions, the reversibility of transformations and the bidimensionality of the resource system in the xor* games, are strictly necessary for the theorem to hold by providing explicit counterexamples. We conclude with several examples of pairs of xor/xor* games and by discussing in detail the possible resources that power the quantum computational advantages in xor* games.
In this work we focus on two classes of games: xor nonlocal games and xor* sequential games with monopartite resources. xor games have been widely studied in the literature of nonlocal games, and we introduce xor* games as their natural counterpart within the class of games where a resource system is subjected to a sequence of controlled operations and a final measurement. Examples of xor* games are 2\ensuremath→1 quantum random access codes (QRAC) and the chsh* game introduced by Henaut et al. [Phys. Rev. A 98, 060302 (2018)]. We prove, using the diagrammatic language of process theories, that under certain assumptions these two classes of games can be related via an explicit theorem that connects their optimal strategies, and so their classical (Bell) and quantum (Tsirelson) bounds. We also show that two of such assumptions, the reversibility of transformations and the bidimensionality of the resource system in the xor* games, are strictly necessary for the theorem to hold by providing explicit counterexamples. We conclude with several examples of pairs of xor/xor* games and by discussing in detail the possible resources that power the quantum computational advantages in xor* games.
Nonlocal games play a crucial role in quantum information theory and have numerous applications in certification and cryptographic protocols. Kalai et al. (STOC 2023) introduced a procedure to compile a nonlocal game into a single-prover interactive proof, using a quantum homomorphic encryption scheme, and showed that their compilation method preserves the classical bound of the game. Natarajan and Zhang (FOCS 2023) then showed that the quantum bound is preserved for the specific case of the CHSH game. Extending the proof techniques of Natarajan and Zhang, we show that the compilation procedure of Kalai et al. preserves the quantum bound for two classes of games: bipartite XOR games and a higher dimensional generalization of CHSH (the SATWAP inequality), that we refer to as d-outcome CHSH games. We also establish that, for any pair of qubit measurements, there exists a compiled XOR game such that its near-optimal winning probability serves as a robust selftest for that particular pair of measurements. Finally, we derive computational self-testing of three anticommuting qubit observables, based on the compilation of the nonlocal game corresponding to the so-called elegant Bell inequality.
Nonlocal games provide a unified framework for studying the distinction between classical, quantum, and more general no-signaling correlations. In this work, we develop this perspective by connecting the Bell-locality framework to several complementary mathematical representations of nonlocal games and quantum strategies. We begin with local hidden-variable models, the CHSH inequality, and the role of Bell nonlocality as a device-independent witness of entanglement, and then introduce nonlocal games through the standard predicate/verifier formalism.
We next examine a set of representative examples, including XOR games, the GHZ game, graph-based coloring games, the Mermin-Peres magic square game, and Hardy's paradox as a related logical manifestation of nonlocality. Building on this foundation, we compare four closely related representation frameworks: conditional-probability and correlation descriptions, Bell-functional formulations, entangled-value optimization, and the quantum-operator approach together with the Navascues-Pironio-Acin (NPA) hierarchy. These viewpoints are then instantiated for the CHSH, magic square, and GHZ games, showing how each representation emphasizes a different aspect of the same underlying task.
Taken together, these examples show that nonlocal games can be studied simultaneously as geometric objects in correlation space, optimization problems over entangled resources, and operator-theoretic constructions. This multi-representation viewpoint clarifies the relation between Bell inequality violations, perfect quantum strategies, pseudo-telepathy, and semidefinite relaxations of quantum correlations.
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a “nice'' sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.
Nonlocal games provide a unified framework for studying the distinction between classical, quantum, and more general no-signaling correlations. This review connects the Bell-locality framework to several complementary mathematical representations of nonlocal games and quantum strategies. We begin with local hidden-variable models, the CHSH inequality, and the role of Bell nonlocality as a device-independent witness of entanglement. We then introduce nonlocal games through the standard predicate/verifier formalism and discuss representative examples, including XOR games, the GHZgame, graph-based colouring games, the Mermin–Peres magic square game, and Hardy’s paradox as a related logical manifestation of nonlocality. The central contribution of the article is a comparative organisation of four closely related representation frameworks: conditional-probability andcorrelation descriptions, Bell-functional formulations, entangled-value optimisation, and the quantum-operator approach together with the Navascu´es–Pironio–Ac´ın hierarchy. These viewpoints are instantiated for the CHSH, magic square, and GHZ games, showing how each representation emphasises a different aspect of the same underlying task. The resulting synthesis clarifies the relation between Bell inequality violations, perfect quantum strategies, pseudo-telepathy, and semidefinite relaxations of quantum correlations.
Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, XOR∗, compiled XOR, XOR∗, and strong parallel repetiton of XOR, XOR∗, and FFL games
We characterize exact, and approximate, optimality of games that players can interact with using quantum strategies. In comparison to a previous work of the author, arXiv: 2311.12887, which applied a 2016 framework due to Ostrev for constructing error bounds beyond CHSH and XOR games, in addition to the existence of well-posed semidefinite programs for determining primal feasible solutions, along with quantum-classical duality gaps, it continues to remain of interest to further develop the construction of error bounds, and related objects, to game-theoretic settings with several participants. In such settings, one encounters a rich information theoretic landscape, not only from the fact that there exists a significantly larger combinatorial space of possible strategies for each player, but also several opportunities for pronounced quantum advantage. We conclude this effort by describing other variants of other possible strategies, as proposed sources for quantum advantage, in XOR∗, compiled XOR∗, and strong parallel repetition variants of XOR∗ games.
Optimal, and approximately optimal, quantum strategies for XOR∗ and FFL games
We analyze optimal, and approximately optimal, quantum strategies in two non-local settings based upon previous investigations of the XOR and CHSH games. By building upon previous arguments due to Ostrev in 2016, {\color{blue}[37]}, which characterized approximately optimal, and optimal, strategies that players Alice and Bob can adopt for increasing their respective winning probabilities, we identify additional applications of the framework for analyzing prospective quantum advantage in other game-theoretic settings. In particular, while it is possible for Alice and Bob to realize quantum advantage if they adopt strategies that are dependent upon entanglement, two-dimensional resource systems, and reversible transformations, the magnitude of the duality gap between the performance of classical and quantum strategies has not yet been classified from the perspective of error bounds. Such bounds are not only dependent upon the winning probability if Alice and Bob leverage entanglement in their strategies but also upon a suitably defined representation-theoretic intertwining operation.