Local simultaneous state discrimination (LSSD) is a recently introduced problem in quantum information processing. Its classical version is a non-local game played by non-communicating players against a referee. Based on a known probability distribution, the referee generates one input for each of the players and keeps one secret value. The players have to guess the referee's value and win if they all do so. For this game, we investigate the advantage of no-signalling strategies over classical ones. We show numerically that for three players and binary values, no-signalling strategies cannot provide any improvement over classical ones. For a certain LSSD game based on a binary symmetric channel, we show that no-signalling strategies are strictly better when multiple simultaneous instances of the game are played. Good classical strategies for this game can be defined by codes, and good no-signalling strategies by list-decoding schemes. We expand this example game to a class of games defined by an arbitrary channel, and extend the idea of using codes and list decoding to define strategies for multiple simultaneous instances of these games. Finally, we give an expression for the limit of the exponent of the classical winning probability, and show that no-signalling strategies based on list-decoding schemes achieve this limit.
In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game
G with optimal winning probability
1−α and its repeated version
Gn (in which
n games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this work the case of multiplayer non-signalling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players we prove a threshold theorem stating that the probability that non-signalling players win more than a fraction
1−α+β of the
n games is exponentially small in
nβ2, for every
0≤β≤α. For games with incomplete support we derive a similar statement, for a slightly modified form of repetition. The result is proved using a new technique, based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.
In the context of multiplayer games, the parallel repetition problem can be phrased as follows: given a game G with optimal winning probability 1 - α and its repeated version Gn(in which n games are played together, in parallel), can the players use strategies that are substantially better than ones in which each game is played independently? This question is relevant in physics for the study of correlations and plays an important role in computer science in the context of complexity and cryptography. In this paper, the case of multiplayer non-signaling games is considered, i.e., the only restriction on the players is that they are not allowed to communicate during the game. For complete-support games (games where all possible combinations of questions have non-zero probability to be asked) with any number of players, we prove a threshold theorem stating that the probability that non-signaling players win more than a fraction 1-α+β of the n games is exponentially small in nβ2for every 0 ≤ β ≤ α. For games with incomplete support, we derive a similar statement for a slightly modified form of repetition. The result is proved using a new technique based on a recent de Finetti theorem, which allows us to avoid central technical difficulties that arise in standard proofs of parallel repetition theorems.