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:2008.07445

Parallel repetition with a threshold in quantum interactive proofs

Abel Molina

Published Aug 17, 2020• 0 citations
arXivHTMLPDF

Abstract

In this note, we show that $O(\log (1/ε))$ rounds of parallel repetition with a threshold suffice to reduce completeness and soundness error to $ε$ for single-prover quantum interactive proof systems. This improves on a previous $O(\log (1/ε) \log \log (1/ε))$ bound from Hornby (2018), while also simplifying its proof. A key element in our proof is a concentration bound from Impagliazzo and Kabanets (2010).

DOI
10.48550/arxiv.2008.07445

Related papers

Concentration Bounds from Parallel Repetition Theorems

Taylor Hornby

This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions: \n \n- A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances). \n \n- Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies. \n \n- A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires a log-factor more repetitions than are necessary in the classical case.

•Aug 22, 2018•1 citation

Tight Post-Quantum Parallel Repetition for Private-Coin Arguments

Zvika Brakerski, Andrew Huang, Yael Tauman Kalai +1 more

We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight 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, and it was not known how to achieve tight bounds. As a corollary, we construct the first constant-round succinct argument for $\mathsf{QMA}$ with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.

quant-pharXiv:2609.38941•Oct 1, 2026•0 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. \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 interaction can superactivate cheating under parallel repetition

Archishna Bhattacharyya, Laura Mančinska, Yuming Zhao

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.

quant-pharXiv:2609.31223•Sep 28, 2026•0 citations

Using Entanglement in Quantum Multi-prover Interactive Proofs

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto +1 more

The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multi- prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from 1 by an inverse polynomial in the input size, and one extra proven Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This "public-coin" property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single prover ones.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2008•26 citations
In this note, we show that O(log⁡(1/ε))O(\log (1/ε))O(log(1/ε)) rounds of parallel repetition with a threshold suffice to reduce completeness and soundness error to εεε for single-prover quantum interactive proof systems. This improves on a previous O(log⁡(1/ε)log⁡log⁡(1/ε))O(\log (1/ε) \log \log (1/ε))O(log(1/ε)loglog(1/ε)) bound from Hornby (2018), while also simplifying its proof. A key element in our proof is a concentration bound from Impagliazzo and Kabanets (2010).
This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions: \n \n- A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances). \n \n- Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies. \n \n- A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires a log-factor more repetitions than are necessary in the classical case.
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight 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 ttt of the executions are accepted (for some threshold ttt). Prior to this work, these results were known only when the cheating prover was assumed to be classical, and it was not known how to achieve tight bounds. As a corollary, we construct the first constant-round succinct argument for QMA\mathsf{QMA}QMA with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.
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. \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 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.
The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multi- prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from 1 by an inverse polynomial in the input size, and one extra proven Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This "public-coin" property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single prover ones.