{"id":"db9c78e2-8f9a-48ca-9a20-733d61975938","arxiv_id":"2509.07276","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new distribution of underdetermined degree-3 polynomial systems over F2 is provably solvable by an expected polynomial-time quantum algorithm, with classical hardness conjectured, yielding a candidate non-relativized quantum advantage.","lead":"This paper designs a family of random degree-3 polynomial equations over F2 that a quantum computer can provably solve in expected polynomial time, while classical hardness is conjectured. If correct, it offers a clean, non-interactive candidate for demonstrating quantum advantage without relying on periodicity.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.8's union bound uses wrong Hamming weight endpoint, understating bad-error probability; the stated α range and example may fail.","rationale":"The reader's weakest_assumption correctly identified that Lemma 4.8 is load-bearing and internally inconsistent, pointing to the S* complement issue and the alpha-inequality discrepancy. My independent check confirms the complement typo and goes further: the probability bound in Eq. (11) uses (1/2+ε) as the Hamming weight of the error support when an upper bound requires the minimum possible weight (1/2-ε). This is not merely a typo; it changes the derived parameter condition and invalidates the paper's concrete example. The resulting concern is serious but repairable: the quantum algorithm may still work if α is chosen sufficiently close to 1, and the overall framework remains plausible. Therefore the reader's CONDITIONAL verdict is appropriate; I would not escalate to REJECT because the gap is quantitative (a parameter range) rather than a fundamental obstruction. The test I propose would settle whether the corrected range still admits the theorem's parameters or whether the paper needs a revised statement.","tokens_in":41859,"tokens_out":16417,"duration_ms":163530,"concrete_test":"Independently re-derive the union bound in Lemma 4.8 with the per-vector probability set to 2^{-c_min |\\bar{S*}| n}, using |\\bar{S*}| ≥ (1/2-ε)m. Verify that the resulting condition on α is α > 1 - c_min/4 + ε(1 + c_min/2), and check whether Theorem 4.3's range α > 7/8 + 3ε/4 and the example ε=1/12, α=31/32 still satisfy it. If they do not, the decoding lemma fails for those parameters as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Lemma 4.8, the central decoding bound, conditions on the zero set S* and then bounds the probability of the bad event E_{S*} by counting vectors in the complement \\bar{S*}. Two concrete problems appear. First, the text writes e_{S*} in Eq. (8) and (11) where it must mean e_{\\bar{S*}} (on S* the error is zero by definition, so the Hamming condition only makes sense on the complement). Second, and more damaging, Eq. (11) bounds the probability of each vector e_{\\bar{S*}} by 2^{-c_min(1/2+ε)mn}. Since e ∈ T only gives |\\bar{S*}| ≥ (1/2-ε)m, the largest possible per-vector probability is 2^{-c_min(1/2-ε)mn}, which is larger by a factor 2^{2c_min ε mn}. Using the corrected value, the union bound over S* and over the 2^{(1-α)mn} codewords y* yields the condition α > 1 - c_min/4 + ε(1 + c_min/2) (for c_min=1/2, α > 7/8 + 5ε/4), not the stated α > 7/8 + 3ε/4. The paper's parameter θ=1/12, α=31/32 gives 7/8+3ε/4 ≈ 0.9375 < 31/32, but 7/8+5ε/4 ≈ 0.9792 > 31/32, so the concrete example falls outside the corrected range. Thus, as written, Lemma 4.8 does not establish that decoding succeeds with overwhelming probability for the claimed parameters, and the proof of Theorem 4.3 inherits this gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a non-interactive, verifiable quantum-advantage candidate based on solving random underdetermined polynomial systems over F2. The system consists of m=n^2 degree-d polynomials on disjoint blocks of n variables, together with linear constraints coming from the dual of a Reed-Solomon code of rate 1-alpha. The authors adapt the Yamakawa-Zhandry/Regev quantum framework: they prepare superpositions over codewords and over roots of the polynomials, pass through QFT, apply average-case list decoding, and uncompute. Their main technical contribution is a Fourier-spectrum bound for the error distribution induced by any shift-invariant and 2-wise independent polynomial distribution, from which they derive an average-case unique-decoding lemma for Reed-Solomon codes. Classical hardness is conjectured for d>=3 and is supported by a review of specialization, combinatorial, and Groebner-basis attacks, plus experiments for cubic systems.","tokens_in":42324,"tokens_out":19821,"duration_ms":217980,"significance":"If the correctness proof is repaired, this is a substantial contribution. It gives a concrete non-oracle, structured NP-search problem with a provable polynomial-time quantum algorithm and a credible, though explicitly conjectural, classical-hardness story. The Fourier-analysis technique for random polynomial distributions may be reusable for other algebraic instantiations of the Yamakawa-Zhandry framework. The paper is careful to separate the unconditional quantum-easiness theorem from the conjectured classical hardness, and I see no circularity in the derivation: the error distribution is derived from the polynomial distribution and the decoding condition is then verified against that derived distribution. The main obstacle to the current version is a load-bearing gap in the average-case decoding lemma, not a fatal conceptual flaw.","major_comments":[{"comment":"The proof of Lemma 4.8 conditions on S_e = S^*; on S^* the error vanishes, and the necessary event derived from Eqs. (6)-(7) constrains e_{\\bar S^*} - y^*_{\\bar S^*}. However, Eq. (8) and the subsequent counting are written with e_{S^*} - y^*_{S^*}. With the overbars dropped, the displayed event is not the one being counted. The paragraph should consistently use \\bar S^* throughout.","section":"Section 4.4.1, Eq. (8)"},{"comment":"The per-vector probability bound in Eq. (11) is wrong by an exponential factor. Since e in T and S_e = S^* only give |\\bar S^*| >= (1/2 - epsilon)m, the maximum probability of a fixed e_{\\bar S^*} is 2^{-c_min(1/2 - epsilon)mn}, not the smaller 2^{-c_min(1/2 + epsilon)mn}. Recomputing the union bound gives alpha > 1 - c_min/4 + epsilon(1 + c_min/2); for c_min = 1/2 this is alpha > 7/8 + 5*epsilon/4. The example epsilon = 1/12, alpha = 31/32 in Section 3 violates this, so Lemma 4.8 does not prove decoding success for the stated parameters and Theorem 4.3 inherits the gap.","section":"Section 4.4.1, Eq. (11)"},{"comment":"Lemma 4.8 assumes only m = omega(1), but the proof's union bound leaves an additive O(m log m) in the exponent. For the final probability to be 2^{-Omega(mn)}, one needs log m = o(n); m = omega(1) allows m = 2^n, where O(m log m) = Theta(mn) and the conclusion does not follow. The theorem's m = omega(log n) is likewise insufficient in principle. The concrete setting m = n^2 satisfies the needed condition, so this is repairable by stating m = 2^{o(n)} or m = n^{O(1)}.","section":"Section 4.4.1, Lemma 4.8 statement"}],"minor_comments":[{"comment":"The displayed inequality m - sqrt((1-alpha)m^2) > (1/2 + epsilon)m is said to hold when alpha > 3/4 - epsilon + epsilon^2. The correct algebra is alpha > 3/4 + epsilon - epsilon^2. The later condition alpha >= 3/4 + 3*epsilon/2 appears to cover the corrected range for the paper's epsilon, so this seems to be a typo, but it should be fixed.","section":"Section 4.4.1, list-decoding radius paragraph"},{"comment":"The set S^* and its complement are both typeset as S^* in several places, notably Eqs. (6)-(11). The missing overline is a substantial readability problem and contributed to the index error described above.","section":"Section 4.4.1, notation"},{"comment":"For polynomials with no roots, the state-preparation loop in Step 1 has success probability zero and would never terminate. Since such polynomials occur with negligible probability under the stated distributions, the algorithm should explicitly abort after polynomially many attempts, or otherwise truncate, so that the expected-time claim is well defined.","section":"Section 4, Remark 4.4"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about Lemma 4.8 is real and material. The main algorithm and the Fourier-analysis part appear sound in outline, and the error is localized to the decoding lemma's union bound. A revised parameter range (alpha > 7/8 + 5*epsilon/4 for the c_min = 1/2 case) and a corrected example should be enough. I therefore recommend major revision, not rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a serious referee, but not as-is. The genuinely new thing is the Fourier-spectrum analysis of root indicators for shift-invariant 2-wise independent polynomial distributions, and the concrete degree-3 instantiation of the Regev/Yamakawa-Zhandry framework to a system of multivariate equations over F2 with Reed-Solomon constraints. That is a substantial step: it gives a clean candidate non-relativized average-case NP-search advantage without periodicity, conditional on the stated classical-hardness conjecture. The authors are honest that the advantage depends on that conjecture, and Section 5's analysis of classical solvers is a reasonable first pass, even if it cannot be conclusive.\n\nThe quantum algorithm proof is long but structurally sound, and Lemma 4.10's bound on the Fourier mass at nonzero points is plausible and, as far as I can tell, correctly uses 2-wise independence and shift invariance. The problem is Lemma 4.8, which is load-bearing for the whole correctness proof. As the reader notes, the proof conditions on the zero-coordinate set S* and then counts vectors indexed by the complement while writing e_{S*}. That looks like a typo-level inconsistency; the union bound issue is worse. Eq. (11) assigns each bad error a per-vector probability 2^{-c_min(1/2+epsilon)mn}, while the typical zero-set size only guarantees the larger 2^{-c_min(1/2-epsilon)mn}. The corrected union bound moves the alpha threshold to 7/8 + 5epsilon/4 (for c_min = 1/2), and the paper's concrete example alpha=31/32, epsilon=1/12 falls outside that range. I checked the endpoint arithmetic and the stress-test note holds up.\n\nI don't think this kills the approach. The framework is YZ's, which is known to work, and the error distribution from Lemma 4.9 is close to YZ's product distribution, so the lemma is probably repairable with a modest slack adjustment or a different parameter pair. But as written, Lemma 4.8 does not establish the stated decoding success, and Theorem 4.3 inherits the gap.\n\nThe paper is for quantum complexity and multivariate-cryptography researchers. The central idea is new and important enough to deserve referee time, and the gap is local rather than a sign that the approach is misconceived. I would not rely on the current version, and I wouldn't cite it for a correctness claim until the decoding lemma is fixed.\n\nRecommendation: send it to peer review, but expect heavy revision on the decoding lemma.","headline":"A real step forward in instantiating Regev/YZ for multivariate polynomials, but the load-bearing decoding lemma has a set-index and union-bound problem that, as written, breaks the stated parameter range.","tokens_in":42746,"tokens_out":2159,"would_cite":false,"duration_ms":27689,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-08-04T22:32:22.171898+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":null,"supporting_citations":[],"review_version":1}