{"id":"d2b1aab5-56ca-42a6-98e6-22729bbe68b7","arxiv_id":"2507.18796","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Any approximate quantum state 2-design is unconditionally pseudorandom against QNC0 and AC0 after QNC0 adversaries, with analogous pseudoentanglement and parallel-query unitary-design results.","lead":"Quantum objects called 2-designs, which can be generated efficiently, are shown to be indistinguishable from fully random quantum states and unitaries to any shallow-depth quantum circuit, with no cryptographic assumptions needed. This supplies the first unconditional pseudorandom quantum objects for near-term-style circuit families, connecting design theory, complexity, and quantum pseudorandomness.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.4's summation step drops a factor of t and the proof as written does not establish the stated concentration bound; the PRU theorems appear repairable but need this corrected.","rationale":"The reader's verdict is CONDITIONAL, and I agree that the concentration lemmas are the load-bearing bridge from second-moment matching to indistinguishability. I agree with the reader that Corollary 4.4 contains a false summation inequality and that the proof needs repair. However, I find the Corollary 3.3 'exponent mismatch' largely benign: the missing 2^k and t factors are absorbed by the n^{O(k)} term in every application (Theorems 3.4, 3.5, 3.9, 3.11, and Corollaries 3.12 and 3.13), since k is either lightcone-bounded or log^{O(1)} n while ε is negligible. The substantive gap is the t factor in Corollary 4.4, which propagates to Corollary 4.5 and the PRU theorems. Because t = poly(n) and the other terms are exponentially or quasi-polynomially small in the stated parameter regimes, the t factor does not invalidate the main theorems; the proof is incomplete but repairable. I found no circularity, no fitted parameters, and no evidence that the high-level lightcone argument fails. The paper presents a significant advance with a clear proof strategy, but the written proof of the PRU concentration lemma is not yet complete. Thus the verdict should remain CONDITIONAL pending the correction, not ACCEPT and not REJECT. The disagreement with the reader is only about which of the two flagged issues is truly load-bearing; the overall assessment is unchanged.","tokens_in":21861,"tokens_out":33652,"duration_ms":327486,"concrete_test":"Re-derive the expectation bound in Corollary 4.4 while preserving the exact identity ∑_{i,j: j≠i}|a_i a_j| = (∑|a_i|)^2 − ∑|a_i|^2 and keeping the sum over τ. Verify whether the failure probability becomes 1 − O(rt)·2^{k−n/2}·δ^{−1} instead of 1 − O(r)·2^{k−n/2}·δ^{−1}. Then substitute this corrected bound into Corollary 4.5 and Theorem 4.6, checking that 2^{O(k)}·r·t·(ε + 2^{−n})^{1/2} ≤ n^{−ω(1)} for t = poly(n), ε = 2^{−Ω(n)}, k = o(n), and r ≤ 4^d. Also re-check Theorem 4.7 with ε = 2^{−log^{ω(1)} n}. If the inequality holds in all stated regimes, the concern is a patchable technical gap; if any regime fails, the main PRU theorem needs a different proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The PRU results rest on Corollaries 4.4 and 4.5, which assert that after applying a Haar unitary (or an approximate unitary 2-design) in parallel, the reduced state on any k-qubit subsystem is close to maximally mixed with failure probability O(r)·2^{k−n/2}·δ^{−1}. In the proof of Corollary 4.4, after summing over the recursive Schmidt-decomposition branches, the authors use the identity ∑_{i1,...,iτ}∑_{jτ≠iτ} |α_{i1...iτ} α_{i1...iτ−1,jτ}| = ∑_{i1...iτ−1} (∑_{iτ} |α_{i1...iτ}|)^2. This equality is false: the left-hand side is (∑|a_i|)^2 − ∑|a_i|^2. The inequality direction needed for an upper bound is true, so this part is patchable. More seriously, the subsequent bound ∑_{τ=1}^t r·2^{(kτ−n)/2} ≤ r·2^{(k−n)/2} uses ∑_τ 2^{kτ/2} ≤ 2^{k/2}, which is false in general; the correct upper bound is t·2^{(k−n)/2}. The same missing factor t appears in the hybrid argument for the diagonal terms. Thus the claimed failure probability O(r)·2^{k−n/2}·δ^{−1} in Corollary 4.4 is not established; the correct bound at this level of proof is O(rt)·2^{k−n/2}·δ^{−1}. In the parameter regimes of Theorems 4.6 and 4.7, t = poly(n), ε = 2^{−Ω(n)} or 2^{−log^{ω(1)} n}, and k = o(n) or k = log^{O(1)} n, so the extra t factor is absorbed and the main theorems survive with a corrected constant. Corollary 3.3 has a related but milder issue: the proof transitions from (ε + 2^{k−n})^{1/2} to (ε + 2^{−n})^{1/2}, but the additional 2^k and t factors are absorbed by the n^{O(k)} term in the regimes where k is used, so this does not threaten the state-PRS results. The central claim is therefore plausible, but Corollary 4.4 as written is a genuine gap in the proof of the PRU theorems.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies unconditional pseudorandomness against shallow quantum circuit classes. It claims that every approximate 2-design state ensemble is a PRS against QNC^0 circuits with arbitrarily many ancillae (Theorem 3.4, Corollary 3.5) and against AC^0∘QNC^0 circuits with polylogarithmically many ancillae (Theorem 3.11, Corollary 3.12); that random phased subspace states yield pseudoentanglement (Corollary 3.13); and that every approximate unitary 2-design is a non-adaptive secure PRU against 1-dimensional geometrically local QNC^0 circuits (Theorems 4.6 and 4.7). The proof strategy combines lightcone arguments with concentration estimates showing that reduced states on small subsystems of t copies of a 2-design are close to maximally mixed, together with a generalization of Braverman's theorem to high min-entropy distributions.","tokens_in":22281,"tokens_out":10692,"duration_ms":103790,"significance":"The central conceptual message—that matching two Haar moments can suffice for computational pseudorandomness against natural constant-depth circuit classes—is novel and, if the technical estimates are corrected, would be an important result. It provides the first unconditional PRS and PRU constructions against restricted quantum adversaries and sharply contrasts with the BQP setting, where two-copy indistinguishability is insufficient. The paper is also methodologically transparent: the constructions are reductions from the external 2-design property, no fitted parameters appear, and the parameter regimes are stated explicitly. No machine-checked proofs or code are provided, but the main reductions are accessible to hand verification once the concentration lemmas are repaired.","major_comments":[{"comment":"The probability bound as stated is not what the proof establishes. From Lemma 2.7 the proof obtains E[Tr(ρ_A^2)−2^{−k}]^{1/2} ≤ (ε+2^{k−n})^{1/2}; the subsequent trace-norm bound should therefore contain a factor 2^{k/2} and the term (ε+2^{k−n})^{1/2}, not (ε+2^{−n})^{1/2} with a 2^k prefactor. Because Corollary 3.3 is the bridge used in Theorems 3.4, 3.11, and Corollary 3.13, this mismatch must be fixed. In the intended regimes k=o(n) and ε=2^{−Ω(n)} the corrected bound is still negligible, so the main theorems appear repairable, but the statement and proof need to be made consistent.","section":"§3, Corollary 3.3"},{"comment":"The claimed failure probability is not established. The equality used to replace Σ_{i1,...,iτ} Σ_{jτ≠iτ} |α_{i1...iτ} α_{i1...iτ−1,jτ}| by Σ_{i1...iτ−1} (Σ_{iτ} |α_{i1...iτ}|)^2 is false; the left-hand side equals (Σ|α_i|)^2 − Σ|α_i|^2. The subsequent bound Σ_{τ=1}^t r·2^{(kτ−n)/2} ≤ r·2^{(k−n)/2} is also unjustified because Σ_τ 2^{kτ/2} ≤ 2^{k/2} is false in general; the correct upper bound carries a factor t. The same missing factor t appears in the hybrid argument for the diagonal terms. As written the lemma gives only O(rt)·2^{k−n/2}δ^{−1}. Since t=poly(n) in Theorems 4.6 and 4.7, the extra factor is absorbed and those theorems appear salvageable, but Corollary 4.4 must be corrected before Theorem 4.6 is fully proved.","section":"§4, Corollary 4.4"}],"minor_comments":[{"comment":"The proof of Lemma 3.10 contains an apparent typo: the first bullet after invoking Braverman's lemma refers to D′_2, whereas the subsequent min-entropy argument concerns D_1 and transfers bounds from the uniform distribution via the 2^r factor; the intended statement should be clarified.","section":"§3, Lemma 3.10"},{"comment":"The role of ancillae is left implicit: Corollaries 3.2 and 3.3 apply to the input state copies, while ancillae have fixed initial states. The proof should state explicitly that the ancilla part of the lightcone contributes the same deterministic state in both ensembles, so the trace-distance bound applies only to the input-qubit part of the lightcone.","section":"§3, Theorem 3.4 and Corollary 3.5"},{"comment":"There are several small typos: 'an QNC0 circuit' in the Figure 1 caption, 'techinical issue' and 'lower bound lower bound' in Section 5, and a duplicated 'every' in Definition 2.3.","section":"Throughout"},{"comment":"The symbol R is used both for the corrupted-qubit subsystem and for the output distribution on those bits; using a different symbol for the distribution would improve readability.","section":"§3, Theorem 3.11"}],"recommendation":"major_revision","confidential_remarks":"The two concentration lemmas flagged in the major comments are genuinely load-bearing, but both appear repairable with straightforward constant tracking, and the conceptual contributions are solid. I recommend major revision rather than rejection. The paper does not hide assumptions: the design property is an external input, and the reductions are transparent. The main risk is that the current statements of Corollaries 3.3 and 4.4 are not proven, so the revision should restate and reprove those lemmas carefully before the derived theorems are relied upon."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the first unconditional quantum pseudorandomness against any natural circuit class, and the core idea—two Haar moments suffice when the adversary's lightcone is small—is genuinely new and, I think, correct. The paper is worth engaging with seriously, but the proofs of the concentration lemmas need repair before I would call them complete.\n\nWhat's new: the theorems that any epsilon-approximate state 2-design is a PRS against QNC0 with arbitrary ancillae, and against AC0◦QNC0 with polylog ancillae; the pseudoentanglement construction from 4-wise independent phased subspace states; and the parallel-query PRU security of unitary 2-designs against 1D geometrically local QNC0. None of these appears in prior work, and they change the picture one might have had from BQP adversaries, where two copies are far from enough. The paper also does a good job of explaining why the lightcone argument stops at QNC0/AC0, and Lemma 3.10, a min-entropy generalization of Braverman's theorem, is a nice technical contribution on its own.\n\nSoft spots: two technical gaps, both in the concentration machinery. Corollary 3.3 states a failure probability with (epsilon+2^{-n})^{1/2}, but the proof's intermediate bound gives (epsilon+2^{k-n})^{1/2}; the claimed bound is true, but the line \"E <= 2^k (epsilon+2^{-n})^{1/2}\" does not follow as written. In the regimes used, the extra factors are absorbed by the n^{O(k)} term, so the state PRS results survive. Corollary 4.4 is more serious. The identity used to sum the Schmidt branches is false: the left-hand side is (sum|a_i|)^2 - sum|a_i|^2, not (sum|a_i|)^2. And the bound sum_tau 2^{k_tau/2} <= 2^{k/2} is also false; the correct upper bound has a factor of t. So the stated O(r)·2^{k-n/2} delta^{-1} failure probability is not established; the proof at this level gives O(rt)·2^{k-n/2} delta^{-1}. Since t = poly(n) and k = o(n) in Theorems 4.6 and 4.7, the extra t is absorbed and the main theorems likely survive, but only after the lemma is fixed. This is a genuine gap in the written proof of the PRU claims, not a mere typo.\n\nThe citation pattern looks fine; prior constructions do rely on cryptographic assumptions, and the paper credits the relevant QAC0 and Braverman-type results.\n\nWho should read it: anyone working on quantum pseudorandomness, shallow-circuit complexity, or near-term quantum advantage. I would put it on a reading group list and would cite the main theorem in my own work.\n\nRecommendation: send to peer review. A serious referee should be able to verify the patch; the conceptual contribution is strong enough that this deserves journal-level attention after the concentration lemmas are corrected.","headline":"First unconditional quantum pseudorandomness against shallow circuits, with a patchable gap in the PRU concentration lemma; deserves a serious referee.","tokens_in":22896,"tokens_out":5589,"would_cite":true,"duration_ms":51766,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every approximate state 2-design is unconditionally pseudorandom against shallow quantum circuits.","keywords":["quantum pseudorandomness","state 2-designs","unitary 2-designs","QNC0","AC0 composed with QNC0","pseudoentanglement","shallow quantum circuits","unconditional security"],"falsifier":"Recompute Corollary 3.3 exactly: Lemma 2.7 gives $E[\\mathrm{Tr}(\\rho_A^2)-2^{-k}] \\le \\varepsilon + 2^{k-n}$, not $\\varepsilon + 2^{-n}$, so the claimed failure probability $n^{O(k)}(\\varepsilon + 2^{-n})^{1/2}\\delta^{-1}$ must be corrected. Also test the summation inequality in the proof of Corollary 4.4 on a concrete recursive Schmidt decomposition; if it fails for some valid state, the claimed failure probability $O(r)2^{k-n/2}\\delta^{-1}$ is not established and the parameter choices for Theorem 4.6 would need adjustment.","tokens_in":2172,"feed_emoji":"","tokens_out":4448,"duration_ms":122979,"temperature":0.7,"pith_summary":"This paper proves that quantum pseudorandomness can be obtained with no cryptographic assumptions at all when the distinguisher is a shallow quantum circuit. The central claim is that any efficient approximate state 2-design - an ensemble matching the first two Haar moments - is already indistinguishable from Haar-random states for QNC0 circuits of constant depth and for AC0 composed with QNC0 circuits with limited ancillae, and that any unitary 2-design is a non-adaptive pseudorandom unitary against one-dimensional geometrically local QNC0 circuits. It also constructs unconditionally pseudoentangled states from random phased subspace states whose phases come from a 4-wise independent function. If correct, these results close the gap between statistical and computational pseudorandomness for shallow adversaries: matching two copies of a Haar object is enough, whereas against polynomial-time quantum distinguishers extra copies break the illusion. The bridge is a concentration phenomenon: in a 2-design, the reduced state on any small subsystem of many copies is close to maximally mixed, so the small lightcone of a shallow circuit cannot tell the ensemble from Haar.","feed_headline":"Two Haar moments fool shallow quantum circuits","feed_subtitle":"State and unitary 2-designs are pseudorandom against shallow circuits, no cryptographic assumptions needed.","key_machinery":"The key mechanism is a lightcone argument combined with concentration estimates. Because a depth-$d$ shallow circuit has each output depending on only $k=2^{O(d)}$ input qubits, indistinguishability reduces to comparing reduced states on $k$-qubit subsystems. The paper's Corollaries 3.2 and 3.3 state that for a Haar random state or an approximate 2-design, the reduced state on every small subsystem of $t$ copies is close to maximally mixed, with failure probability bounded by an explicit expression. For the unitary results, Lemma 4.3 bounds the expected Frobenius norm of partial traces of off-diagonal terms conjugated by a Haar random unitary, and Corollaries 4.4 and 4.5 combine this with a recursive Schmidt decomposition of the output of a one-dimensional geometrically local shallow circuit. For the AC0 post-processing step, Lemma 3.10 extends Braverman's theorem that polylogarithmic independence fools AC0 to distributions that are only almost $k$-wise indistinguishable but have high min-entropy, which is what limits the ancilla count.","core_discovery":"On its own terms, the paper establishes that every approximate state 2-design with negligible error is an unconditionally secure pseudorandom state against QNC0 circuits with arbitrarily many ancillae, and against AC0 composed with QNC0 circuits with almost linear ancillae for exact designs. It also establishes that every unitary 2-design is a non-adaptive secure pseudorandom unitary against one-dimensional geometrically local QNC0 circuits, even with limited AC0 post-processing, and that random phased subspace states with 4-wise independent phases are unconditionally pseudoentangled against these classes. The defining feature is that the only structural property required is matching two Haar moments; no one-way functions or other complexity assumptions appear. The paper's main theorems are Theorem 1.1, Corollary 3.5, Theorem 4.6, Theorem 4.7, and Corollary 3.13.","pith_inferences":["The same lightcone-plus-concentration recipe may apply to other circuit classes with polylogarithmic lightcones, such as shallow Clifford circuits or noisy intermediate-scale devices; this is an extension the authors did not pursue.","If the concentration estimates are repaired, the pseudoentanglement construction is efficiently preparable, so it could be implemented on near-term hardware as a direct experimental test of the theory.","The results sharpen the contrast with the BQP setting: pseudorandomness against shallow circuits is not a weaker version of the standard notion but a different phenomenon, where two-copy statistical matching already implies computational indistinguishability.","The authors conjecture that 2-designs also fool QAC0 circuits; a natural next test is whether the min-entropy extension of Braverman's theorem has a quantum analogue for unbounded fan-out gates."],"forward_implications":["Any efficiently implementable state 2-design becomes a drop-in unconditionally secure pseudorandom state for shallow quantum distinguishers, with no cryptographic setup required.","Against QNC0 the security holds even with arbitrarily many ancillae, so the result covers realistic near-term circuits where auxiliary qubits are freely available.","Unitary 2-designs yield parallel-query pseudorandom unitaries against one-dimensional geometrically local QNC0 circuits, giving a simple shallow-circuit construction of a quantum pseudorandom unitary.","Random phased subspace states give the first unconditional pseudoentanglement against these shallow classes, with entanglement entropy at most $d$ across every cut.","As the paper notes, the same 2-design property cannot give security against BQP adversaries, since any $t$-design is distinguishable from Haar with more than $t$ copies; the shallow-circuit result is therefore not a path to standard assumption-free pseudorandomness."],"supporting_citations":[{"why":"Provides the Haar reduced-state second-moment formula that seeds the concentration bounds.","marker":"[Lub78; LLZ+18]"},{"why":"Supplies the Haar-measure tools and symmetric-subspace projection used to compare designs with Haar objects.","marker":"[Mel24]"},{"why":"Shows that polylogarithmic independence fools AC0 circuits, the engine behind the AC0 post-processing theorem.","marker":"[Bra08]"},{"why":"Tightens the AC0 approximation parameters used in Lemma 3.8.","marker":"[Tal17]"},{"why":"Improves the polynomial approximation to AC0 used in Lemma 3.8.","marker":"[HS19]"},{"why":"Provides the conversion between almost $k$-wise indistinguishability and $k$-wise indistinguishable distributions used in Lemma 3.10.","marker":"[BIV+16]"},{"why":"Shows that subspace states are efficiently preparable, making the pseudoentanglement construction efficient.","marker":"[KP22]"},{"why":"Gives the Haar collision probability used in the distinguishing example separating $t$-designs from Haar with $d+1$ copies.","marker":"[DHB22]"},{"why":"Introduces the AC0 composed with QNC0 hybrid model and its parity hardness, fixing the adversarial class for the hybrid results.","marker":"[Slo24]"}],"fun_headline_variants":["Two Haar moments: unconditional security for shallow quantum circuits","Shallow circuits can't tell: two Haar moments is all it takes","No assumptions needed: two Haar moments fool shallow quantum circuits","Two Haar moments: unconditional quantum pseudorandomness for shallow circuits"],"cache_read_input_tokens":24704,"weakest_assumption_plain":"The load-bearing premise is that every small-subsystem reduced state of many copies of a 2-design, or of Haar objects after shallow pre-processing, is close to maximally mixed with the failure probability stated in Corollaries 3.3 and 4.4; as written, those two concentration estimates contain an exponent mismatch and an invalid summation inequality, so the proofs need repair before the main theorems are fully established.","fun_headline_variants_meta":{"raw":{"variants":["Two Haar moments: unconditional security for shallow quantum circuits","Shallow circuits can't tell: two Haar moments is all it takes","No assumptions needed: two Haar moments fool shallow quantum circuits","Two Haar moments: unconditional quantum pseudorandomness for shallow circuits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001314,"raw_usage":{"total_tokens":5369,"prompt_tokens":976,"completion_tokens":4393,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":4322}},"tokens_in":592,"tokens_out":4393,"duration_ms":28769,"temperature":1.0,"reasoning_tokens":4322,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:09:12.381099+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute Corollary 3.3 exactly: Lemma 2.7 gives $E[\\mathrm{Tr}(\\rho_A^2)-2^{-k}] \\le \\varepsilon + 2^{k-n}$, not $\\varepsilon + 2^{-n}$, so the claimed failure probability $n^{O(k)}(\\varepsilon + 2^{-n})^{1/2}\\delta^{-1}$ must be corrected. Also test the summation inequality in the proof of Corollary 4.4 on a concrete recursive Schmidt decomposition; if it fails for some valid state, the claimed failure probability $O(r)2^{k-n/2}\\delta^{-1}$ is not established and the parameter choices for Theorem 4.6 would need adjustment.","supporting_citations":[],"review_version":2}