Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.31223

Quantum interaction can superactivate cheating under parallel repetition

Archishna Bhattacharyya, Laura Mančinska, Yuming Zhao

quant-phcs.CCSubmitted Sep 25, 2026• Announced Sep 28, 2026• 0 citations
arXivHTMLPDF

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.

Comments
27 pages

Related papers

No Strong Parallel Repetition with Entangled and Non-signaling Provers

Julia Kempe, Oded Regev

We consider one-round games between a classical verifier and two provers. One of the main questions in this area is the parallel repetition question: If the game is played H times in parallel, does the maximum winning probability decay exponentially in ℓ? In the classical setting, this question was answered in the affirmative by Raz. More recently the question arose whether the decay is of the form (1 - ⊖ (ε))ℓwhere 1 - ε is the value of the game and H is the number of repetitions. This question is known as the strong parallel repetition question and was motivated by its connections to the unique games conjecture. It was resolved by Raz who showed that strong parallel repetition does not hold, even in the very special case of games known as XOR games. This opens the question whether strong parallel repetition holds in the case when the provers share entanglement. Evidence for this is provided by the behavior of XOR games, which have strong (in fact perfect) parallel repetition, and by the recently proved strong parallel repetition of linear unique games. A similar question was open for games with so-called non-signaling provers. Here the best known parallel repetition theorem is due to Holenstein, and is of the form (1 - ⊖ (ε2))ℓ. We show that strong parallel repetition holds neither with entangled provers nor with non-signaling provers. In particular we obtain that Holenstein's bound is tight. Along the way we also provide a tight characterization of the asymptotic behavior of the entangled value under parallel repetition of unique games in terms of a semidefinite program.

arXiv:0911.0201•IEEE Conference on Computational Complexity (CCC)•Jun 1, 2010•33 citations

Parallel Repetition for Post-Quantum Arguments

Andrew Huang, Yael Tauman Kalai

In this work, we show that parallel repetition of public-coin interactive arguments reduces the soundness error at an exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least t of the executions are accepted (for some threshold t). Prior to this work, these results were known only when the cheating prover was assumed to be classical.We also prove a similar result for three-message private-coin arguments. Previously, Bostanci, Qian, Spooner, and Yuen (STOC 2024) proved such a parallel repetition result in the more general setting of quantum protocols, where the verifier and communication may be quantum. We consider only protocols where the verifier is classical, but obtain a simplified analysis, and for the more general setting of threshold verifiers.

arXiv:2506.02277•Annual Symposium on Foundations of Computer Science•Dec 14, 2025•1 citation

Parallel Repetition of Prover-Verifier Quantum Interactions

Abel Molina

In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. We first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. We look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is $p$. A reasonable conjecture for the answer would be \sum_{m \geq k} {n \choose m} p^m (1-p)^{n-m}, as that is the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n, and also in the classical case. It is also correct in some generalizations of the classical case that we will discuss later. We will show how this cannot be extended to all cases, presenting an example of an interaction with k=1,n=2 in which p\approx 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. Finally, we will connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.

arXiv:1203.4885•Mar 22, 2012•0 citations

Parallel Repetition of Prover-Verifier Quantum Interactions

Abel Molina

In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. \n \nWe first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. \n \nWe look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is p. A reasonable conjecture for the answer would be the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n. We will show how this cannot be extended to the general case, presenting an example of an interaction with k=1,n=2 in which p is approximately 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. \n \nFinally, we connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.

•Jan 1, 2011•0 citations

Quantum Multiprover Interactive Proofs with Communicating Provers

Michael Ben-Or, Avinatan Hassidim, Haran Pilpel

We introduce a new variant of quantum multiprover interactive proofs (QMIP) where the provers and the verifier are quantum. The verifier can exchange quantum messages with the provers. The provers cannot communicate quantumly between themselves and do not share entanglement, but are unlimited in the classical communication between them, even after receiving messages from the verifier. We show that any language in nondeterministic exponential time (NEXP) can be recognized in this model efficiently, with just two provers and two rounds of communication, and with a constant completeness/soundness gap. This is in contrast to the result of [R. Jain et al., Comm. ACM, 53 (2010), pp. 102--109], which shows that QIP = PSPACE, or equivalently that the set of languages that can be recognized by a quantum verifier communicating with a single quantum prover is equal to PSPACE. To analyze the cheating power of the provers, we give them more power and allow them to perform any separable operation. We then show a unique two-phase protocol in which the provers first commit to a superposition of correct answers to all possible questions, and then in the second phase the verifier opens up the committed answer and checks for correctness and consistency.

SIAM Journal on Computing•Jan 1, 2014•4 citations

