Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input $x_i$ to the $i^{th}$ player who then responds by sending an answer $a_i$ to the referee. The players win if the answers $a_i$ satisfy a condition that may depend on the inputs $x_i$ . Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study of non-local games in a worst-case scenario when the referee's probability distribution is unknown and study several non-local games in this scenario.Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input $x_i$ to the $i^{th}$ player who then responds by sending an answer $a_i$ to the referee. The players win if the answers $a_i$ satisfy a condition that may depend on the inputs $x_i$. Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study of non-local games in a worst-case scenario when the referee's probability distribution is unknown and study several non-local games in this scenario.

arXiv:1112.2856Dec 13, 20111 citation

Perfect Strategies for Non-Local Games

M. Lupini, Laura Mančinska, V. I. Paulsen +5 more

arXiv:1804.06151Mathematical Physics Analysis and GeometryFeb 26, 202026 citations

A Direct Product Theorem for One-Way Quantum Communication

Rahul Jain, Srijita Kundu

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$ . For any $\varepsilon, ζ> 0$ and any $k\geq1$ , we show that $\mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),$ where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $\varepsilon$ and $f^k$ denotes $k$ parallel instances of $f$ . As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})$ where $q$ is a distribution on $\mathcal{X}\times\mathcal{Y}$ anchored on any one side with anchoring probability $ζ$ , then $ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}$ where $ω^*(G)$ represents the entangled value of the game $G$ . This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, ζ> 0$ and any $k\geq1$, we show that \[ \mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),\] where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $\varepsilon$ and $f^k$ denotes $k$ parallel instances of $f$. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})$ where $q$ is a distribution on $\mathcal{X}\times\mathcal{Y}$ anchored on any one side with anchoring probability $ζ$, then \[ ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}\] where $ω^*(G)$ represents the entangled value of the game $G$. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.

arXiv:2008.08963Leibniz international proceedings in informaticsAug 20, 20201 citation

On symmetric nonlocal games

Andris Ambainis, Dmitry Kravchenko, Nikolay Nahimov +2 more

Theoretical Computer ScienceMar 25, 20132 citations

Additive non-Gaussian noise attacks on the scalar Costa scheme (SCS)

Roman Tzschoppe, Robert Bäuml, Robert F. H. Fischer +2 more

The additive attack public mutual information game is explicitly solved for one of the simplest quantization based watermarking schemes, the scalar Costa scheme (SCS). It is a zero-sum game played between the embedder and the attacker, and the payoff function is the mutual information. The solution of the game, a subgame perfect nash equilibrium, is found by backward induction. Therefore, the Blahut-Arimoto algorithm is employed for numerically optimizing the mutual information over noise distributions. Although the worst case distribution is in general strongly non-Gaussian, the capacity degradation compared to a suboptimal Gaussian noise attack is quite small. The loss, if the embedder optimizes SCS for a Gaussian attack but the worst case attack is employed, is negligible.The additive attack public mutual information game is explicitly solved for one of the simplest quantization based watermarking schemes, the scalar Costa scheme (SCS). It is a zero-sum game played between the embedder and the attacker, and the payoff function is the mutual information. The solution of the game, a subgame perfect nash equilibrium, is found by backward induction. Therefore, the Blahut-Arimoto algorithm is employed for numerically optimizing the mutual information over noise distributions. Although the worst case distribution is in general strongly non-Gaussian, the capacity degradation compared to a suboptimal Gaussian noise attack is quite small. The loss, if the embedder optimizes SCS for a Gaussian attack but the worst case attack is employed, is negligible.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEMar 21, 20059 citations

Zero-sum games

Physics WorldApr 1, 19990 citations

x_i

to the

i^{th}

player who then responds by sending an answer

a_i

to the referee. The players win if the answers

a_i

satisfy a condition that may depend on the inputs

x_i

. Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study of non-local games in a worst-case scenario when the referee's probability distribution is unknown and study several non-local games in this scenario.

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation

f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}

. For any

\varepsilon, ζ> 0

and any

k\geq1

, we show that

\mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),

where

\mathrm{Q}^1_{\varepsilon}(f)

represents the one-way entanglement-assisted quantum communication complexity of

f

with worst-case error

\varepsilon

and

f^k

denotes

k

parallel instances of

f

. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game

G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})

where

q

is a distribution on

\mathcal{X}\times\mathcal{Y}

anchored on any one side with anchoring probability

ζ

, then

ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}

where

ω^*(G)

represents the entangled value of the game

G

. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.