Source-linked AI summary
Quantum interaction can superactivate cheating under parallel repetition
Archishna Bhattacharyya, Laura Mančinska, Yuming Zhao
TL;DR
The paper asks whether parallel repetition can suppress cheating when verifier–prover communication is quantum. It builds a quantum game–channel correspondence and finds perfect local-value cheating after repetition despite subunit one-copy value, while short entangled protocols obey a no-increase result.
Problem
Parallel repetition is used for error reduction, but its behavior for games with quantum communication is at issue.
Source: §1 · pp. 2, 4Method
The authors construct quantum games and protocols whose classical and entangled values correspond to zero-error channel capacities.
Source: §1 · pp. 3, 5Results
ω(G)<1 yet ω(G^n)=1 for every n≥2; analogous superactivation occurs for local values of QMIP protocols with at least two nontrivial rounds.
Source: §1 · pp. 2–3Takeaways & Limitations
For entangled value, repetition cannot increase it in protocols with at most 3 messages, implying entanglement-assisted zero-error classical and quantum capacities cannot be superactivated.
Source: §1 · p. 3The unassisted zero-error classical-capacity protocol is considered asymptotically, with separable preshared states.
Source: §5.1 · p. 18
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames quantum parallel repetition as a setting where added quantum resources can reverse the usual soundness-suppression intuition. It connects this phenomenon to zero-error channel capacities and discusses its implications for cryptography and quantum PCP research.
1 Introduction
- ω(G)<1 while ω(G^n)=1 for every n≥2; repeated quantum questions can supply entanglement usable jointly across copies.The extra quantum state can enable a perfect strategy for repeated instances even when one copy cannot be won perfectly.Source: §1 · pp. 2–3
- Local-value superactivation also occurs in classes of QMIP protocols with at least two nontrivial rounds of interaction.The constructions use protocols that model zero-error classical and quantum communication.Source: §1 · pp. 3, 5
- The paper establishes a quantum game-channel correspondence linking game values to one-shot zero-error classical and quantum capacities, with and without entanglement assistance.The introduced games and protocols capture these capacities, and perfect winning corresponds to achieving full capacity.Source: §1 · pp. 3, 5
- Entangled-value superactivation is impossible for single-round quantum games and QMIP protocols with at most 3 messages; entanglement-assisted zero-error classical and quantum capacities also cannot be superactivated.The capacity conclusions follow from the game-channel correspondence.Source: §1 · pp. 3, 6
- Parallel repetition can add exploitable quantum resources as well as winning constraints, allowing strategies across copies that are impossible in one instance.In the constructions, the extra copy of the question state provides the resource needed for perfect play.Source: §1 · p. 3
- The authors identify obstacles to cryptographic gap amplification and to using parallel repetition for quantum-game soundness amplification.They also describe the result as relevant to the quantum PCP conjectures and the path toward proving them.Source: §1 · pp. 4–5
2 Preliminaries
The preliminaries define quantum games and multiprover protocols, distinguish local from entanglement-assisted strategies, and introduce channel capacities and the SWAP test. They also establish notation for registers, states, and quantum channels.
2 Preliminaries
- The notation defines [n] as {1, 2, ..., n}, identifies registers with Hilbert spaces, and defines quantum channels as completely positive trace-preserving maps.It also introduces the Choi-Jamiołkowski isomorphism for representing a channel by its Choi state.Source: §2 · pp. 6–7
2.1 Quantum games and interactive protocols
- A quantum game has a referee distribute quantum questions, receive local channel outputs, and test them with an accepting measurement.In a multiprover interactive proof, the verifier and multiple provers exchange messages over multiple rounds; local and entangled values distinguish product initial states from arbitrary shared states.Source: §2.1 · pp. 7–9
2.2 Quantum channel capacities
- Channel capacity measures information transmitted per channel use; zero-error capacity requires perfect transmission, while one-shot capacity concerns a single use.Entanglement assistance permits preshared entangled states, and some capacities can be superactivated: two zero-capacity channels can have a positive capacity when combined.Source: §2.2 · pp. 9–10
2.3 SWAP test
- The SWAP test is a quantum procedure for testing whether two states are identical or have inner product at most δ.It uses a controlled-SWAP operation and measures an ancillary qubit.Source: §2.3 · p. 10
3 Superactivation of cheating for quantum games
A one-round quantum game can have local value below one while its value under every parallel repetition of at least two copies is one. The construction uses exact state conversion that fails for one copy but succeeds for all such repetitions.
3 Superactivation of cheating for quantum games
- For any two quantum games, the entangled value of their product is no greater than the entangled value of either game.In particular, the entangled value cannot increase under two-fold repetition of the same game.Source: §3 · p. 11
- The product-game comparison need not hold for distinct games: an always-accepting game can supply the entanglement needed to raise the local value of another game.For such games G and H, ω(G × H) = ω*(G) > ω(G).Source: §3 · p. 12
- ω(G) < 1, yet ω(G^n) = 1 for every n ≥ 2 for a quantum game G.The proof first establishes perfect conversion for two and three copies, then uses that every integer n ≥ 2 has the form 2a + 3b.Source: §3 · pp. 12–13
- The game encodes state conversion: a perfect local strategy exists exactly when local channels convert the input state to the target state.For the chosen probability vectors, conversion fails for one copy but succeeds for repeated copies through factorizations p⊗n = q⊗n ⊗ r_n, up to permutation.Source: §3 · pp. 12–13
4 Interactive quantum protocols for zero-error capacities
The section constructs interactive protocols and quantum games that encode one-shot zero-error classical and quantum capacities. It also gives reductions from two-round protocols to one-round games, relating their local and entangled values.
4 Interactive quantum protocols for zero-error capacities
- The constructions establish a mapping from channels to interactive protocols, and then to games, for both zero-error classical and quantum capacities and their entanglement-assisted counterparts.The classical and quantum constructions are presented in separate subsections.Source: §4 · p. 13, §4.2 · pp. 15–16
4.1 Zero-error classical capacities
- The classical-capacity protocol Gseq has a perfect entanglement-assisted strategy exactly when C^(1)_0,E(N) ≥ log|M|; the local analogue characterizes unassisted capacity.Perfect play corresponds to encoding messages into channel outputs that the receiver can distinguish without error.Source: §4.1 · p. 14
- The classical-capacity construction also yields a one-round game whose local and entangled values are affinely related to those of the sequential protocol.Lemma 12 gives the relation for both values.Source: §4.1 · p. 15
4.2 Zero-error quantum capacities
- The quantum-capacity protocol Hseq has a perfect entanglement-assisted strategy exactly when Q^(1)_0,E(N) ≥ log|M|.Its verification tests recovery of the input state, and the corresponding unassisted statement uses a separable shared state.Source: §4.2 · pp. 15–16
- For quantum capacity, the construction likewise yields a one-round game whose local and entangled values are affinely related to those of the sequential protocol.Lemma 16 supplies the multi-to-single-round equivalence for both values.Source: §4.2 · p. 17
5 From channel superactivation to interactive quantum protocols
The section shows that channel superactivation yields quantum multiprover protocols whose local value is imperfect once but perfect under parallel repetition. It develops this for zero-error classical and quantum capacities, with the classical construction using an unassisted setting and a one-time-pad direct sum.
5.1 Cheating in the classical capacity QMIP protocol
- The classical-capacity protocol uses a separable preshared state, and running it in parallel corresponds to running the verifier over the joint channel.The joint message set corresponds to the product of the individual message sets.Source: §5.1 · p. 18
- Before establishing failure of repetition for the same protocol, a corollary exhibits two distinct protocols with imperfect local values whose product has value one.This is presented as a stepping stone to the same-protocol result.Source: §5.1 · pp. 18–19
- The one-time-pad direct sum is designed to break correlations between channel outputs, allowing imperfect single-instance execution to be overcome through multiround superactivation.The construction combines channels while enabling joint use of resources across repetitions.Source: §5.1 · p. 19
- For a single QMIP protocol G, ω(G) < 1 yet ω(G^n) = 1 for every n ≥ 2.The construction also gives ω(G^2) = ω(G^3) = 1.Source: §5.1 · p. 21
5.2 Cheating in the quantum capacity QMIP protocol
- For the quantum-capacity protocol class Hseq, the local value is below one in a single instance but equals one under every repetition n ≥ 2.The setting is the unassisted zero-error quantum capacity.Source: §5.2 · pp. 21–22
6 Impossibility of superactivation
The section identifies settings where superactivation is impossible, including entanglement-assisted zero-error channel capacities and entangled values of short interactive protocols. The results distinguish asymptotic capacities from a one-shot quantum-capacity case that can still superactivate.
6 Impossibility of superactivation
- The section frames the impossibility results across cryptographically relevant protocols and channel capacities as cases where superactivated cheating does not occur.It highlights a security-game model among the multi-round settings considered.Source: §6 · p. 22, §6.2 · p. 24
6.1 Impossibility of superactivation in channel capacities
- If a one-shot channel capacity cannot be superactivated, its asymptotic regularized capacity cannot be superactivated either.This general lemma is used to extend the relevant one-shot impossibility to the asymptotic case.Source: §6.1 · p. 22
- For any channels with zero entanglement-assisted one-shot zero-error classical capacity, their joint channel also has zero such capacity, so the asymptotic classical capacity cannot be superactivated.The result covers both one-shot and asymptotic entanglement-assisted zero-error classical capacity.Source: §6.1 · pp. 22–23
- The asymptotic entanglement-assisted zero-error quantum capacity cannot be superactivated when both component channels have zero capacity.The paper derives this using its relation between entanglement-assisted classical and quantum capacities.Source: §6.1 · p. 23
- In contrast, one-shot entanglement-assisted zero-error quantum capacity can superactivate: the dephasing channel has zero capacity alone but positive capacity across two uses.The supplied passages state Q0,E(Δ) = 0 and Q0,E(Δ⊗2) ≥ 1.Source: §6.1 · p. 23
6.2 Impossibility of superactivated cheating in multi-round protocols
- For 3-message QMIP protocols, the entangled value cannot be superactivated by parallel repetition.The protocol model has the players send registers to the verifier, receive channel outputs, apply local channels, and return outputs for verification.Source: §6.2 · p. 24