Related papers: Connecting XOR and XOR* games

Connecting XOR and XOR* games

URL: http://arxiv.org/abs/2210.00397v4
Date: Mon, 5 Feb 2024 16:20:48 GMT
Title: Connecting XOR and XOR* games
Authors: Lorenzo Catani, Ricardo Faleiro, Pierre-Emmanuel Emeriau, Shane Mansfield, Anna Pappa
Abstract summary: We focus on two classes of games: XOR nonlocal games and XOR* sequential games with monopartite resources. We prove that under certain assumptions these two classes of games can be related via an explicit theorem that connects their optimal strategies.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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\rightarrow 1$ quantum random access codes (QRAC) and the CHSH* game introduced by Henaut et al. in [PRA 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 bi-dimensionality 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.

Related papers

A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
arXiv Detail & Related papers (2024-08-13T08:11:56Z)
Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
arXiv Detail & Related papers (2024-06-23T00:27:28Z)
Quantum bounds for compiled XOR games and $d$-outcome CHSH games [1.099532646524593]
We show that the compilation procedure of Kalai et al. preserves the quantum bound for two classes of games. For any pair of qubit measurements, there exists an XOR game such that its optimal winning probability serves as a self-test for that particular pair of measurements.
arXiv Detail & Related papers (2024-03-08T18:20:21Z)
A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [9.818381970014284]
We show that the compiler proposed by Kalai et al. is sound for any two-player XOR game. Using our techniques, we obtain several additional results, including tight bounds on the compiled value of parallel-repeated XOR games.
arXiv Detail & Related papers (2024-02-27T08:24:21Z)
Reasoning about Causality in Games [63.930126666879396]
Causal reasoning and game-theoretic reasoning are fundamental topics in artificial intelligence. We introduce mechanised games, which encode dependencies between agents' decision rules and the distributions governing the game. We describe correspondences between causal games and other formalisms, and explain how causal games can be used to answer queries that other causal or game-theoretic models do not support.
arXiv Detail & Related papers (2023-01-05T22:47:28Z)
Connes implies Tsirelson: a simple proof [91.3755431537592]
We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
arXiv Detail & Related papers (2022-09-16T13:59:42Z)
On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
arXiv Detail & Related papers (2021-12-09T21:06:52Z)
Quantum guessing games with posterior information [68.8204255655161]
A quantum guessing game with posterior information uses quantum systems to encode messages and classical communication to give partial information after a quantum measurement has been performed. We formalize symmetry of guessing games and characterize the optimal measurements in cases where the symmetry is related to an irreducible representation.
arXiv Detail & Related papers (2021-07-25T19:10:26Z)
Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
Subtraction games are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum games. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms.
arXiv Detail & Related papers (2020-06-12T06:36:07Z)
Quantum one way vs. classical two way communication in XOR games [0.0]
We show an example of a XOR game for which $O(n)$ bits of two way classical communication are needed. We also find a characterization for the value of a XOR game assisted with a limited amount of two way communication.
arXiv Detail & Related papers (2020-03-21T20:30:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.