ﻻ يوجد ملخص باللغة العربية
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.
We consider two aspects of quantum game theory: the extent to which the quantum solution solves the original classical game, and to what extent the new solution can be obtained in a classical model.
We introduce various measures of forward classical communication for bipartite quantum channels. Since a point-to-point channel is a special case of a bipartite channel, the measures reduce to measures of classical communication for point-to-point ch
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 par
We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix $Ainmathbb{R}^{ntimes d}$, sublinear algorithms for the matrix game $min_
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 res