{"id":"0466039e-20d9-4aff-aa65-db2b1fd1820d","arxiv_id":"2608.00265","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Testing degree-d phase states requires at least Ω(binomial(⌊m/2⌋,⌊(d−1)/2⌋)) copies, and degree-2 states require Ω(m), so no efficient quantum low-degree test exists in the studied regime.","lead":"This paper proves that testing whether a quantum state encodes a low-degree polynomial in its phases requires many copies of the state, not the few queries a classical low-degree test uses. The result blocks a leading route toward proving QMA(2)=NEXP and gives new limits on quantum state testing.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.1 hinges on the unverified q-ary Reed–Muller decoding bound (Cor. 3.14 / §5.2); if the Heijnen–Pellikaan weight identity fails in the required range, the copy lower bounds collapse.","rationale":"The proof chain for Theorem 1.1 is: (i) Theorem 3.2 + 3.7 give ρ_C^t ≈ ρ_Haar if p^t_decode(C^⊥) is close to 1; (ii) Lemma 3.9 converts this into a copy lower bound; (iii) for Reed–Muller codes, Corollary 3.14 supplies the required decoding bound. The entire weight of (iii) falls on Theorem 5.1/5.4, whose proof uses the Heijnen–Pellikaan formula to bound the size of the closure of evaluation points by q^r. This external theorem is cited but not re-derived, and the specific instantiation (d_a = q^m − q^r for a = N − D_{d,q}(r)) is asserted rather than proven. If this identity is wrong (or misapplied), the decoding bound fails and no lower bound follows. The reader's weakest assumption names exactly this dependence, so I agree with the reader's assessment. The off-by-one in Lemma 3.15 is a separate, easily fixable issue but reinforces that the proof needs careful checking. Because the reader already conditioned the verdict on verifying this decoding bound, my stress-test does not change the verdict.","tokens_in":36134,"tokens_out":27877,"duration_ms":229551,"concrete_test":"Verify the weight-hierarchy identity used in Lemma 5.8 by brute force for small parameters. For q=3, m=3, d=1 and q=5, m=2, d=1, enumerate all linear subcodes of RM_q[m,d] and compute the generalized Hamming weight d_a for a = N − D_{d,q}(r), r=0,1,2; check d_a = q^m − q^r. Separately, Monte Carlo–sample t≤D_{d,q}(r) random evaluation points in F_q^m and test linear independence of the corresponding columns of the generator matrix; compare the failure rate with t q^{r−m}. If the identity or the independence bound fails in any small instance, Corollary 3.14 is false and the main lower bound is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bound is obtained by applying Corollary 3.14 to the dual of RM_q[m,d]. Corollary 3.14 follows from Theorem 5.1, whose proof in §5.2 relies on Lemma 5.8, which uses Theorem 5.9 (Heijnen–Pellikaan) to assert the specific generalized Hamming weight identity d_a(RM_q[m,d]) = q^m − q^r for a = N − D_{d,q}(r). This identity is the load-bearing step: if it fails for any (q,m,d,r) in the stated range, the decoding success probability bound in Corollary 3.14 is not established, and with it the indistinguishability bound in Corollary 3.8 and hence the copy lower bounds (Theorems 3.16/1.1) collapse. The paper does not re-derive the HP theorem or the required corollary, so the main result rests on an unverified external computation. I also note an apparent off-by-one in Lemma 3.15: C' is defined as RM_q[m,2d_0−1], but applying Corollary 3.14 with the stated D_{d_0,q}(r) requires C' = RM_q[m,2d_0+1]; if this is not a typo, the proof has a gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the copy complexity of testing whether an unknown m-qudit state is a phase state |ψ_f⟩ = q^{-m/2} Σ_x ω^{f(x)}|x⟩ for a degree-d polynomial f over F_q, or is ε-far from every such state. The main claim is a lower bound of Ω(binomial(⌊m/2⌋, ≤⌊(d−1)/2⌋)) copies, and Ω(m) for d=2, interpreted as ruling out poly(m,d,q)-copy testers in the PCP-inspired parameter regime of Eq. (1). The proof develops a general framework: if the dual code C^⊥ is average-case decodable against t random errors, then the t-copy average codeword-state ensemble is close to the all-phase/Haar ensemble (Thm 3.2, Cor 3.8); together with a small Haar-neighborhood estimate (Lemma 3.13) this yields testing lower bounds. The main technical input is a q-ary generalization of Abbe–Shpilka–Wigderson (Thm 5.1), proved via random column independence and generalized Hamming weights from Heijnen–Pellikaan. A separate hyperplane-truncation argument handles degree 2 (Section 3.4).","tokens_in":36481,"tokens_out":21294,"duration_ms":186299,"significance":"If the result holds, it resolves the hyperefficient low-degree-test question negatively in the parameter regime relevant to QMA(2)=NEXP attempts, and it provides a clean reduction from quantum property testing to classical average-case decoding of dual codes. The paper gives a new q-ary Reed–Muller decoding theorem, a full proof of the Eldar–Forney optimality lemma, and careful design implications (Theorems 3.17–3.18). The framework is likely to be reused. However, the present statements overclaim in several places, and one central lemma contains an apparent off-by-one error; these should be fixed. The reliance on published coding theory (Heijnen–Pellikaan) is legitimate and I did not find a defect in the application.","major_comments":[{"comment":"The main theorem is stated more broadly than what is proved and used to draw a stronger conclusion than the lower bound supports. Theorem 3.16, which supplies the proof, requires ε<1−π/4 and 'for all sufficiently large m'; the degree-2 statement in §3.4 requires ε∈(0,1−1/q]. The text after Theorem 1.1 claims the bound 'rules out any tester using poly(m,d,q) copies'. For fixed d, the binomial bound is polynomial in m (e.g., d=3 gives Ω(m)), so it is fully compatible with a poly(m,d,q)-copy tester. The 'rule-out' conclusion only follows when d grows with m so that the binomial is superpolynomial, such as in Eq. (1). Please revise the theorem, abstract, and consequence paragraph to include the ε and m hypotheses and to state the PCP-regime conclusion precisely.","section":"§1.1, Thm 1.1; §3.3, Thm 3.16"},{"comment":"In the proof, C' is set to RM_q[m, 2d0−1] and Corollary 3.14 is then applied with parameter d0. Corollary 3.14 applies to codes of the form RM_q[m, 2d+1] and requires t≤D_{d,q}(r). With C'=RM_q[m, 2d0−1] the relevant degree is d0−1, and the hypothesis t≤D_{d0,q}(r) does not imply t≤D_{d0−1,q}(r). The intended code should be C'=RM_q[m, 2d0+1]. The lemma statement also omits the relation 2d0+1≤d that is used in the proof (in Theorem 3.16 this holds with d0=⌊(d−1)/2⌋). As written this is a gap in the central chain; please fix and restate.","section":"§3.3, Lemma 3.15"},{"comment":"The central lower bound depends on the q-ary Reed–Muller decoding bound, whose proof in §5.2 relies on the Heijnen–Pellikaan generalized Hamming weight identity (Thm 5.9). I checked the derivation in Lemma 5.8: the lexicographic argument gives d_a(RM_q[m,d])=q^m−q^r for the relevant a, and the parameter range appears consistent. Thus I do not see a correctness problem with using the published HP theorem. I do recommend, however, that the authors include the exact statement of Theorem 5.9 or a self-contained proof, since the entire lower bound collapses if this external identity is misapplied.","section":"§5, Cor 3.14 / Thm 5.1"}],"minor_comments":[{"comment":"The abstract and Theorem 1.1 do not state the restriction ε<1−π/4 or the 'sufficiently large m' condition. Also, for d=2 the general binomial formula gives Ω(1), so the separate Ω(m) statement should be explicitly tied to the ε range of Theorem 3.25.","section":"§1.1 / abstract"},{"comment":"The lemma statement says 'suppose d0 ≤ floor(m(q−1)−2)/2' but does not say how d0 relates to d; the proof uses 2d0+1≤d. Please state d0=⌊(d−1)/2⌋ (or the needed inequality) in the lemma.","section":"§3.3, Lemma 3.15 statement"},{"comment":"The phrase 'q^{t−m} → 0 as n→∞ unless t ≥ m + log_q(2/(3(q+2))) ≥ m−2' is imprecise because q^{t−m} is a step function of t−m. The intended threshold should be stated as an explicit inequality on t (which, as written, is also weaker than the proof actually gives for q≥3).","section":"§3.4, Theorem 3.25 proof"},{"comment":"In the Eldar–Forney proof, the line 'P_χ P_χ = I' should read 'Σ_χ P_χ = I' (or 'P_χ P_χ = P_χ'); as printed it contradicts the earlier orthogonality relation P_χ P_χ' = δ_{χ,χ'} P_χ.","section":"Appendix A"},{"comment":"The paper should explicitly state the convention that polynomials are reduced modulo x_i^q−x_i, so that the degree parameter satisfies d≤m(q−1). Without this, statements about degree-d phase states and D_{d,q}(r) are ambiguous for d≥m(q−1).","section":"§2 / §3"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct in substance and the framework is valuable. The main obstacles are the overclaim in Theorem 1.1 and the off-by-one in Lemma 3.15; both are fixable with a careful restatement. The reliance on Goppa–Heijnen–Pellikaan is standard and the application appears sound. I would not reject on the HP concern raised by the stress-test. Please require the authors to tighten the theorem statements before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core result is real and the framework is genuinely useful, but the advertised version is not the proven version. The paper shows that decodability of the dual code implies indistinguishability of codeword states, then leverages a q-ary Reed–Muller decoding bound to get strong copy lower bounds for testing low-degree phase states. That chain is coherent and mostly self-contained. The q-ary generalization of ASW15 is a nontrivial contribution, and the learning characterization via Rényi entropy is a nice bonus.\n\nThe soft spots are presentation and statement issues, not fatal flaws. First, Theorem 1.1 and the abstract omit the hypothesis ε < 1 − π/4. The proof needs that for the Haar-concentration argument; as written, the theorem claims more than it proves. Second, the displayed binomial bound is not the actual bound. The proof gives Ω(D_{d0,q}(⌊m/2⌋)), which for d ≥ m/2 is q^{Θ(m)}, not the binomial with floor((d−1)/2) in the bottom—that binomial is zero when d > m. The paper’s own Theorem 3.16 states the correct ≤ d0 version, but the abstract misleads. This matters because the PCP regime has d >> m; the real bound still rules out poly(m,d,q) copies, but the displayed formula would not. Third, the QMA(2)=NEXP implication is asserted without proof; it should be marked as a conditional claim. Fourth, the off-by-one in Lemma 3.15 is indeed a typo: C′ should be RM_q[m, 2d_0 + 1], not 2d_0 − 1. Easy fix.\n\nThe reliance on Heijnen–Pellikaan for generalized Hamming weights is acceptable—it is a standard theorem, and the paper gives the corollary they need. A referee should double-check the exact parameter range, but I see no red flag. The degree-2 Ω(m) bound comes from a different argument and looks sound.\n\nWho should read this: people in quantum property testing, quantum complexity, and coding theory. It deserves a serious referee. My recommendation: send it to peer review with a request to correct the statements, fix the typo, and qualify the complexity-theoretic aside. The core mathematics is solid.","headline":"Strong lower-bound framework, but the abstract and Theorem 1.1 overstate what is proven: the epsilon range is missing, the displayed binomial bound is not the actual bound in the high-degree regime, and the QMA(2) claim is unproven.","tokens_in":36970,"tokens_out":5959,"would_cite":true,"duration_ms":57107,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","94B35"],"pacs":["03.67.-a"],"model":"deepseek-v4-flash","headline":"The paper proves that any tester distinguishing an m-qudit degree-d phase state from states ε-far from all such states needs Ω(binomial(⌊m/2⌋,⌊(d−1)/2⌋)) copies, so no tester with poly(m,d,q) copies exists in the PCP-motivated parameter reg","keywords":["phase states","property testing","Reed-Muller codes","average-case decoding","QMA(2)","state designs","copy complexity","low-degree testing"],"falsifier":"Go looking for a violation of the key decoding estimate in a small case, e.g., compute the exact MAP-decoding success probability of RM_3[4,2] (the dual of RM_3[4,5]) against t = 1,...,6 random errors of the paper's type and compare with 1 − t/9. If the actual success probability falls below the claimed bound, the proof of the no-testing theorem fails at its load-bearing step; if it holds, the estimate survives this check.","tokens_in":36023,"feed_emoji":"⚛️","tokens_out":8928,"duration_ms":90931,"temperature":0.7,"pith_summary":"The paper claims that there is no efficient quantum analogue of the classical low-degree test: any procedure that decides whether a given m-qudit state is a degree-d phase state or ε-far from every such state must use at least a binomial number of copies, which is super-polynomial in the parameter regime relevant to PCP constructions. The proof works through a general framework: for any linear code C, if the dual code C⊥ can correct t random errors, then t copies of a random C-codeword phase state are information-theoretically indistinguishable from t copies of a uniformly random phase state. Applying this to Reed-Muller codes, and generalizing a binary decoding result to prime fields, yields the lower bound. A separate argument gives Ω(m) copies for degree-2 states, matching known upper bounds. A consequence is that the natural approach to proving QMA(2)=NEXP by simulating a PCP verifier with low-degree phase states cannot work with polynomially many copies.","feed_headline":"Superpolynomial copies needed for any quantum low-degree test","feed_subtitle":"To tell a degree-d phase state from far states takes a binomial number of copies, closing a PCP route to QMA(2)=NEXP.","key_machinery":"The central object is the codeword phase state |ψ_c⟩ = (1/√n) Σ_i ω^{c_i}|i⟩ for c in a linear code C, with degree-d phase states as the case C = RM_q[m,d]. The machinery has four pieces: (1) a dephasing channel that realizes the t-copy mixture of codeword states as a projective measurement; (2) an identity relating the trace distance between the coded and uniform mixtures to the MAP-decoding success probability of the dual code; (3) a random-error correction theorem for q-ary Reed-Muller codes, bounding how many random errors their duals can correct; and (4) a concentration lemma showing the neighborhood of flat-phase states has tiny Haar measure. The dual-code decoding probability carries","core_discovery":"The central discovery is a transfer principle: testing phase-state families reduces to classical average-case decoding of the dual code. Concretely, for a linear code C, the trace distance between t copies of a random C-codeword state and t copies of a uniformly random phase state is at most sqrt(1 − p_t_decode(C⊥)²), where p_t_decode is the maximum a posteriori decoding success probability against t random errors. Because degree-d phase states are exactly Reed-Muller codeword states, the paper proves that the dual Reed-Muller code corrects t random errors with probability at least 1 − t q^{r−m} for t up to the dimension of a lower-degree Reed-Muller code, and therefore a random degree-d pha","pith_inferences":["If the dual-code decoding estimate can be tightened, the same framework would likely upgrade the lower bound to Ω(m^{d−2}) or beyond, potentially matching the conjectured Θ(m^{d−1}/ε²) testing upper bound.","The framework is not specific to Reed-Muller codes: any code family whose duals correct t random errors gives the same indistinguishability bound, so similar no-testing results should hold for codeword states from algebraic-geometric or random high-rate codes.","The Rényi-entropy learning formula suggests a practical pipeline for new code families: compute the syndrome entropy of the dual code to get the exact sample complexity, then check whether a pretty-good measurement achieves it.","The approximate-design corollary hints that low-degree phase states can be used as explicit pseudorandom-state constructions; numerically measuring the trace distance for small m,q,d would show how quickly the t ≈ binomial threshold appears."],"forward_implications":["The hyperefficient-testing route to QMA(2)=NEXP via low-degree phase states is closed: poly(m,d,q) copies cannot suffice.","Random degree-d phase states form approximate state designs for t up to roughly the binomial bound, so they are much more Haar-random than their degree alone would suggest.","For degree-2 phase states over F_2, the Ω(m) lower bound matches the known O(m/ε²) testing upper bound, settling that case up to constants.","Learning C-codeword states has a classical formula: optimal copy complexity equals the point where the order-1/2 Rényi entropy of the syndrome distribution reaches log_q |C|.","The lower bounds hold for both fixed and growing field size q = poly(m), becoming stronger as q grows."],"fun_headline_variants":["Testing quantum phase states requires superpolynomial copies","No quantum low-degree test exists without many copies","Quantum low-degree testers need superpolynomial copies","Superpolynomial copies to test low-degree phase states","Quantum low-degree tests proven impossible"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"Everything rests on the claim that the dual q-ary Reed-Muller code can correct t random errors with probability close to 1 in the stated parameter range; if that classical decoding estimate fails, the indistinguishability proof and hence every copy lower bound in the paper fall apart.","fun_headline_variants_meta":{"raw":{"variants":["Testing quantum phase states requires superpolynomial copies","No quantum low-degree test exists without many copies","Quantum low-degree testers need superpolynomial copies","Superpolynomial copies to test low-degree phase states","Quantum low-degree tests proven impossible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000582,"raw_usage":{"total_tokens":2564,"prompt_tokens":718,"completion_tokens":1846,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":462,"completion_tokens_details":{"reasoning_tokens":1790}},"tokens_in":462,"tokens_out":1846,"duration_ms":15300,"temperature":1.0,"reasoning_tokens":1790,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T00:52:38.241664+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Go looking for a violation of the key decoding estimate in a small case, e.g., compute the exact MAP-decoding success probability of RM_3[4,2] (the dual of RM_3[4,5]) against t = 1,...,6 random errors of the paper's type and compare with 1 − t/9. If the actual success probability falls below the claimed bound, the proof of the no-testing theorem fails at its load-bearing step; if it holds, the estimate survives this check.","supporting_citations":[],"review_version":1}