arXiv:2609.38941

Tight Post-Quantum Parallel Repetition for Private-Coin Arguments

Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner

quant-phcs.CRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 1, 2026 (v2)

Abstract

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.

Related papers

Parallel Repetition for Post-Quantum Arguments

Andrew Huang, Yael Tauman Kalai

arXiv:2506.02277Annual Symposium on Foundations of Computer ScienceDec 14, 20251 citation

Post-quantum zero knowledge in constant rounds

Nir Bitansky, Omri Shmueli

We construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA.

ACM Symposium on Theory of Computing (STOC)Jun 6, 202045 citations

The Randomness Complexity of Parallel Repetition

Kai-Min Chung, Rafael Pass

Annual Symposium on Foundations of Computer ScienceOct 1, 20114 citations

Parallel repetition with a threshold in quantum interactive proofs

Abel Molina

arXiv:2008.07445Aug 17, 20200 citations

Compiling Any $\mathsf{MIP}^{*}$ into a (Succinct) Classical Interactive Argument

Andrew Huang, Yael Tauman Kalai

arXiv:2510.08495Oct 9, 20250 citations

Quantum interaction can superactivate cheating under parallel repetition

Archishna Bhattacharyya, Laura Mančinska, Yuming Zhao

quant-pharXiv:2609.31223Sep 28, 20260 citations

arXiv:2609.38941

Tight Post-Quantum Parallel Repetition for Private-Coin Arguments

Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner

quant-phcs.CRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 1, 2026 (v2)

arXiv HTML PDF

Abstract

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.

Related papers

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.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.02277Annual Symposium on Foundations of Computer ScienceDec 14, 20251 citation

Post-quantum zero knowledge in constant rounds

Nir Bitansky, Omri Shmueli

ACM Symposium on Theory of Computing (STOC)Jun 6, 202045 citations

The Randomness Complexity of Parallel Repetition

Kai-Min Chung, Rafael Pass

Consider a m-round interactive protocol with soundness error 1/2. How much extra randomness is required to decrease the soundness error to δ through parallel repetition? Previous work, initiated by Bell are, Goldreich and Goldwasser, shows that for public-coin interactive protocols with statistical soundness, m · O(log (1/δ)) bits of extra randomness suffices. In this work, we initiate a more general study of the above question. We establish the first derandomized parallel repetition theorem for public-coin interactive protocols with computational soundness (a.k.a. arguments). The parameters of our result essentially matches the earlier works in the information-theoretic setting. We show that obtaining even a sub-linear dependency on the number of rounds m (i.e., o(m)·log(1/δ)) is impossible in the information-theoretic, and requires the existence of one-way functions in the computational setting. We show that non-trivial derandomized parallel repetition for private-coin protocols is impossible in the information-theoretic setting and requires the existence of one-way functions in the computational setting. These results are tight in the sense that parallel repetition theorems in the computational setting can trivially be derandomized using pseudorandom generators, which are implied by the existence of one-way functions.Consider a m-round interactive protocol with soundness error 1/2. How much extra randomness is required to decrease the soundness error to δ through parallel repetition? Previous work, initiated by Bell are, Goldreich and Goldwasser, shows that for public-coin interactive protocols with statistical soundness, m · O(log (1/δ)) bits of extra randomness suffices. In this work, we initiate a more general study of the above question. We establish the first derandomized parallel repetition theorem for public-coin interactive protocols with computational soundness (a.k.a. arguments). The parameters of our result essentially matches the earlier works in the information-theoretic setting. We show that obtaining even a sub-linear dependency on the number of rounds m (i.e., o(m)·log(1/δ)) is impossible in the information-theoretic, and requires the existence of one-way functions in the computational setting. We show that non-trivial derandomized parallel repetition for private-coin protocols is impossible in the information-theoretic setting and requires the existence of one-way functions in the computational setting. These results are tight in the sense that parallel repetition theorems in the computational setting can trivially be derandomized using pseudorandom generators, which are implied by the existence of one-way functions.

Annual Symposium on Foundations of Computer ScienceOct 1, 20114 citations

Parallel repetition with a threshold in quantum interactive proofs

Abel Molina

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).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).

