Pith. sign in

REVIEW 3 major objections 4 minor 19 references

Parallel Repetition for Post-Quantum Arguments

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that parallel repetition amplifies soundness exponentially for post-quantum interactive arguments, covering public-coin and three-message protocols, including threshold verifiers.

desk verdict Important open problem addressed, but the advertised exponential bounds in the corollaries are not proven as written; the core reduction is plausible and likely fixable. read the letter →

arxiv 2506.02277 v2 pith:QHPGGCGR submitted 2025-06-02 quant-ph cs.CR

Andrew Huang , Yael Tauman Kalai This is my paper
classification quant-phcs.CR MSC 81P6868Q1294A60 PACS 03.67.-a
keywords parallelrepetitionpost-quantumsoundnessinteractiveargumentsquantumrewindingfloodingthresholdverifierspublic-coinprotocolsprivate-coin
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that parallel repetition amplifies soundness in the post-quantum setting: repeating an interactive argument k times side by side, with the same classical verifier, makes it exponentially harder for a quantum-powered prover to cheat. Specifically, any public-coin $m$-message argument with soundness error $s$ has $k$-fold parallel repetition soundness error at most about $2^{-(t/k-s)^2 \cdot \Omega(k/m^2)}+\mathrm{negl}(\lambda)$ under a threshold verifier that demands at least $t$ accepting executions. Any three-message argument, even private-coin, has soundness error at most about $2^{-\Omega(k)\cdot (t/k - o(1) - s)^2}+\mathrm{negl}(\lambda)$. Prior to this work these amplification theorems for interactive arguments were established only against classical cheating provers. The proof's engine is a 'memoryless' quantum rewinding procedure that repairs a measured prover state while erasing its memory of the query that caused the measurement.

What carries the argument

The load-bearing object is the paper's 'memoryless' repair procedure, Lemma 4.1, which upgrades the value-estimation-and-state-repair technique into a rewinding tool that forgets. The procedure runs an almost-projective measurement ValEst to estimate how likely the prover's current state is to lead to acceptance, applies a projection $\Pi$ that tests a candidate query, and then repairs the state using Prepare and Repair'. To make the repaired state independent of $\Pi$, the procedure floods the prover with $T=4\ell/\eta^3$ dummy projective tests, where $\ell$ is a known upper bound on the prover's qubit count; by a memory bound, an $\ell$-qubit state cannot retain enough information to distinguish the embedded query from a dummy one. The final guarantee is that the repaired state still accepts random continuations with probability close to the original, while its joint distribution with the tested projection is nearly unchanged. Raz's lemma then bounds the statistical distance between successive hybrids, and for three-message private-coin protocols a soft-decision projection substitutes for the unknown verdict of the embedded execution.

What would settle it

Implement Lemma 4.1's Prepare and Repair' on an $\ell$-qubit state engineered to encode which projection $\Pi$ was used, and verify whether the output state's joint distribution with $\Pi$ differs in trace distance by more than $N\cdot\eta$; exceeding this bound would refute the memoryless repair guarantee. Alternatively, exhibit a public-coin argument and a quantum prover who wins the $k$-fold threshold game with probability $\xi$ while every $\mathrm{poly}(|B|,\lambda,1/\xi)$-time reduction to a single execution wins with probability below $t/k - 2m\sqrt{-\log(\xi/3m^2)/k}$, which would falsify the reduction of Theorem 5.1.

Watch

Extended reading notes

Core claim

The central claim is that exponential soundness amplification by parallel repetition survives quantum cheating provers, provided the verifier is classical. For a public-coin $m$-message argument with soundness error $\varepsilon$, the $k$-fold parallel repetition has post-quantum soundness error at most $\max\{6m^2 \exp(-(k/4m^2)(t/k-\varepsilon)^2),\mathrm{negl}(\lambda)\}$ for threshold $t$; with $t=k$ the base of the exponential is roughly $2^{-(1-\varepsilon)^2}$. For any three-message argument the corresponding bound is $\max\{2\exp(-(k/9)((t-2\sqrt{k}\log k)/k-\varepsilon)^2),\mathrm{negl}(\lambda)\}$. These are obtained by constructing, from any quantum adversary that wins the $k$-fold game with probability $\xi$, a quantum adversary that wins the single-fold game with probability about $t/k - 2m\sqrt{-\log(\xi/3m^2)/k}$ (public-coin case) or $t/k - 2\log k/\sqrt{k} - 3\sqrt{-\log \xi/k}$ (three-message case), up to negligible terms. The contrapositive of this reduction is exactly the stated soundness bound.

Load-bearing premise

The load-bearing premise is that flooding with $T=4\ell/\eta^3$ dummy queries forces any $\ell$-qubit quantum memory to forget which query was real; if a cheating prover's state can preserve correlations beyond this $\ell$-qubit bound, the forgetfulness guarantee of Lemma 4.1 fails and the reductions of Theorems 5.1 and 6.1 collapse.

