Quantum interaction can superactivate cheating under parallel repetition

AI summary

Overview

Research area: Quantum information theory and quantum complexity theory — specifically quantum multiprover interactive games and protocols (QMIP), parallel repetition, and zero-error quantum channel capacities.

Technical level: Advanced. The paper assumes familiarity with quantum channels, CPTP maps, entanglement-assisted strategies, and interactive proof complexity classes. The summary below is written in plain language, but the underlying results are technical.

Scope: The paper proves that when communication between a verifier and provers is quantum, parallel repetition can fail completely — a single-copy game that cannot be won perfectly becomes perfectly winnable when played in parallel two or more times.

What This Paper Is About

Parallel repetition is a standard tool: if players cannot win a game with certainty once, playing many independent copies at once should make winning all of them exponentially unlikely. Raz (STOC '95) proved this for classical two-prover games, and Yuen (ICALP '16) and Bavarian, Vidick and Yuen (STOC '17) extended it to quantum strategies. This paper shows that when the questions and answers themselves are quantum states, the opposite can happen: repetition can hand the players extra quantum resources — entanglement contained in the exchanged states — which they can exploit jointly across copies to win perfectly.

The goal is to construct explicit counterexamples, connect them to the known phenomenon of superactivation of quantum channel capacities, and then map out exactly where the failure does and does not occur.

Key Contributions

1. A one-round quantum game that breaks parallel repetition completely. The paper exhibits a quantum game $G$ with local value $\omega(G) < 1$ for a single instance but $\omega(G^n) = 1$ under $n$-fold parallel repetition for every $n \geq 2$ (Theorem 7).

2. Multiround $\mathsf{QMIP}$ counterexamples. The same superactivation of cheating is shown for $\mathsf{QMIP}$ protocols with at least 2 nontrivial rounds of interaction, for the local (unentangled) value (Theorem 24, Corollary 25, Theorem 28). Because these are $\mathsf{QMIP}$ protocols with 2 nontrivial rounds, this gives a further concrete separation between $\mathsf{QMIP}$ and $\mathsf{QMIP}^{*}$.

3. A quantum game–channel correspondence. The authors introduce $\mathsf{QMIP}$ protocols $G$ and $H$, each with 2 nontrivial rounds, that capture one-shot zero-error classical and quantum communication (Definitions 9 and 13), and prove a one-to-one mapping from the zero-error classical and quantum capacities to the classical values, and from the entanglement-assisted capacities to the entangled values (Theorems 10 and 14). This quantises the earlier classical channel–nonlocal game correspondence of [CLMW10].

4. A no-go result for entanglement-assisted settings. When shared entanglement is allowed, parallel repetition cannot increase the entangled value for one-round quantum games (Proposition 4) or for $\mathsf{QMIP}$ protocols exchanging at most 3 messages (Theorem 35), consistent with Bellare–Impagliazzo–Naor (FOCS '97) and Kitaev–Watrous (STOC '00). Combined with the game–channel correspondence, this shows entanglement-assisted zero-error classical and quantum capacities cannot be superactivated (Theorem 30, Corollary 31).

Main Findings

• Perfect cheating from two copies onward. For the one-round quantum game of Theorem 7, $\omega(G) < 1$ while $\omega(G^n) = 1$ for all $n \geq 2$. The mechanism is that the extra copy of the question state supplies precisely the entanglement needed to convert an imperfect one-copy strategy into a perfect strategy for the repeated game, and the same carries through to 3 repetitions and beyond.

• Parallel repetition supplies resources, not just constraints. The paper's explanation is that repetition does not only add winning conditions; it also gives the provers additional quantum states, including the entanglement inside them, which can be exploited jointly across copies.

• Multiround failure for the local value. Theorems 24 and 28 and Corollary 25 extend the phenomenon to $\mathsf{QMIP}$ protocols with at least 2 nontrivial rounds. The authors state that such an extreme violation of parallel repetition for a game or protocol is not known to date, and contrast it with [CJPPG15], which shows parallel repetition is only approximately satisfied for rank-one quantum games — a much weaker consequence.

• The entangled value is protected at short lengths. For the entangled value $\omega^{*}(G)$, superactivated cheating is impossible for one-round quantum games (Proposition 4) and for $\mathsf{QMIP}$ protocols with at most 3 messages exchanged, i.e. 1.5 rounds (Theorem 35). This matches the intuition that provers who already share unbounded entanglement gain nothing from entanglement in question states.

• No superactivation of entanglement-assisted zero-error capacities. Theorem 30 rules out superactivation of entanglement-assisted zero-error classical capacity; Corollary 31 gives the asymptotic case for its quantum analogue. Lemma 29 provides the general tool: if a channel capacity's one-shot version cannot be superactivated, neither can its asymptotic version, via a teleportation-based reduction from two rounds to one (Definition 11, Lemma 12, Definition 15, Lemma 16).

• A construction tool: the one-time-pad direct sum. Definition 21 introduces a direct sum of channels that breaks any correlations between two channel outputs, which the authors use to turn channel superactivation into failures of parallel repetition.

• Cryptographic and complexity consequences. Since parallel repetition is the standard route to soundness amplification and gap amplification, the result removes the possibility of using parallel repetition to amplify soundness even for a single repetition of a quantum game, and poses an obstacle to gap amplification relevant to quantum PCP conjectures. The paper notes that [BQSY24] shows a computationally bounded 4-message $\mathsf{QMIP}$ protocol already faces barriers to parallel repetition, and that [BQSY24] and [LV26] show parallel repetition is respected by single-prover $\mathsf{QIP}$ protocols, in contrast with the counterexample here.

Methodology in Plain English

The authors do not attack games directly. Instead they build a bridge between two areas that are usually studied separately: interactive games with a referee, and communication through noisy quantum channels.

First, they design $\mathsf{QMIP}$ protocols that mirror what a channel can transmit with zero error — one protocol for classical data, one for quantum data, each with and without pre-shared entanglement. Winning such a protocol perfectly corresponds to achieving full capacity. Playing the repeated game in parallel then corresponds to sending information through several joint uses of the channel.

Second, they import known superactivation results from channel theory — cases where two channels each carry zero information but together carry some — into the game setting, using a direct sum construction that severs correlations between the two channel outputs. In the game language, this becomes a strategy that fails on one copy but succeeds on two.

Third, they use quantum-state verification (the SWAP test) and a teleportation-based reduction that collapses two rounds into one, so results about one-round games transfer to multiround protocols and back.

Fourth, they prove the converse direction for entangled provers using monotonicity arguments, showing the entangled value cannot increase with repetition at short message lengths, and then translate that back through the correspondence into a no-superactivation statement for entanglement-assisted capacities.

The authors disclose that an LLM was used to identify the probability vectors required for the proof of Theorem 7.

Why This Matters

Parallel repetition is the workhorse behind soundness amplification, error reduction and hardness of approximation. If it fails this dramatically for quantum interaction, protocol designers cannot assume that repeating a quantum protocol makes it safer — in fact, repeating it can make a cheating strategy perfect rather than negligible.

• Cryptographic error reduction: in protocols where noise corresponds to adversarial side information, a failure of parallel repetition means soundness is not preserved and noise can be amplified in uncontrolled ways, endangering tasks that depend on concurrent execution of interactive proofs.

• Quantum money and related primitives: the paper notes that quantum hedging — where only a subset of repeated instances must be won — already produced attacks on quantum money [MVW13]; the superactivation shown here is a stronger failure and is expected to have stronger consequences.

• Security games and $\mathsf{QMIP}$-based protocols: Theorem 35 covers the 3-message $\mathsf{QMIP}$ model, which the authors describe as cryptographically relevant and as capturing a security game.

• Hardness of approximation and PCP-style gap amplification: the classical PCP theorem relies on parallel repetition to amplify inapproximability; the counterexample removes that route in the quantum setting, which the authors suggest could influence thinking about the quantum PCP conjecture.

Industry relevance: the results matter to anyone building or analysing quantum interactive protocols, quantum cryptography with concurrent sessions, or quantum-safe security proofs — particularly where soundness amplification is assumed to be a black box.

Future Directions

• Safe quantum games. The paper asks how to circumvent the failure and still build sound quantum games, noting that the "anchoring" transformation [BVY17] does this for classical games, and asks whether a quantum analogue exists. A trivial criterion is to require the question state to be separable; the authors state that any nontrivial criterion would be of immediate interest.

• Beyond 3 messages. Whether superactivation of $\omega^{*}(G)$ is possible for protocols with many rounds, or at least beyond 3 messages, is left open.

• Implications for the quantum PCP conjecture. The authors suspect the failure of parallel repetition could influence the two proposed versions of the quantum PCP theorem, or at least the path toward proving them, given that gap amplification already faces challenges [NN24].

• Stronger cryptographic consequences. The authors expect that superactivated cheating for any $n \geq 2$ has stronger cryptographic fallout than quantum hedging, and leave the precise consequences to future work.

Target Audience

Researchers in quantum information theory and quantum complexity theory; cryptographers working on interactive proof systems, concurrent security and soundness amplification; and graduate students familiar with quantum channels, entanglement-assisted strategies and the $\mathsf{QMIP}$/$\mathsf{QMIP}^{*}$ framework. Readers without a quantum computing background will find the framing accessible but the technical content demanding.

Authors’ 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.