arXiv:2008.07445Aug 17, 20200 citations

Compiling Any $\mathsf{MIP}^{*}$ into a (Succinct) Classical Interactive ArgumentCompiling Any $\mathsf{MIP}^{*}$ into a (Succinct) Classical Interactive Argument

Andrew Huang, Yael Tauman Kalai

We present a generic compiler that converts any $\mathsf{MIP}^{*}$ protocol into a succinct interactive argument where the communication and the verifier are classical, and where post-quantum soundness relies on the post-quantum sub-exponential hardness of the Learning with Errors ( $\mathsf{LWE}$ ) problem. Prior to this work, such a compiler for $\mathsf{MIP}^{*}$ was given by Kalai, Lombardi, Vaikuntanathan and Yang (STOC 2022), but the post-quantum soundness of this compiler is still under investigation. More generally, our compiler can be applied to any $\mathsf{QIP}$ protocol which is sound only against semi-malicious provers that follow the prescribed protocol, but with possibly malicious initial state. Our compiler consists of two steps. We first show that if a language $\mathcal{L}$ has a $\mathsf{QIP}$ with semi-malicious soundness, where the prover runs in time $T$ , then $\mathcal{L} \in \mathsf{QMATIME}(T)$ . Then we construct a succinct classical argument for any such language, where the communication complexity grows polylogarithmically with $T$ , under the post-quantum sub-exponential hardness of $\mathsf{LWE}$ . Note: After this work was finished, an independent and concurrent work (Baroni et al. 2025) resolved the question of quantum soundness of the KLVY compiler.We present a generic compiler that converts any $\mathsf{MIP}^{*}$ protocol into a succinct interactive argument where the communication and the verifier are classical, and where post-quantum soundness relies on the post-quantum sub-exponential hardness of the Learning with Errors ($\mathsf{LWE}$) problem. Prior to this work, such a compiler for $\mathsf{MIP}^{*}$ was given by Kalai, Lombardi, Vaikuntanathan and Yang (STOC 2022), but the post-quantum soundness of this compiler is still under investigation. More generally, our compiler can be applied to any $\mathsf{QIP}$ protocol which is sound only against semi-malicious provers that follow the prescribed protocol, but with possibly malicious initial state. Our compiler consists of two steps. We first show that if a language $\mathcal{L}$ has a $\mathsf{QIP}$ with semi-malicious soundness, where the prover runs in time $T$, then $\mathcal{L} \in \mathsf{QMATIME}(T)$. Then we construct a succinct classical argument for any such language, where the communication complexity grows polylogarithmically with $T$, under the post-quantum sub-exponential hardness of $\mathsf{LWE}$. Note: After this work was finished, an independent and concurrent work (Baroni et al. 2025) resolved the question of quantum soundness of the KLVY compiler.

arXiv:2510.08495Oct 9, 20250 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.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.31223Sep 28, 20260 citations

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.

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).

Compiling Any

\mathsf{MIP}^{*}

into a (Succinct) Classical Interactive Argument

We present a generic compiler that converts any

\mathsf{MIP}^{*}

protocol into a succinct interactive argument where the communication and the verifier are classical, and where post-quantum soundness relies on the post-quantum sub-exponential hardness of the Learning with Errors (

\mathsf{LWE}

) problem. Prior to this work, such a compiler for

\mathsf{MIP}^{*}

was given by Kalai, Lombardi, Vaikuntanathan and Yang (STOC 2022), but the post-quantum soundness of this compiler is still under investigation. More generally, our compiler can be applied to any

\mathsf{QIP}

protocol which is sound only against semi-malicious provers that follow the prescribed protocol, but with possibly malicious initial state. Our compiler consists of two steps. We first show that if a language

\mathcal{L}

has a

\mathsf{QIP}

with semi-malicious soundness, where the prover runs in time

T

, then

\mathcal{L} \in \mathsf{QMATIME}(T)

. Then we construct a succinct classical argument for any such language, where the communication complexity grows polylogarithmically with

T

, under the post-quantum sub-exponential hardness of

\mathsf{LWE}

. Note: After this work was finished, an independent and concurrent work (Baroni et al. 2025) resolved the question of quantum soundness of the KLVY compiler.

\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.