Quantum communication can increase cheating success under repeated games
Quantum interaction can superactivate cheating under parallel repetition
Computational Complexity
Summary
In some games where players try to prove something using quantum communication, repeating the same game multiple times usually makes cheating harder. However, the authors found that when the communication is quantum, repeating the games can actually help dishonest players win perfectly, even if they couldn't win as well in a single game. This happens because repeating the game gives players extra quantum resources that they can use together across all repeats. The authors also show that if the players share entanglement beforehand, this problem does not happen for certain simple protocols.
What this means in practice
- •For quantum protocol designers: Avoid quantum communication setups where repeated executions can inadvertently help cheating strategies succeed perfectly.
- •For quantum communication engineers: Design communication protocols that account for superactivation effects preventing soundness degradation under repetition.
A theory result. No direct application yet.
Authors
Archishna Bhattacharyya, Laura Mančinska, Yuming Zhao
Abstract
We study interactive multiprover games and many-round protocols in which the communication between the verifier and the provers is quantum. Parallel repetition is known to suppress soundness error of classical two-prover games arbitrarily close to zero, as shown by Raz (STOC '95), even with quantum strategies as shown by Yuen (ICALP '16), and Bavarian, Vidick and Yuen (STOC '17). Yet, we show that quantum communication can have the opposite, unexpected effect. Specifically, we exhibit a one-round quantum game and two-round $\mathsf{QMIP}$ protocols whose local (unentangled) value is strictly less than one for a single instance, yet equals one under $n$-fold parallel repetition for every $n \geq 2$. The key is that parallel repetition not only imposes additional winning conditions but also supplies additional quantum resources as entanglement in the exchanged states can be exploited jointly across copies. Our multiround examples build on superactivation of zero-error capacities of quantum channels. To establish this connection, we introduce quantum games and interactive protocols which capture the one-shot zero-error classical and quantum capacities, both with and without entanglement assistance. Our constructions use quantum-state verification and a teleportation-based reduction from two rounds to one. In contrast, when shared entanglement is allowed, we show that parallel repetition cannot increase the entangled value when at most $3$ messages are exchanged, consistent with classical results of Bellare, Impagliazzo and Naor (FOCS '97), and that of single-prover systems by Kitaev and Watrous (STOC '00). Combining this monotonicity with our quantum game-channel correspondence, we show that entanglement-assisted zero-error classical and quantum capacities cannot be superactivated.