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.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)
v1 · Sep 30, 2026v2 · Oct 1, 2026
arXivHTMLPDF

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.

AI Summary

Parallel repetition is a standard way to reduce the soundness error of interactive arguments without increasing their round complexity, but obtaining tight guarantees against quantum cheating provers is the question addressed here. The paper considers private-coin arguments transformed so that they run under homomorphic encryption, rather than claiming a repetition theorem for arbitrary unmodified arguments. Assuming homomorphic encryption secure in the post-quantum setting, the stated main result is that parallel repetition of these transformed arguments reduces soundness error at a tight exponential rate. The result also covers threshold repetition: the repeated verifier accepts exactly when at least $t$ of the component executions accept. The abstract distinguishes this from earlier guarantees restricted to classical cheating provers and states that tight bounds were not previously known. As an application, the paper states a construction of a constant-round succinct argument for $\mathsf{QMA}$ with both negligible completeness error and negligible soundness error, assuming only quantum homomorphic encryption. This connects the repetition theorem to amplification for succinct verification of quantum witnesses. The guarantees are conditional on encryption assumptions and apply after the encryption-based transformation. The supplied text contains only the abstract and LaTeX setup, so it does not provide explicit repetition bounds, parameter dependence, the proof technique beyond the encryption-based framework, or further stated limitations. Those details cannot be assessed from this excerpt.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

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.

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

Does parallel repetition lower the error in computationally sound protocols?

Mihir Bellare, Russell Impagliazzo, Moni Naor

Whether or not parallel repetition lowers the error has been a fundamental question in the theory of protocols, with applications in many different areas. It is well known that parallel repetition reduces the error at an exponential rate in interactive proofs and Arthur-Merlin games. It seems to have been taken for granted that the same is true in arguments, or other proofs where the soundness only holds with respect to computationally bounded parties. We show that this is not the case. Surprisingly, parallel repetition can actually fail in this setting. We present four-round protocols whose error does not decrease under parallel repetition. This holds for any (polynomial) number of repetitions. These protocols exploit non-malleable encryption and can be based on any trapdoor permutation. On the other hand we show that for three-round protocols the error does go down exponentially fast. The question of parallel error reduction is particularly important when the protocol is used in cryptographic settings like identification, and the error represents the probability that an intruder succeeds.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•121 citations

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, 2020•48 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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2011•4 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).

arXiv:2008.07445•Aug 17, 2020•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
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.
Parallel repetition is a standard way to reduce the soundness error of interactive arguments without increasing their round complexity, but obtaining tight guarantees against quantum cheating provers is the question addressed here. The paper considers private-coin arguments transformed so that they run under homomorphic encryption, rather than claiming a repetition theorem for arbitrary unmodified arguments.
Assuming homomorphic encryption secure in the post-quantum setting, the stated main result is that parallel repetition of these transformed arguments reduces soundness error at a tight exponential rate. The result also covers threshold repetition: the repeated verifier accepts exactly when at least ttt of the component executions accept. The abstract distinguishes this from earlier guarantees restricted to classical cheating provers and states that tight bounds were not previously known.
As an application, the paper states a construction of a constant-round succinct argument for QMA\mathsf{QMA}QMA with both negligible completeness error and negligible soundness error, assuming only quantum homomorphic encryption. This connects the repetition theorem to amplification for succinct verification of quantum witnesses.
The guarantees are conditional on encryption assumptions and apply after the encryption-based transformation. The supplied text contains only the abstract and LaTeX setup, so it does not provide explicit repetition bounds, parameter dependence, the proof technique beyond the encryption-based framework, or further stated limitations. Those details cannot be assessed from this excerpt.
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.
Whether or not parallel repetition lowers the error has been a fundamental question in the theory of protocols, with applications in many different areas. It is well known that parallel repetition reduces the error at an exponential rate in interactive proofs and Arthur-Merlin games. It seems to have been taken for granted that the same is true in arguments, or other proofs where the soundness only holds with respect to computationally bounded parties. We show that this is not the case. Surprisingly, parallel repetition can actually fail in this setting. We present four-round protocols whose error does not decrease under parallel repetition. This holds for any (polynomial) number of repetitions. These protocols exploit non-malleable encryption and can be based on any trapdoor permutation. On the other hand we show that for three-round protocols the error does go down exponentially fast. The question of parallel error reduction is particularly important when the protocol is used in cryptographic settings like identification, and the error represents the probability that an intruder succeeds.
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.
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).
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.