Pith. sign in

REVIEW 3 major objections 5 minor 2 references

No low-degree tests for quantum states

T0 review · 3 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2608.00265 v1 pith:5JNVLD6L submitted 2026-07-31 quant-ph cs.CC

Omar Alrabiah , Srinivasan Arunachalam , Sabee Grewal , John Wright This is my paper · ORCID
classification quant-phcs.CC MSC 81P6894B35 PACS 03.67.-a
keywords phasestatespropertytestingReed-Mullercodesaverage-casedecodingQMA(2)statedesignscopycomplexitylow-degree
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

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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 / 5 minor

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).

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 (3)
  1. [§1.1, Thm 1.1; §3.3, Thm 3.16] 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.
  2. [§3.3, Lemma 3.15] 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.
  3. [§5, Cor 3.14 / Thm 5.1] 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.
minor comments (5)
  1. [§1.1 / abstract] 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.
  2. [§3.3, Lemma 3.15 statement] 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.
  3. [§3.4, Theorem 3.25 proof] 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).
  4. [Appendix A] 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_χ.
  5. [§2 / §3] 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).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main lower bound is derived from internal quantum arguments plus external classical coding facts (ASW15, Heijnen–Pellikaan), not from the target result.

full rationale

The central derivation is self-contained. Theorem 3.2 reduces trace distance to the MAP-decoding success probability p_t_decode(C^⊥) via Lemmas 3.3–3.4, which are proved from the definitions; no term is defined in terms of the target. The Reed–Muller applications then invoke Corollary 3.14, whose proof (Section 5) is a q-ary generalization of the ASW15 decoding bound, using the external Heijnen–Pellikaan generalized-Hamming-weight formula (Theorem 5.9). That is independent, parameter-free support rather than a self-citation chain. The paper’s self-citations ([AGIMR25], [GK25]) appear only in the motivational QMA(2) discussion, and the asserted implication is explicitly stated with proof omitted; it is not used to prove Theorem 1.1. I flag two non-circular caveats: the omitted proof of the conditional QMA(2)=NEXP statement, and an apparent typo/off-by-one in Lemma 3.15 (C′ is written RM_q[m,2d_0−1] where Corollary 3.14 with parameter d_0 requires RM_q[m,2d_0+1]). These are correctness/verification concerns, not evidence that a prediction reduces to its input by construction.

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

No empirical parameters or invented entities. The central lower-bound chain uses external standard results (Reed–Muller duality, generalized Hamming weights, PGM optimality) plus internally proved lemmas. The only hand-chosen quantity is the proof parameter r. The QMA(2)=NEXP implication is asserted without proof but is not load-bearing for the copy-complexity theorem.

free parameters (1)
  • r (decoding/parameter-tuning integer) = maximized over [0,m]; e.g. r=⌊m/2⌋ in Theorem 3.16
    Appears in Cor 3.14/Lemma 3.15 as a free integer in [0,m]. The final lower bound maximizes over r. It is a proof optimization parameter, not an empirically fitted constant.
assumptions (5)
  • standard math Duality of q-ary Reed–Muller codes: RM_q[m,r]^⊥ = RM_q[m,m(q−1)−r−1].
    Used in Cor 3.14 and throughout §3.3 to identify C⊥ for degree-d phase states.
  • standard math Heijnen–Pellikaan formula for generalized Hamming weights of q-ary Reed–Muller codes (Theorem 5.9).
    Basis for Lemma 5.8 and Theorem 5.4; quoted rather than proved from scratch.
  • domain assumption The ASW15 binary Reed–Muller random-error correction program can be generalized to F_q using HP97 generalized Hamming weights.
    The paper extends [ASW15] instead of re-proving the binary theorem; the q-ary extension relies on HP97. If the cited binary result or its generalization has unstated restrictions, the RM decoding bound fails.
  • standard math Eldar–Forney optimality of the pretty-good measurement for geometrically uniform ensembles.
    Used for the learning characterization in Theorem 4.3; proof is supplied in Appendix A.
  • standard math Lévy's lemma concentration bound on the unit sphere.
    Used in Lemma 3.13 to bound the Haar measure of the neighborhood of flat phase states.

how reviews work

0 comments
Cite this review

Pith. "Pith review of No low-degree tests for quantum states." pith.science (2026). https://pith.science/paper/5JNVLD6L

@misc{pith2026260800265,
  author       = {Pith},
  title        = {Pith review of: No low-degree tests for quantum states},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5JNVLD6L}},
  note         = {Machine review of arXiv:2608.00265}
}
abstract

We study the problem of testing low-degree phase states, namely m-qudit quantum states of the form $q^{-m/2} \sum_{x \in \mathbb{F}_q^m} \omega^{f(x)} |x>$, where $f$ is a degree-$d$ polynomial. In contrast to the classical setting, where low-degree polynomials admit highly efficient classical testers, it is not known whether analogous quantum tests exist. We show that no such quantum low-degree test exists: any tester requires $\Omega(\binom{\lfloor m/2\rfloor}{\lfloor (d-1)/2 \rfloor})$ copies to determine whether a given state is a degree-$d$ phase state or is far from every such state. Our results follow from a general framework that relates quantum testing of codeword phase states to classical decoding properties of the dual code, which allows us to leverage known bounds on the tolerance of high-rate Reed--Muller codes to random errors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

2 extracted references · 1 linked inside Pith

  1. [2]

    Next, let {Mg}g∈G be any POVM withMg = UgM0U † g

    Hence tr √ρ= X χ∈ bG ∥|ϕχ⟩∥2. Next, let {Mg}g∈G be any POVM withMg = UgM0U † g. Since P χ Pχ = IH0 and P g∈G Mg = IH0 on H0, we have IH0 = X g∈G UgM0U † g = X g∈G Ug   X χ∈ bG Pχ  M0   X χ′∈ bG Pχ′  U † g = X χ,χ′∈ bG  X g∈G χ(g)χ′(g)  PχM0Pχ′ =|G| X χ∈ bG PχM0Pχ. Therefore, for everyχ∈ bG, IH0 =|G| X χ′∈ bG Pχ′M0Pχ′ ⇐ ⇒1 |G| PχIH0 Pχ = X χ′∈ ...

  2. [2023]

    Shadow Tomography of Quantum States

    arXiv:2305.20069 [quant-ph](page 2). 30 [Aar18] Scott Aaronson. “Shadow Tomography of Quantum States”. In:Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018.doi: 10.1145/3188745.3188802 .url: https: //doi.org/10.1145/3188745.3188802(page 21). [ABDY23] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder....

    arXiv 2018

Pith tools

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