Parallel Repetition of Entangled Games

Julia Kempe, Thomas Vidick

We consider one-round games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in Raz's celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other. In the case where players share entanglement, the only previously known results are for special cases of games, and are based on techniques that seem inherently limited. Here we show for the first time that the maximum success probability of entangled games can be reduced through parallel repetition, provided it was not initially 1. Our proof is inspired by a seminal result of Feige and Kilian in the context of classical two-prover one-round interactive proofs. One of the main components in our proof is an orthogonalization lemma for operators, which might be of independent interest.

arXiv:1012.4728•Dec 21, 2010•2 citations
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 QMIP\mathsf{QMIP}QMIP protocols whose local (unentangled) value is strictly less than one for a single instance, yet equals one under nnn-fold parallel repetition for every n≥2n \geq 2n≥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 333 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.
We consider one-round games between a classical verifier and two provers. One of the main questions in this area is the parallel repetition question: If the game is played H times in parallel, does the maximum winning probability decay exponentially in ℓ? In the classical setting, this question was answered in the affirmative by Raz. More recently the question arose whether the decay is of the form (1 - ⊖ (ε))ℓwhere 1 - ε is the value of the game and H is the number of repetitions. This question is known as the strong parallel repetition question and was motivated by its connections to the unique games conjecture. It was resolved by Raz who showed that strong parallel repetition does not hold, even in the very special case of games known as XOR games. This opens the question whether strong parallel repetition holds in the case when the provers share entanglement. Evidence for this is provided by the behavior of XOR games, which have strong (in fact perfect) parallel repetition, and by the recently proved strong parallel repetition of linear unique games. A similar question was open for games with so-called non-signaling provers. Here the best known parallel repetition theorem is due to Holenstein, and is of the form (1 - ⊖ (ε2))ℓ. We show that strong parallel repetition holds neither with entangled provers nor with non-signaling provers. In particular we obtain that Holenstein's bound is tight. Along the way we also provide a tight characterization of the asymptotic behavior of the entangled value under parallel repetition of unique games in terms of a semidefinite program.
In this work, we show that parallel repetition of public-coin interactive arguments reduces the soundness error at an exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least t of the executions are accepted (for some threshold t). Prior to this work, these results were known only when the cheating prover was assumed to be classical.We also prove a similar result for three-message private-coin arguments. Previously, Bostanci, Qian, Spooner, and Yuen (STOC 2024) proved such a parallel repetition result in the more general setting of quantum protocols, where the verifier and communication may be quantum. We consider only protocols where the verifier is classical, but obtain a simplified analysis, and for the more general setting of threshold verifiers.
In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. We first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. We look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is ppp. A reasonable conjecture for the answer would be \sum_{m \geq k} {n \choose m} p^m (1-p)^{n-m}, as that is the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n, and also in the classical case. It is also correct in some generalizations of the classical case that we will discuss later. We will show how this cannot be extended to all cases, presenting an example of an interaction with k=1,n=2 in which p\approx 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. Finally, we will connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.
In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. \n \nWe first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. \n \nWe look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is p. A reasonable conjecture for the answer would be the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n. We will show how this cannot be extended to the general case, presenting an example of an interaction with k=1,n=2 in which p is approximately 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. \n \nFinally, we connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.
We introduce a new variant of quantum multiprover interactive proofs (QMIP) where the provers and the verifier are quantum. The verifier can exchange quantum messages with the provers. The provers cannot communicate quantumly between themselves and do not share entanglement, but are unlimited in the classical communication between them, even after receiving messages from the verifier. We show that any language in nondeterministic exponential time (NEXP) can be recognized in this model efficiently, with just two provers and two rounds of communication, and with a constant completeness/soundness gap. This is in contrast to the result of [R. Jain et al., Comm. ACM, 53 (2010), pp. 102--109], which shows that QIP = PSPACE, or equivalently that the set of languages that can be recognized by a quantum verifier communicating with a single quantum prover is equal to PSPACE. To analyze the cheating power of the provers, we give them more power and allow them to perform any separable operation. We then show a unique two-phase protocol in which the provers first commit to a superposition of correct answers to all possible questions, and then in the second phase the verifier opens up the committed answer and checks for correctness and consistency.
We consider one-round games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in Raz's celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other. In the case where players share entanglement, the only previously known results are for special cases of games, and are based on techniques that seem inherently limited. Here we show for the first time that the maximum success probability of entangled games can be reduced through parallel repetition, provided it was not initially 1. Our proof is inspired by a seminal result of Feige and Kilian in the context of classical two-prover one-round interactive proofs. One of the main components in our proof is an orthogonalization lemma for operators, which might be of independent interest.