Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userContinuous input nonlocal games
107
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a family of nonlocal games in which the inputs the players receive are continuous. We study three representative members of the family. For the first two a team sharing quantum correlations (entanglement) has an advantage over any team restricted to classical correlations. We conjecture that this is true for the third member of the family as well.
rate research
Read More
We introduce a simple transformation on two-player nonlocal games, called anchoring, and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the Feige-Kilian transformation (SICOMP 2000), and has the property that if the quantum value of the original game $G$ is $v$ then the quantum value of the anchored game $G_bot$ is $1 - (1 - alpha)^2 cdot (1 - v)$ where $alpha$ is a parameter of the transformation. In particular the anchored game has quantum value $1$ if and only if the original game $G$ has quantum value $1$. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.
Recent developments surrounding resource theories have shown that any quantum state or measurement resource, with respect to a convex (and compact) set of resourceless objects, provides an advantage in a tailored subchannel or state discrimination task, respectively. Here we show that an analogous, more general result is also true in the case of dynamical quantum resources, i.e., channels and instruments. In the scenario we consider, the tasks associated to a resource are input-output games. The advantage a resource provides in these games is naturally quantified by a generalized robustness measure. We illustrate our approach by applying it to a broad collection of examples, including classical and measure-and-prepare channels, measurement and channel incompatibility, LOCC operations, and steering, as well as discussing its applicability to other resources in, e.g., quantum thermodynamics. We finish by showing that our approach generalizes to higher-order dynamics where it can be used, for example, to witness causal properties of supermaps.
We bound separations between the entangled and classical values for several classes of nonlocal $t$-player games. Our motivating question is whether there is a family of $t$-player XOR games for which the entangled bias is $1$ but for which the classical bias goes down to $0$, for fixed $t$. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-$m$ games and show that their classical value is always at least $frac{1}{m} + frac{m-1}{m} t^{1-t}$. Secondly, for free XOR games, in which the input distribution is of product form, we show $beta(G) geq beta^*(G)^{2^t}$ where $beta(G)$ and $beta^*(G)$ are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is $1-epsilon$ then the classical value is at least $1-mathcal{O}(sqrt{epsilon log k})$ where $k$ is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms.
This paper considers a special class of nonlocal games $(G,psi)$, where $G$ is a two-player one-round game, and $psi$ is a bipartite state independent of $G$. In the game $(G,psi)$, the players are allowed to share arbitrarily many copies of $psi$. The value of the game $(G,psi)$, denoted by $omega^*(G,psi)$, is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states $psi$. For a noisy maximally entangled state $psi$, a two-player one-round game $G$ and an arbitrarily small precision $epsilon>0$, this paper proves an upper bound on the number of copies of $psi$ for the players to win the game with a probability $epsilon$ close to $omega^*(G,psi)$. Hence, it is feasible to approximately compute $omega^*(G,psi)$ to an arbitrarily precision. Recently, a breakthrough result by Ji, Natarajan, Vidick, Wright and Yuen showed that it is undecidable to approximate the values of nonlocal games to a constant precision when the players preshare arbitrarily many copies of perfect maximally entangled states, which implies that $mathrm{MIP}^*=mathrm{RE}$. In contrast, our result implies the hardness of approximating nonlocal games collapses when the preshared maximally entangled states are noisy. The paper develops a theory of Fourier analysis on matrix spaces by extending a number of techniques in Boolean analysis and Hermitian analysis to matrix spaces. We establish a series of new techniques, such as a quantum invariance principle and a hypercontractive inequality for random operators, which we believe have further applications.
The continuous patrolling game studied here was first proposed in Alpern et al. (2011), which studied a discrete time game where facilities to be protected were modeled as the nodes of a graph. Here we consider protecting roads or pipelines, modeled as the arcs of a continuous network $Q$. The Attacker chooses a point of $Q$ to attack during a chosen time interval of fixed duration (the attack time, $alpha$). The Patroller chooses a unit speed path on $Q$ and intercepts the attack (and wins) if she visits the attacked point during the attack time interval. Solutions to the game have previously been given in certain special cases. Here, we analyze the game on arbitrary networks. Our results include the following: (i) a solution to the game for any network $Q$, as long as $alpha$ is sufficiently short, generalizing the known solutions for circle or Eulerian networks and the network with two nodes joined by three arcs; (ii) a solution to the game for all tree networks that satisfy a condition on their extremities. We present a conjecture on the solution of the game for arbitrary trees and establish it in certain cases.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
