arXiv:2609.31223
Quantum interaction can superactivate cheating under parallel repetition
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.
AI Summary
The paper asks whether parallel repetition suppresses cheating when verifiers and noncommunicating provers exchange quantum messages. It constructs a one-round two-prover quantum game and two-round interactive protocols whose unentangled value satisfies $\omega(G)<1$, yet $\omega(G^{\otimes n})=1$ for every $n\geq2$. Winning requires passing every repeated instance, rather than at least one as in quantum hedging. The one-round example reduces to exact bipartite pure-state conversion by local channels. Its Schmidt probability vectors cannot factor as $p=q\otimes r$, but their tensor powers admit the corresponding factorization for two and three copies, hence every larger number. An explicit polynomial construction supplies these vectors. The multiround examples instead use known superactivation of unassisted zero-error channel capacities and a new “one-time-pad direct sum” channel construction. Protocols identify perfect success with zero-error classical or quantum transmission; a teleportation-based reduction also relates sequential protocols to one-round games. For entanglement-assisted strategies, the paper proves $\omega^*(G_1\otimes G_2)\leq\min\{\omega^*(G_1),\omega^*(G_2)\}$ for one-round quantum games and analogous monotonicity for three-message protocols. It also establishes non-superactivation of entanglement-assisted zero-error classical capacity and asymptotic quantum capacity. The one-shot quantum capacity is explicitly excluded: two uses of a noiseless classical-bit channel can teleport a qubit although one use cannot. The counterexamples do not quantify a uniform single-instance soundness gap. Whether entangled-value superactivation occurs beyond three messages, and which nontrivial restrictions permit safe soundness amplification, remain open.
Error found: The proof of the ancillary classical-capacity non-superactivation theorem thm:C-imp-sup omits a necessary implication from perfect decoding through the product channel to perfect play in the product teleportation game, whose additional single-success Bell branches impose decoding requirements not covered by that argument.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 27 pages