Editorial extensions

If this is right

  • For any public-coin $m$-message argument, running $k$ copies in parallel preserves round count while post-quantum soundness error falls as $2^{-\Omega(k/m^2)}$ when the threshold is a constant fraction above the original soundness error.
  • Threshold verifiers can require $t$ of $k$ executions to accept, and the amplification rate depends on the normalized gap $(t/k-s)^2$; this supports direct-product-style hardness amplification for post-quantum arguments.
  • Three-message private-coin arguments are covered: even without public coins, parallel repetition now provably amplifies against quantum provers at an exponential rate.
  • These theorems hold with only classical communication and a classical verifier, so they apply to existing post-quantum argument systems without adding quantum hardware at the verifier.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One step further: the flooding mechanism only needs the reduction to sample the verifier's messages and verdict after a transcript prefix, so the same proof should cover protocols that are public-coin except possibly in the final round; the paper notes this class includes many classical-verification-of-quantum-computation protocols.
  • The $k/m^2$ rate is an artifact of using Raz's lemma; a quantum analogue of the relative-entropy chain rule (which the paper notes fails in its direct form) would be a plausible route to the optimal $k$ rate.
  • The reduction's need to know the prover's qubit count $\ell$ suggests a memory-bounded statement: if a quantum prover's memory is bounded by $\ell$, the flooding threshold can be set accordingly, potentially giving quantitative soundness bounds for restricted adversaries even where the unbounded theorem is open.
  • If the public-coin result extends to arguments where the last verifier message is private, the techniques may yield a post-quantum parallel repetition theorem for more than three messages, which the paper identifies as the main open problem.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proves post-quantum parallel repetition theorems in two settings: (1) any public-coin m-message interactive argument has k-fold parallel repetition soundness error bounded by roughly exp(-O(k/m^2)) in the post-quantum setting, including threshold verifiers; and (2) any three-message (possibly private-coin) interactive argument has exponentially decreasing soundness under parallel repetition, again including threshold verifiers. The proofs use the value-estimation and state-repair framework of CMSZ22, augmented with a flooding technique from BBK22 to make the repaired state forgetful of the embedded query. The approach is explicitly non-black-box and non-constructive in that the reduction uses poly-many copies of the prover's initial state and knowledge of its size. The paper also discusses limitations and open problems, such as the multi-round private-coin case.

Significance. If the proofs are correct, these results are a significant advance: they are the first post-quantum parallel repetition theorems for multi-round public-coin arguments and for three-message arguments with threshold verifiers, extending classical results that were previously known only against classical provers. The memoryless repair lemma (Lemma 4.1) is a useful technical contribution that may find other applications. The paper is also commendably explicit about its non-black-box and non-constructive features, and it correctly identifies the multi-round private-coin case as the main open problem. The reliance on published results (CMSZ22, BBK22, Raz, HPPW10) is appropriate, and the self-citation of BBK22 is a legitimate use of an established tool rather than a circular dependency. However, as detailed below, the proof of the two main corollaries contains a concrete logical gap, and the hybrid proof of Lemma 5.5 has an indexing error; both are load-bearing and need repair before the claims can be considered established.

major comments (3)
  1. [Section 5.1, Corollary 5.2] The proof concludes that the constructed adversary A satisfies Pr[A succeeds] >= ε + 2m^2/t - negl(λ), and then states: 'Since m and t are polynomial, ε+2m^2/t−negl(λ) > ε+negl(λ).' This inequality is false in general. For example, with m=λ and t=λ^5, both are polynomial but 2m^2/t = 2/λ^3 is negligible, so the stated lower bound does not exceed ε+negl(λ). The contradiction with ε-soundness therefore does not follow in this parameter regime. This is not a vacuous regime: it includes thresholds t close to k with k >> m^2, exactly where the claimed exp(-k/(4m^2)(t/k-ε)^2) bound is strongest. The corollary may still be true, for instance by retaining the exact expression t/k - 2m sqrt(-log(ξ/3m^2)/k) and splitting into cases, but that argument is not supplied in the paper.
  2. [Section 6.1, Corollary 6.2] The same logical gap appears in the proof of Corollary 6.2. The proof derives Pr[A succeeds] >= ε + 9/(2t) - negl(λ) and then concludes this is strictly greater than ε+negl(λ) because t is polynomial. When 9/(2t) is negligible, which can happen with t=λ^5, the inequality is false and the contradiction with ε-soundness is not obtained. The affected threshold regime overlaps with the strongest form of the claimed bound exp(-k/9 ((t-2√k log k)/k - ε)^2), so the issue is not merely cosmetic. As with Corollary 5.2, this is a repairable gap, but the proof as written does not establish the corollary for all claimed polynomial choices of t and k.
  3. [Section 5.1, Lemma 5.5] The proof of Lemma 5.5 defines intermediate hybrids H_{j,h} that 'replace the conditional sampling of ¯q in step 3(c)(i) with a uniform sample' when ℓ=j and s∈{1,...,h}. But by the definition of H_j, rounds 1 through j are already sampled uniformly, so modifying round j does not change the behavior: H_{j,h} is identical to H_j for every h. The difference between H_j and H_{j+1} occurs at round j+1, since H_{j+1} makes rounds 1 through j+1 uniform. Thus the proof should use ℓ=j+1 and re-derive the statements about the 'first j−1 rounds' and the state at the 'end of the jth round.' As written, Lemma 5.5, which is essential for the hybrid argument proving Theorem 5.1, is not established. The error appears to be an indexing typo, but it is load-bearing and must be corrected.
