{"id":"343fa47f-0731-4603-a0b7-30ee009aed57","arxiv_id":"2509.01945","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Quantum statistical witness indistinguishability (QSWI) is defined and shown to equal its honest-verifier and public-coin versions, with SWI contained in QSWI.","lead":"A new complexity class QSWI is defined for quantum proofs that hide which witness the prover used, and it is shown that honest and malicious verifiers see the same class of proofs. The result also lets classical statistical witness indistinguishability be studied with quantum tools.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop. 5.5 applies the QDS lemma to the full verifier view, whose qubit count is not bounded by ρ-compression; the O(√ρ) bound needs an explicit transcript-reduction argument that the paper does not give.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing gap: Proposition 5.5 applies a communication-bounded stability lemma to the full verifier view, while the compression parameter only bounds message qubits. This is a real correctness risk in the written proof, not a disagreement with the consensus. However, the gap appears repairable by a standard transcript-reduction argument, so it does not by itself justify rejection. I do not see a more serious flaw in the central hvQSWI = QSWI proof: the malicious-verifier simulation is sketched and post-selects, but the public-coin honest transcript gives a uniform independent bit, so the post-selection succeeds with constant probability and the construction is plausible. The batch-proof issue is the most load-bearing because it is the main technical step that the paper's second theorem relies on, and the proof as written is incomplete. Since the reader already gave CONDITIONAL, my read does not change that verdict.","tokens_in":20278,"tokens_out":37719,"duration_ms":405892,"concrete_test":"Re-derive Proposition 5.5 with f_j replaced by the transcript map g_j(b) that outputs the first j message registers (at most j·q_M qubits), and prove that ViewV is obtained from g_j by a fixed CPTP map. If trace distance of views is bounded by trace distance of transcripts, then Corollary 2.3 applied to g_j restores O(sqrt(ρ)); if the fixed-channel reduction fails for quantum transcripts, Theorem 5.4 is unsupported. A sharper test: take a batch proof whose verifier uses q_V = t^2 private qubits (e.g., it copies the whole batch) and check whether the written view-based QDS bound degrades to O(sqrt(t)).","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Proposition 5.5, the function f_j(b) = ViewV(x, w(b), j) is fed into Corollary 2.3. That corollary's bound is O(sqrt(t'/t)), where t' is the number of output qubits. But Definition 5.2 only bounds k·q_M, the total message communication. The verifier view also contains q_V private qubits and, in this construction, the classical batch x of length t·n. Nothing in the definition of a ρ-compressing quantum batch proof bounds q_V + |x| by O(ρt). For example, an efficient verifier may use q_V = t^2 private workspace while keeping q_M·k = o(ρt). Then the written QDS application gives only O(sqrt((q_V+|x|)/t)), which need not be O(sqrt(ρ)). The proof implicitly assumes that the view can be replaced by the transcript (size at most k·q_M = o(ρt)) via a fixed verifier map, but this reduction is neither stated nor proved. Thus the claimed O(sqrt(ρ)) witness-indistinguishability error in Theorem 5.4 does not follow from the written argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces QSWI, a quantum analogue of statistical witness indistinguishability, and proves two main results. First, any problem with an honest-verifier QSWI proof can be transformed into a 3-message, public-coin, malicious-verifier QSWI proof, yielding pubQSWI = QSWI = hvQSWI and, as a corollary, SWI ⊆ QSWI. Second, any ρ-compressing quantum batch proof for an NP relation gives an honest-verifier QSWI proof with O(√ρ) witness-indistinguishability error, using a non-uniform honest prover. The proofs follow Kobayashi's QSZK transformations, Watrous rewinding, and Drucker's quantum distributional stability lemma, and the paper includes a transparently labeled failed attempt at quantum batch proofs for NP in Appendix A.","tokens_in":20594,"tokens_out":12040,"duration_ms":150539,"significance":"If the proofs are made fully rigorous, this is a substantive contribution: it initiates the study of QSWI, shows a malicious-verifier/ honest-verifier collapse that is not known classically, proves a classical-class containment SWI ⊆ QSWI, and extends the batch-proof-to-WI compilation of Bitansky et al. to the quantum setting. Strengths include a clean set of definitions, explicit error tracking through the transformations, reliance on established external results, and honest disclosure of a failed construction. The main concerns below are about load-bearing gaps in the written proofs rather than about the novelty or plausibility of the claims.","major_comments":[{"comment":"Definition 5.2 bounds only k·q_M = o(ρt), i.e., the total message communication. The function f_τ(b) = ViewV(x,w(b),j) used in Prop. 5.5 outputs the full verifier view, which includes the verifier's private workspace (q_V qubits) and, in the compiled protocol, the full instance vector x of length n·t sent by the prover. Corollary 2.3 gives O(√(t'/t)) where t' is the output qubit count, and nothing in the definition of ρ-compression bounds q_V + n·t by O(ρt). For example, q_V = t² and n·t = t² with ρ = 1/t would give only O(1), not O(√ρ). The stated O(√ρ) WI error therefore does not follow from the written argument. The proof needs either a definition of ρ-compression that also bounds the view size, or an explicit argument reducing the view to the transcript (of size O(k·q_M)) in a way that preserves the trace distance.","section":"§5.2, Prop. 5.5 / Thm. 5.4"},{"comment":"In the WI analysis for the compressed protocol, S'(x,1) is defined as the tensor product of S(x,j-1) over the round registers, and the proof bounds ∥ViewV'(x,w,1) − S'(x,1)∥_tr by a sum of per-round errors via 'subadditivity of trace distance for tensor products.' That subadditivity only applies when both states are tensor products. ViewV'(x,w,1) is the joint state of all the round registers and is not shown to be a product state; correlations between the round states are not addressed. This is a load-bearing gap in the round-compression step of Theorem 4.6.","section":"§4.1, Lemma 4.1"},{"comment":"The malicious-verifier simulation is presented as a sketch. In particular, step 5 post-selects on the register X containing |0⟩, but the proof does not justify that the post-selection operation preserves the εWI error; the probability of the conditioning event can differ between real and simulated executions, and conditioning can amplify trace distance. Since this lemma is the step that upgrades honest-verifier security to malicious-verifier security, a formal argument (or a precise reference to the exact claim in [Kob08, Lemma 28]) is needed.","section":"§4.3, Lemma 4.5"}],"minor_comments":[{"comment":"The second triangle inequality in the reverse direction uses ∥ViewV(x,w0,j) − S(x,j)∥ twice; it should be ∥ViewV(x,w1,j) − S(x,j)∥.","section":"Fact 3.4 proof"},{"comment":"The definition says ρ ∈ N, but Theorem 5.4 and Corollary 5.6 use ρ ∈ (0,1). Please reconcile the notation.","section":"Def. 5.2"},{"comment":"The QSWI prover is described as sending 'x and j' to the verifier, but the verifier algorithm appears to use only x. Clarify whether the index j is part of the message and how it is used in completeness and soundness.","section":"Figs. 3–4"},{"comment":"The appendix is clearly labeled as a failed attempt and is discussed as such in Section 6; I did not treat it as a proof claim.","section":"Appendix A"}],"recommendation":"major_revision","confidential_remarks":"The paper's central claims are plausible and the overall strategy is sound, but the written proofs have load-bearing gaps, especially in Prop. 5.5 (view size vs. compression) and in the WI analysis of Lemma 4.1. These appear fixable locally, but they require a real revision rather than copy-editing. I have no concerns about attribution or scope; the Appendix is unusually candid but does not affect the theorems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper defines QSWI and argues that honest-verifier, malicious-verifier, and public-coin versions coincide, plus a quantum batch-proof-to-QSWI implication. The high-level approach is right, and I think the main theorems are probably true, but the written proofs don't yet support them. There are two specific gaps that need patching before I'd trust the details.\n\nWhat's genuinely new: the QSWI definition, the collapse of the three variants, and the corollary SWI ⊆ QSWI. The reduction to Kobayashi's machinery is sensible, and the paper correctly notes there's no classical analogue. The batch-proof compilation is a natural quantum extension of BKP+24, and the use of Drucker's distributional stability is appropriate. Credit also for including Appendix A, a failed batch-proof attempt with a real attack; that level of transparency is rare and useful.\n\nThe soft spots, in order of importance. First, Proposition 5.5 applies Corollary 2.3 to the full verifier view, but the output size of that view isn't bounded by ρt. The compression definition only bounds k·q_M, the total message communication; it says nothing about q_V, the verifier's private workspace, or about the batch instances x that the prover sends in the QSWI protocol. The stress-test note is right: as written, the O(√ρ) witness-indistinguishability error doesn't follow. This is likely fixable by arguing the view can be replaced by the transcript via a fixed efficient map, but that argument is absent.\n\nSecond, Lemma 4.5 (malicious verifier) is a sketch. The simulator post-selects on X=0 after applying the malicious verifier's transformation, but the state space bookkeeping is off—S(x,1) is a state on the honest verifier's registers, not on the adversary's auxiliary register, and the normalization after post-selection is hand-waved. Again, probably repairable following Kobayashi, but as written it doesn't prove the claim.\n\nThere are minor notation issues throughout, but nothing else that looks like a load-bearing error. The paper's honesty in the appendix and its clear discussion of the limitations (non-uniform prover, inverse-polynomial error) count in its favor.\n\nWho should read it: someone working on quantum interactive proofs or on the classical SWI question. It's a solid paper to give a serious referee, but the referee will need to ask for those two fixes. If I were handling it, I'd send it out and expect a revised version to be correct.","headline":"Fresh definition and plausible equivalences for QSWI, but the written proofs have two gaps—the view-qubit count in the batch-to-QSWI step and the malicious-verifier simulation—that need real work before the results are fully established.","tokens_in":21070,"tokens_out":6420,"would_cite":false,"duration_ms":62718,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q15","81P68"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"This paper defines quantum statistical witness indistinguishability (QSWI) and proves that its honest-verifier, malicious-verifier, and public-coin variants coincide: every honest-verifier QSWI proof can be made a 3-message public-coin proo","keywords":["QSWI","statistical witness indistinguishability","quantum interactive proofs","quantum batch proofs","public-coin protocols","quantum rewinding","distributional stability","statistical zero-knowledge"],"falsifier":"Build a ρ-compressing quantum batch proof whose honest verifier keeps a private register of Ω(t) qubits and measure the compiled protocol's witness-indistinguishability error: if the error grows with the private register size, the O(√ρ) bound fails as written. For the collapse theorem, exhibit a language in hvQSWI and a malicious quantum verifier that distinguishes two witnesses in every 3-message public-coin protocol for it.","tokens_in":20166,"feed_emoji":"⚛️","tokens_out":10137,"duration_ms":95814,"temperature":0.7,"pith_summary":"The paper introduces QSWI, the quantum analogue of statistical witness indistinguishability (SWI), and asks which relations admit interactive proofs whose transcript hides which valid witness the prover used. Its main claim is that the three natural definitions coincide: any problem with an honest-verifier QSWI proof has a 3-message public-coin QSWI proof secure against malicious quantum verifiers, so pubQSWI = QSWI = hvQSWI, with the witness-indistinguishability error inflated by at most a polynomial factor. Since classical SWI proofs are a special case, the equivalence yields SWI ⊆ QSWI. The paper further proves that any ρ-compressing quantum batch proof compiles into a QSWI proof with O(√ρ) witness-indistinguishability error using a non-uniform honest prover, extending the classical batch-proof-to-WI conversion of Bitansky et al. If true, this makes QSWI structurally tractable in ways SWI is not, and makes quantum batching of NP a concrete route to weak QSWI for all of NP.","feed_headline":"Quantum WI proofs collapse to 3 public-coin messages","feed_subtitle":"The same result places classical SWI inside QSWI and turns compressing quantum batch proofs into weak WI proofs.","key_machinery":"The load-bearing machinery is twofold. First, the unbounded-simulator characterization of witness indistinguishability: a protocol is QSWI exactly when an (unbounded) simulator can reproduce the verifier's view at every round, and this lets the paper carry over Kobayashi's three QSZK transformations — Kitaev-Watrous round compression, Marriott-Watrous private-coin to public-coin conversion, and Watrous rewinding — while preserving prover efficiency and tracking the WI error. Second, for the batch-to-QSWI theorem, the quantum distributional stability lemma: any map from t classical bits to ρt qubits is O(√ρ)-sensitive to a random input bit, which forces a ρ-compressing batch proof to lose the","core_discovery":"On the paper's own terms, the central discovery is that quantum statistical witness indistinguishability is robust across all reasonable definitions of the class: hvQSWI, QSWI, and pubQSWI are equal, and every honest-verifier QSWI proof can be transformed into a 3-message proof in which the verifier sends only random bits and cannot distinguish between any two valid witnesses even when malicious. The transformation chain — round compression following Kitaev and Watrous, private-coin to public-coin conversion following Marriott and Watrous, and malicious-verifier security via Watrous-style rewinding, all adapted from Kobayashi's QSZK framework — preserves the honest prover's efficiency and in","pith_inferences":["The Achilles heel of the batch-proof argument is that ρ-compressing constrains message qubits, not the verifier's private workspace, while the distributional-stability argument is applied to the full verifier view; a batch proof whose verifier keeps a large private register may need an extra workspace-dependent term in the WI error — this is my reading of the written proof, not a claim the paper m","The same simulator-based lens might extend the round-compression and public-coin machinery to QMA-style witness indistinguishability with quantum witnesses, which the paper mentions as future work but does not attempt.","The failed Grover-based batch protocol points to a concrete obstruction — a cheating prover's private register can suppress interference and break soundness — suggesting that quantum batching for NP, if achievable, needs a technique that does not rely on amplitude amplification over the prover's messages.","A numerical check on small instances of the distributional-stability lemma, comparing bit sensitivity of full views versus transcripts, would show whether the O(√ρ) bound is tight in the presence of private workspace."],"forward_implications":["Because SWI ⊆ QSWI, any structural property proved for QSWI — the paper singles out closure under complement — would immediately constrain SWI, and would separate SWI from NP unless the polynomial hierarchy collapses.","The class QSWI can be studied through 3-message public-coin protocols only, matching the structural simplicity that made QSZK tractable.","Any language with a sufficiently compressing quantum batch proof, with no privacy requirement on the batch proof, inherits a malicious-verifier QSWI proof with inverse-polynomial witness-indistinguishability error.","A quantum batch proof for all of NP would place NP in QSWI (with weak, inverse-polynomial WI error), giving a new conditional attack on the conjecture that NP is outside statistical WI."],"supporting_citations":[{"why":"Supplies the three QSZK transformations (round compression, private-coin to public-coin, malicious-verifier robustness) that the paper adapts to QSWI.","marker":"[Kob08]"},{"why":"The Kitaev-Watrous round-compression technique used in Lemma 4.1 to compress arbitrary hvQSWI protocols to three messages.","marker":"[KW00]"},{"why":"The Marriott-Watrous transformation that turns 3-message private-coin protocols into public-coin protocols, used in Lemma 4.4.","marker":"[MW05]"},{"why":"Watrous's quantum rewinding technique used in Lemma 4.5 to obtain security against malicious verifiers.","marker":"[Wat06]"},{"why":"Quantum distributional stability lemma used in Section 5 to bound the sensitivity of ρ-compressing functions and hence the WI error.","marker":"[Dru12]"},{"why":"The classical result that batch proofs imply statistical WI proofs, which the paper extends to the quantum setting.","marker":"[BKP+24]"},{"why":"Sparse minimax theorem used to select a polynomial-size non-uniform prover distribution for the batch-to-QSWI compilation.","marker":"[LY94]"}],"fun_headline_variants":["Quantum WI proofs collapse to 3 public-coin messages","QSWI: 3 public-coin messages for malicious verifiers","Honest-verifier QSWI equals full QSWI","Quantum batch proofs yield inverse-polynomial WI","SWI sits inside QSWI"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"In the batch-proof argument, the proof implicitly assumes that the verifier's full view of the interaction fits in O(ρt) qubits, even though the ρ-compressing condition only bounds the message communication and says nothing about the verifier's private workspace; if the private workspace is much larger, the stated O(√ρ) witness-indistinguishability error does not follow from the written argument.","fun_headline_variants_meta":{"raw":{"variants":["Quantum WI proofs collapse to 3 public-coin messages","QSWI: 3 public-coin messages for malicious verifiers","Honest-verifier QSWI equals full QSWI","Quantum batch proofs yield inverse-polynomial WI","SWI sits inside QSWI"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000783,"raw_usage":{"total_tokens":3266,"prompt_tokens":686,"completion_tokens":2580,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":2501}},"tokens_in":430,"tokens_out":2580,"duration_ms":21504,"temperature":1.0,"reasoning_tokens":2501,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:04:15.278848+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a ρ-compressing quantum batch proof whose honest verifier keeps a private register of Ω(t) qubits and measure the compiled protocol's witness-indistinguishability error: if the error grows with the private register size, the O(√ρ) bound fails as written. For the collapse theorem, exhibit a language in hvQSWI and a malicious quantum verifier that distinguishes two witnesses in every 3-message public-coin protocol for it.","supporting_citations":[],"review_version":1}