{"id":"5d90129c-c876-464a-91dc-01da14d4dccc","arxiv_id":"2504.17650","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper defines and constructs pseudorandom quantum states for subpolynomial-time observers, proving that weaker observers can be fooled with less coherence, entanglement, and magic.","lead":"This paper introduces T-PRS, quantum state ensembles that look Haar-random to quantum algorithms running in subpolynomial time. It shows such states need fewer quantum resources when they must fool weaker computers, and gives constructions using pseudorandom functions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper never fixes the cost model for 'runtime': with depth-style runtime the subset-state construction fails a simple collision test for T=log n (and poly log n), while with gate-count runtime the resource-lower-bound proofs use Ω(n)-size distinguishers, leaving Tables I–III unsupported.","rationale":"The reader's verdict correctly identifies a gap in the copy-count handling, but the more fundamental issue is the unspecified notion of 'runtime'. Once a cost model is fixed, the problem sharpens: under a depth-style model, the construction for sublinear T is actually broken by a very simple collision test, and under a gate-count model, the paper's own resource-lower-bound distinguishers are not available to the restricted observers. Either way, the central claimed construction and the Section III resource bounds for T=log n and T=poly log n do not survive. The reader's weakest_assumption focused on the unspecified existence of T-QPRPF and T-QPRP primitives; that is a separate, conditional concern and is not the issue I would test first. Because the flaw concerns the core definitional framework and invalidates the advertised sublinear-T construction under a natural reading, I would move the verdict from CONDITIONAL to REJECT, while noting that a careful redefinition of the cost model and security notion could lead to a salvageable but substantially different claim.","tokens_in":24227,"tokens_out":23811,"duration_ms":267546,"concrete_test":"Fix an explicit cost model in Definition 10 and rerun the two key tests. (a) If runtime means circuit depth: for T(n)=log n, take L=log^2 n, t=L+1, and implement the collision test (measure all copies in the computational basis, then compute an AND/OR tree over equality of outcomes). Compute the distinguishing advantage between the subset-phase-state ensemble with |S|=L and the Haar ensemble; if it is ≥1-negl(logn), Theorems 17(1) and 21(1) are false as stated. (b) If runtime means circuit size: write out an explicit circuit for the projector Π_c2 used in Proposition 22 and for the SWAP test used in Proposition 23; count elementary gates. If either circuit has Ω(n) gates, verify that it cannot be run by an O(log n)-time observer under Definition 10; if it cannot, the derivations of eqs. (38), (57), and (79) for T=log n and T=poly log n are invalid, and Tables I–III need revision.","verdict_should_be":"REJECT","load_bearing_attack":"Definition 10 defines T-indistinguishability over every t(n) with s(nt(n)) ∈ O(T(n)), but Proposition 15 and the proofs of Theorems 17 and 21 only handle t(n) ∈ O(1) for the f(n) case. This is not just a proof gap: for T(n) = log n, choose a subset of size L = log^2 n (which is ω(log n)) and take t = L + 1 copies. Since log(n t) = log n + O(log log n) ∈ O(log n), such t is permitted by Definition 10. A depth-O(log n) algorithm can measure every copy in the computational basis and check whether two measured strings are equal. For a subset phase state or subset state of size L, the t outcomes are i.i.d. uniform over a fixed set of size L, so a collision is certain. For a Haar-random state, the collision probability is about t^2/2^n, negligible. This gives a T-time distinguisher with advantage near 1, contradicting Theorem 17(1) and Theorem 21(1) if 'runtime' means circuit depth. If instead 'runtime' means circuit size, the collision test is not a log-time algorithm, but then the resource lower-bound proofs fail: Propositions 22–24 use distinguishers such as the projector Π_c2 and the SWAP test on full n-qubit registers, which require Ω(n) elementary gates and are not available to an O(log n)-size observer. The paper calls the SWAP test 'constant-size' without justifying the cost model. Thus the central sublinear-T claims are not well-defined: the construction is false under a depth cost model, and the resource characterization is unproven under a gate-count cost model.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper generalizes pseudorandom quantum states (PRS) to a notion of T-PRS, where the distinguisher's runtime is bounded by a subpolynomial function T(n). It introduces T-negligible functions, defines T-indistinguishability, and proposes two constructions: subset phase states and subset states, built from T-quantum-secure pseudorandom phase functions and permutations. It then derives lower bounds on the coherence, entanglement, and magic of any low-resource ensemble that is T-indistinguishable from a high-resource ensemble, and tabulates how these required resources decrease as T goes from polynomial to logarithmic time. The central claims are Theorems 17 and 21 (the constructions) and Propositions 22–24 with Tables I–III (the resource characterization).","tokens_in":24566,"tokens_out":12651,"duration_ms":127731,"significance":"If the main theorems were valid, the paper would provide a useful framework for near-term pseudorandomness and an interesting quantitative connection between an observer's computational power and the amount of quantum resource that can be faked. The closure-property treatment of T-negligible functions is clean, and the resource lower-bound propositions are internally coherent derivations from the imposed indistinguishability assumption. The paper is also explicit that its constructions are conditional on T-secure pseudorandom primitives. However, the positive constructions and the resource bounds are not simultaneously supportable: the runtime model is never fixed, and the security definition demands indistinguishability for all allowed copy counts while the proofs only cover very restricted copy counts. These issues affect the paper's central claims, not merely its presentation.","major_comments":[{"comment":"Definition 10 defines T-indistinguishability by quantifying over every function t(n) such that s(nt(n)) ∈ O(T(n)) for the distinguisher's runtime s. However, Proposition 15 and Theorem 17 only establish indistinguishability for t(n) ∈ O(1) in the f(n) case, and Remark 16 explicitly restricts to this copy count. This is not a harmless simplification: for T(n) = log n and s(N) = O(log N), any polynomial t(n) = n^c satisfies s(nt(n)) = O(log n), so polynomial copy numbers are allowed by Definition 10. The proofs therefore do not establish that the constructed ensembles are T-PRS as defined.","section":"Section I.B, Definition 10; Section II.A, Theorem 17 and Remark 16"},{"comment":"Under a circuit-depth cost model, the constructions are falsified by a simple collision test. Take f(n) = log n and choose subset size |S| = n, which is allowed because n = ω(log n) and, for subset states, n < o(2^n). Let t(n) = n + 1. Since log(n(n+1)) = O(log n), this t(n) is permitted by Definition 10. A depth-O(log n) circuit can measure all t copies in the computational basis and check whether two of the t n-bit outcomes coincide, using an AND-tree comparison of O(log n) depth. For a subset phase state or subset state with |S| = n, the t outcomes are i.i.d. uniform over a fixed set of size n, so a collision is certain; for a Haar-random state, the collision probability is O(t^2/2^n), which is negligible. This gives a distinguisher with advantage 1, contradicting Theorems 17(1) and 21(1) if 'runtime' means circuit depth. The same construction with |S| = n^k and t = n^k + 1 works for polylogarithmic T.","section":"Section II.A, Theorem 17(1); Section II.B, Theorem 21(1)"},{"comment":"The resource lower-bound proofs use distinguishers that act on entire n-qubit registers: the projector Π_c2 in Proposition 22, the SWAP test in Proposition 23, and the Hadamard test in Proposition 24. If 'runtime' means circuit size (gate count), these distinguishers require Ω(n) gates or more, so they are not available to an O(log n)-time or O(polylog n)-time observer; the statement in the proof of Proposition 23 that the SWAP test is a 'constant-size' circuit is false in this model. If 'runtime' means circuit depth, these tests are cheap, but then the collision attack in the previous comment invalidates the T-PRS constructions. The manuscript never fixes the cost model, so the central claim that the positive constructions and the resource lower bounds coexist is not well-defined.","section":"Section III.A–C, Propositions 22–24"},{"comment":"The constructions are conditional on the existence of T-QPRPF and T-QPRP with evaluation time O(T(n)) and security against O(T(n))-time adversaries. No construction or supporting evidence for these primitives is provided for subpolynomial T, and the abstract's reference to standard quantum-secure pseudorandom functions and permutations is not the same as the T-secure primitives used in the proofs. The paper should state clearly that Theorems 17 and 21 are conditional on the existence of these stronger primitives and should discuss their plausibility, since the claimed 'constructions' otherwise rest on an unproven assumption.","section":"Definition 12 and Theorems 17 and 21"}],"minor_comments":[{"comment":"The notation Θ(T) is used for a family of functions T, but this is not standard and should be defined carefully, since T is a set of functions rather than a single function.","section":"Section I.A, Definition 3"},{"comment":"The caption contains a duplicated expression 'A(E_k[|ψ_k>])∈{0,1}' where the second occurrence should refer to the φ ensemble.","section":"Figure 1 caption"},{"comment":"The abstract says the constructions use 'quantum-secure pseudorandom functions and pseudorandom functions', while the body uses T-QPRPF and T-QPRP; the terminology should be aligned, and the word 'demonstate' should be corrected.","section":"Abstract and Section II"},{"comment":"Remark 16 says t(n) = O(1) is required to satisfy f(n)-indistinguishability, but this conflicts with the universal quantification over t(n) in Definition 10; the remark should be reconciled with the definition rather than simply stating the restriction.","section":"Remark 16"},{"comment":"Lemma 14 states that the subset phase state can be generated by a circuit of depth O(polyn), while the proof of Theorem 17 says the states can be generated 'in O(n)'; the manuscript should specify whether this is circuit size or depth, since the two notions behave very differently for sublinear T.","section":"Section II.A, Lemma 14 and Theorem 17 proof"},{"comment":"The caption contains an incomplete sentence ('We assume that Right column...') and should be rewritten.","section":"Table III caption"}],"recommendation":"reject","confidential_remarks":"The core problem is not fixable by small edits: the security definition, the runtime model, and the copy-count quantification need to be redesigned together. The collision attack shows the constructions fail under a depth cost model, while the resource lower bounds fail under a gate-count cost model, leaving no consistent interpretation of the paper's central claims. I would not invite a revision unless the authors substantially reformulate the framework and rework the main theorems."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this one: the T-PRS framework is a genuinely useful way to think about pseudorandomness against weaker observers, and the construction proofs as written only cover a restricted number of copies, which leaves the central sublinear-T claims unproven. There is also an unresolved ambiguity about what 'runtime' means, and the sublinear claims break under one natural reading.\n\nWhat is actually new: the T-negligible functions, the T-indistinguishability definition, and the resource lower bounds in Propositions 22–24. Those propositions are valid derivations from the indistinguishability assumption, and the tables showing that weaker observers can be fooled with less coherence, entanglement, and magic are a nice conceptual contribution. The linear and linearithmic cases, where the allowed number of copies is O(1), appear to go through.\n\nThe soft spots are real and load-bearing. Definition 10 requires indistinguishability for every t(n) with s(nt(n)) in O(T(n)). The proofs of Theorems 17 and 21 only establish it for t(n)=O(1) in the f(n) case and t(n)=O(poly f(n)) in the polyf(n) case. For T(n)=log n, t can be much larger than O(1): take t = n^2, then s(nt)=log(n^3)=3 log n, allowed. So the constructions are not shown to be T-PRS by the paper's own definition. The stress-test note makes this concrete: with t roughly log^2 n copies, a depth-O(log n) collision test distinguishes subset states from Haar with probability near 1. If 'runtime' means depth, the construction is simply false. If 'runtime' means circuit size, the collision test is not O(log n)-size, but then the resource lower-bound proofs fail too, because the SWAP test and the coherence projector on n-qubit registers require Omega(n) gates, which a log-size observer cannot run. So either way, the tables for T(n)=log n and polylog are unsupported.\n\nThe paper also assumes T-QPRPFs and T-QPRPs exist without constructing them. That is an honest assumption, but it is an additional primitive.\n\nIs the paper worth refereeing? Yes. The framework is new and the resource characterization is a solid conditional contribution. The flaws are serious but addressable: fix the cost model, prove security for all allowed t, or change the definition to match what is proved. I would not cite the sublinear claims as they stand, but I would send this to a serious referee rather than desk reject.","headline":"A useful new framework for weakening PRS, but the construction proofs cover fewer copies than the definition demands, and the unspecified runtime model undermines the sublinear claims.","tokens_in":25154,"tokens_out":4885,"would_cite":false,"duration_ms":46112,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper defines pseudorandom quantum states for sub-polynomial-time observers and shows they require fewer quantum resources as the observer's power shrinks.","keywords":["pseudorandom quantum states","near-term quantum computers","T-negligible functions","subset phase states","subset states","pseudoresource","coherence","entanglement"],"falsifier":"Exhibit a quantum algorithm with runtime O(T(n)) that, given O(1) copies of an f,S-subset phase state with |S| in omega(f(n)), guesses whether the input is from that ensemble or from the Haar-random ensemble with advantage larger than any T-negligible function. Since the proof reduces this to the trace-distance closeness of random subset phase states to Haar-random states, a direct computation showing a non-negligible trace distance for some f would also falsify the construction.","tokens_in":23944,"feed_emoji":"🎲","tokens_out":5374,"duration_ms":49061,"temperature":0.7,"pith_summary":"Pseudorandom quantum states (PRS) are ensembles that look Haar-random to efficient quantum algorithms, but \"efficient\" has always meant polynomial-time. This paper relaxes that to observers whose runtime grows slower than any polynomial, defining T-PRS for a runtime bound T(n). It gives two explicit constructions, based on subset phase states and subset states, and shows that if the subset is super-polylarge relative to f(n), the states are f(n)-PRS with constant copies, and poly(f(n))-PRS when the subset is super-polylarge relative to poly(f(n)) and the observer gets poly(f(n)) copies. The paper then proves that the minimum coherence, entanglement, and magic needed to impersonate Haar-random states decreases as the observer's computational power decreases, so computationally weaker observers can be fooled by cheaper quantum states.","feed_headline":"Cheaper quantum states pass near-term randomness tests","feed_subtitle":"Subset phase states need only super-polylog subset size to look Haar-random to sub-polynomial-time circuits.","key_machinery":"The load-bearing machinery is a parameterized notion of computational indistinguishability. A function is T-negligible if it is eventually smaller than 1/g(n) for every g in Theta(T), and the closure properties under addition and repetition, with repetition consistency, ensure that repeating a distinguishing test does not amplify success beyond negligibility. Indistinguishability is defined for algorithms whose runtime on t copies stays within O(T(n)). The explicit states are f,S-subset phase states, uniform superpositions over a subset S with phases (-1)^{f(x)}, and subset states, which drop the phase. Their security follows from a hybrid argument using T-quantum-secure pseudorandom phase functions and T-quantum-secure pseudorandom permutations, together with trace-distance bounds inherited from prior subset-phase and subset-state constructions. For resources, the proofs use constant-size circuits as distinguishers: a projective measurement for Hilbert-Schmidt coherence, the SWAP test for entanglement, and the Hadamard test for magic.","core_discovery":"The paper's central claim is that pseudorandomness does not require the full polynomial-time security framework. Theorems 17 and 21 state that subset phase states and subset states whose subset size is |S| in omega(f(n)) form f(n)-PRS with O(1) copies, and with |S| in omega(poly f(n)) form poly(f(n))-PRS with O(poly f(n)) copies, where f is any non-decreasing polynomially bounded function. Indistinguishability holds with respect to the paper's T-negligible functions and repeat-consistency conditions. For T equal to linearithmic, linear, polylogarithmic, and logarithmic, the paper derives lower bounds on the expected relative entropy of coherence, entanglement entropy, and stabilizer Renyi entropy of any ensemble that is T-indistinguishable from Haar-random; these bounds fall as T falls, yielding larger pseudoresource gaps for weaker observers.","pith_inferences":["If T-quantum-secure pseudorandom phase functions and permutations exist for subpolynomial T, then near-term hardware would only need to prepare subset states with modestly large subsets to pass subpolynomial-time scrutiny; this is a directly testable prediction on small devices.","The resource lower bounds are necessary conditions, not sufficiency: a state with the required coherence, entanglement, or magic need not be pseudorandom, and the paper's constructions are one explicit way to meet the bounds.","The same T-indistinguishability formulation could convert any resource-versus-observer tradeoff into a quantitative relation whenever a small distinguishing circuit is known, potentially covering resources beyond coherence, entanglement, and magic.","The paper leaves open the case where the generator is also T-bounded rather than polynomial-time; if that were achieved, T-PRS would be useful for low-power preparation, not only low-power verification."],"forward_implications":["Subset phase states with |S| in omega(f(n)) are f(n)-PRS with constant copies, and subset states with omega(f(n)) < |S| < o(2^n) are f(n)-PRS with constant copies.","With |S| in omega(poly f(n)) and O(poly f(n)) copies, both families are poly(f(n))-PRS.","Any ensemble that is T-indistinguishable from Haar-random must carry at least the stated expected coherence, entanglement, and magic; for weaker observers these required amounts shrink, implying that near-term devices can use lower-resource states to mimic randomness.","The pseudoresource gap between a T-PRS and the Haar-random ensemble sits strictly between the gap for polynomial-time PRS and the zero-resource gap of pseudorandom density matrices.","The T-framework can be applied to other pseudorandom objects, including pseudorandom density matrices, function-like states, unitaries, and isometries."],"supporting_citations":[{"why":"Introduces pseudorandom quantum states and sets the polynomial-time indistinguishability baseline that this work relaxes.","marker":"[1]"},{"why":"Supplies the subset phase state construction and the trace-distance bound t^2/2^m used in Theorem 17.","marker":"[4]"},{"why":"Supplies the subset state construction and the trace-distance bound O(tm/2^n + t^2/m) used in Theorem 21.","marker":"[6]"},{"why":"Defines pseudorandom density matrices, the zero-resource benchmark that the T-pseudoresource gaps are compared against.","marker":"[9]"},{"why":"Gives the coherence-based pseudoresource argument and the omega(log n) lower bound that this work generalizes to other T.","marker":"[22]"},{"why":"Supplies the stabilizer Renyi entropy and pseudomagic framework, including the Hadamard-test relation used for magic gaps.","marker":"[23]"},{"why":"Provides the classical treatment of negligible functions and closure properties that motivates Definitions 1 and 7.","marker":"[24]"}],"fun_headline_variants":["Subset states fake randomness for slow quantum circuits","Near-term pseudorandom states need less coherence","Sub-polynomial-time observers can't tell cheap states","Pseudorandomness for weak quantum computers","Slow circuits see cheaper states as Haar-random"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The constructions inherit their security from T-quantum-secure pseudorandom phase functions and permutations for the same runtime bound T; if no such primitives exist for subpolynomial T, the explicit T-PRS constructions collapse.","fun_headline_variants_meta":{"raw":{"variants":["Subset states fake randomness for slow quantum circuits","Near-term pseudorandom states need less coherence","Sub-polynomial-time observers can't tell cheap states","Pseudorandomness for weak quantum computers","Slow circuits see cheaper states as Haar-random"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000202,"raw_usage":{"total_tokens":1444,"prompt_tokens":1066,"completion_tokens":378,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":682,"completion_tokens_details":{"reasoning_tokens":308}},"tokens_in":682,"tokens_out":378,"duration_ms":4450,"temperature":1.0,"reasoning_tokens":308,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:38:02.131391+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a quantum algorithm with runtime O(T(n)) that, given O(1) copies of an f,S-subset phase state with |S| in omega(f(n)), guesses whether the input is from that ensemble or from the Haar-random ensemble with advantage larger than any T-negligible function. Since the proof reduces this to the trace-distance closeness of random subset phase states to Haar-random states, a direct computation showing a non-negligible trace distance for some f would also falsify the construction.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces pseudorandom quantum states and sets the polynomial-time indistinguishability baseline that this work relaxes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the subset phase state construction and the trace-distance bound t^2/2^m used in Theorem 17."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the subset state construction and the trace-distance bound O(tm/2^n + t^2/m) used in Theorem 21."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines pseudorandom density matrices, the zero-resource benchmark that the T-pseudoresource gaps are compared against."},{"cited_title":"T(n) = O(n logn), first note that for g(n) ∈ O(n logn), it holds that there exists c > 0 and N ∈ N such thatg(n)<cn logn ifn>N, which is equivalent to g(n)∈O(1)n logn","cited_arxiv_id":null,"evidence_quote":"Gives the coherence-based pseudoresource argument and the omega(log n) lower bound that this work generalizes to other T."},{"cited_title":"(49) Thus the expected relative entropy of coherence of {∣ψ⟩} is lower bounded as Eψ[C(ψ)]≥− log(2−O(1)−logn) =ω(1)+ logn","cited_arxiv_id":null,"evidence_quote":"Supplies the stabilizer Renyi entropy and pseudomagic framework, including the Hadamard-test relation used for magic gaps."},{"cited_title":"T(n) = O(poly log(n))), first note that poly logn = logO(1)n = 2log(logO(1)n) = 2O(log logn)","cited_arxiv_id":null,"evidence_quote":"Provides the classical treatment of negligible functions and closure properties that motivates Definitions 1 and 7."}],"review_version":1}