minor comments (4)
  1. [Section 1.1, Theorems 1.1-1.4] The informal statements use f(s) ≈ 2^{-(1-s)^2} and 2^{-(t/k-s)^2}; since the formal corollaries state different explicit constants, readers would benefit from a sentence explaining that the informal f(s) is representative of the best constants and that the formal bounds are the ones proved.
  2. [Section 5.1, Corollary 5.2, footnote 12] The footnote says that when ε ≥ t/k, a direct-product argument converts an adversary succeeding with probability ε into one that convinces at least t verifiers with constant probability, but no proof or citation is given; a short derivation would improve clarity.
  3. [Section 5.1, proof of Theorem 5.1] The text says 'we can assume without loss of generality that ξ ≫ δ, as otherwise our guarantee is essentially trivially true'; since δ is set to min{2^{-λ},2^{-k}}, this is plausible, but the threshold for 'trivially true' is not quantified.
  4. [Algorithm 1, step 2] In the loop over s in step 2, if p_0 < ξ-ε_0 and s=iter, the reduction returns (i,⊥). The prose and proof treat this as an abort, but the algorithm box does not explicitly define the output state in this case; this is a minor notational issue.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main reductions are genuine proofs from independent external lemmas, and the BBK22 self-citation is not a circular premise.

full rationale

The derivation chain is not circular. Theorem 5.1 is a reduction from a k-fold quantum adversary B to a single-execution adversary A, and its proof combines the external value-estimation/repair lemma of CMSZ22/LMS22 (Lemma 3.2), the BBK22 flooding lemma (Lemma 3.6), and Raz's lemma (Lemma 3.7); none of these inputs states or assumes the parallel-repetition conclusion. Lemma 4.1 is proved directly by a hybrid argument plus the information-theoretic BBK22 bound. Theorem 6.1 similarly uses the HPPW10 soft-decision lemma as an external ingredient. Although BBK22 is co-authored by Kalai, it is cited as a self-contained information-theoretic lemma whose stated assumptions do not include the target result, so it is independent support rather than a circular premise. The only serious issue found is a non-circular correctness gap: in Corollary 5.2's proof the line 'Since m and t are polynomial, ε+2m^2/t−negl(λ)>ε+negl(λ)' does not follow when 2m^2/t is negligible, and the analogous 'Since t is polynomial, ε+9/(2t)−negl(λ)>ε+negl(λ)' step in Corollary 6.2 fails when 9/(2t) is negligible. This is an algebraic/quantitative error, not an instance of a conclusion being fed back as an assumption, and it does not affect the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The proof uses standard results from the literature as building blocks: the CMSZ22 value-estimation and repair lemma, the BBK22 flooding lemma, Raz's lemma, and the HPPW10 soft-decision lemma. No new entities are postulated, and no parameters are fitted to data; the reduction parameters are set analytically to satisfy inequalities in the proof.

assumptions (5)
  • domain assumption ValEst and Repair algorithms exist with the guarantees in Lemma 3.2 (from CMSZ22 and LMS22).
    Invoked throughout Sections 5 and 6 as the core estimation and repair primitive.
  • domain assumption The flooding bound in Lemma 3.6 (from BBK22): an ℓ-qubit state cannot remember which of t sampled values was the 'real' one, with trace distance at most sqrt(ℓ/(2t)).
    Used in the proof of Lemma 4.1 to make the repaired state forgetful.
  • standard math Raz's lemma (Lemma 3.7): for independent random variables, conditioning on an event W, the location of a coordinate is hidden with distance at most sqrt(-log Pr[W]/k).
    Used in Lemma 5.5 and Proposition 5.6 to bound hybrid distances.
  • domain assumption The HPPW10 soft-decision lemma (Lemma 6.10) bounding the probability that a random coordinate rejects conditioned on the soft-decision accepting.
    Used in Lemma 6.9 for the three-message threshold analysis.
  • standard math Deferred measurement and purification of quantum adversaries to unitaries.
    Used in Fact 5.2.1 and in the definition of the unitaries U_j.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parallel Repetition for Post-Quantum Arguments." pith.science (2026). https://pith.science/paper/QHPGGCGR

@misc{pith2026250602277,
  author       = {Pith},
  title        = {Pith review of: Parallel Repetition for Post-Quantum Arguments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QHPGGCGR}},
  note         = {Machine review of arXiv:2506.02277}
}
abstract

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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Constructive post-quantum reductions

    Nir Bitansky, Zvika Brakerski, and Yael Tauman Kalai. Constructive post-quantum reductions. In Annual International Cryptology Conference , pages 654--683. Springer, 2022

    work page 2022

  2. [2]

    Does parallel repetition lower the error in computationally sound protocols? In Proceedings 38th Annual Symposium on Foundations of Computer Science , pages 374--383

    Mihir Bellare, Russell Impagliazzo, and Moni Naor. Does parallel repetition lower the error in computationally sound protocols? In Proceedings 38th Annual Symposium on Foundations of Computer Science , pages 374--383. IEEE, 1997

    work page 1997

  3. [3]

    Arthur-merlin games: a randomized proof system, and a hierarchy of complexity classes

    L \'a szl \'o Babai and Shlomo Moran. Arthur-merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences , 36(2):254--276, 1988

    work page 1988

  4. [4]

    An efficient quantum parallel repetition theorem and applications

    John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen. An efficient quantum parallel repetition theorem and applications. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1478--1487, 2024

    work page 2024

  5. [5]

    Hardness amplification of weakly verifiable puzzles

    Ran Canetti, Shai Halevi, and Michael Steiner. Hardness amplification of weakly verifiable puzzles. In Theory of Cryptography Conference , pages 17--33. Springer, 2005

    work page 2005

  6. [6]

    Efficient parallel repetition theorems with applications to security amplification

    Kai-Min Chung. Efficient parallel repetition theorems with applications to security amplification . Harvard University, 2011

    work page 2011

  7. [7]

    Parallel repetition theorems for interactive arguments

    Kai-Min Chung and Feng-Hao Liu. Parallel repetition theorems for interactive arguments. In Theory of Cryptography: 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings 7 , pages 19--36. Springer, 2010

    work page 2010

  8. [8]

    Post-quantum succinct arguments: breaking the quantum rewinding barrier

    Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry. Post-quantum succinct arguments: breaking the quantum rewinding barrier. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 49--58. IEEE, 2022

    work page 2021

Show all 19 references
  1. [9]

    Tight parallel repetition theorems for public-coin arguments using kl-divergence

    Kai - Min Chung and Rafael Pass. Tight parallel repetition theorems for public-coin arguments using kl-divergence. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, ...

    2015

  2. [10]

    Chain rule for the quantum relative entropy

    Kun Fang, Omar Fawzi, Renato Renner, and David Sutter. Chain rule for the quantum relative entropy. Physical review letters , 124(10):100501, 2020

    2020

  3. [11]

    A parallel repetition theorem for any interactive argument

    Iftach Haitner. A parallel repetition theorem for any interactive argument. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages 241--250. IEEE, 2009

    2009

  4. [12]

    Parallel repetition: simplifications and the no-signaling case

    Thomas Holenstein. Parallel repetition: simplifications and the no-signaling case. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 411--419, 2007

    2007

  5. [13]

    An efficient parallel repetition theorem

    Johan H stad, Rafael Pass, Krzysztof Pietrzak, and Douglas Wikstr \"o m. An efficient parallel repetition theorem. In Theory of Cryptography: 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings 7 , pages 1--18. Springer, 2010

    2010

  6. [14]

    Kitaev and John Watrous

    Alexei Y. Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000...

    2000

  7. [15]

    Quantum rewinding for many-round protocols

    Russell WF Lai, Giulio Malavolta, and Nicholas Spooner. Quantum rewinding for many-round protocols. In Theory of Cryptography Conference , pages 80--109. Springer, 2022

    2022

  8. [16]

    An efficient parallel repetition theorem for arthur-merlin games

    Rafael Pass and Muthuramakrishnan Venkitasubramaniam. An efficient parallel repetition theorem for arthur-merlin games. In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 20...

    2007

  9. [17]

    Parallel repetition of computationally sound protocols revisited

    Krzysztof Pietrzak and Douglas Wikstr \" o m. Parallel repetition of computationally sound protocols revisited. In Salil P. Vadhan, editor, Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007, Proceedings , ...

    2007

  10. [18]

    A parallel repetition theorem

    Ran Raz. A parallel repetition theorem. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing , pages 447--456, 1995

    1995

  11. [19]

    Theory and application of trapdoor functions

    Andrew C Yao. Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) , pages 80--91. IEEE, 1982

    1982

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.