REVIEW 3 major objections 3 minor 2 cited by
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.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
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.
T0 review reviewed 2026-08-04 challenge →
load-bearing objection 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. the 3 major comments →
Quantum Advantage via Solving Multivariate Polynomials
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 quantum algorithm follows a framework due to Regev and to Yamakawa and Zhandry. It prepares a quantum superposition of all code words, and another superposition of all roots of the polynomial equations. A quantum Fourier transform and a decoding step are used to combine the two superpositions into a state whose measurement gives a vector that is both a code word and a root of every polynomial. The main technical work is showing that the 'error' introduced by the root superpositions looks, after the Fourier transform, like a distribution that a Reed-Solomon decoder can correct in the average case. The key lemma proves that random polynomials of degree at least 2 are 2-wise independent and shift-invariant, which makes the Fourier spectrum of their root indicator nearly flat.
The classical hardness part is not proven. The paper reviews exhaustive search, Grobner bases, and specialization attacks, gives small experiments, and argues that none of these methods runs in polynomial time on this distribution. The authors are explicit that this is a conjecture. So the result is best read as a strong candidate for quantum advantage, conditional on a new classical-hardness assumption.
Core claim
Theorem 4.3: for every constant epsilon in (0,1/6), for alpha with 7/8 + 3epsilon/4 < alpha < 1, and for m = omega(log n), there exists an expected polynomial-time quantum algorithm that inverts the described polynomial system (P,H) with probability 1 - mu(lambda). In particular, the informal main theorem: given H and degree-3 polynomials {p_i}, the algorithm computes y with H.y = 0 and p_i(y_i) = 0 for all i.
Load-bearing premise
Lemma 4.8 is the load-bearing decoding bound. The proof in Section 4.4.1 conditions on the zero-coordinate set S* of the error e, then defines the bad event E_{S*} by a Hamming-weight condition on e_{S*}; but the derivation from Eq. (6)-(7) and the subsequent probability count only make sense for the complement coordinates. The same paragraph states the list-decoding radius requirement as alpha > 3/4 - epsilon + epsilon^2, whereas the correct inequality from m(1 - sqrt(1-alpha)) > (1/2 + epsilon)m is alpha > 3/4 + epsilon - epsilon^2; the later stronger condition alpha > 7/8 + 3epsilon/4 may cover it, but the text as written is internally inconsistent. If the intended counting bound is false, the decoder could fail on a non-negligible fraction of errors. Separately, the claimed quantum advantage depends on the unproven classical-hardness conjecture of Section 5.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 4.4.1, Eq. (8)] 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 4.4.1, Eq. (11)] 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 4.4.1, Lemma 4.8 statement] 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)}.
minor comments (3)
- [Section 4.4.1, list-decoding radius paragraph] 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 4.4.1, notation] 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 4, Remark 4.4] 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.
Circularity Check
No significant circularity: quantum correctness proof derives the error distribution from the polynomial distribution and verifies it against a generic decoding bound; no fitted input or self-referential load-bearing step.
full rationale
The claimed derivation chain is not circular. Algorithm 1's correctness is proved by bounding the bad-error mass E_P[sum_{e in B} |Ŵ_P(e)|^2] and the interference term; the first bound (Lemma 4.5) is obtained by (i) a generic average-case unique-decoding condition (Lemma 4.8) for any product distribution with 1/2 mass at zero and per-point mass at most 2^{-c_min n}, and (ii) a Fourier-spectrum characterization (Lemmas 4.9-4.12) showing that the distribution induced by the polynomial system satisfies that condition. Both components are derived from the paper's stated assumptions (shift-invariance and 2-wise independence) together with external Reed-Solomon list-decoding [GS98] and the Yamakawa-Zhandry framework. No parameter is fitted to the target; the decoding success is not assumed in the error-distribution analysis. The only author self-citations (e.g., [Din21b] in the classical-hardness survey) are not used in the quantum correctness proof and are therefore non-load-bearing. The skeptic's concerns about Lemma 4.8's Hamming-weight endpoint and the alpha range are correctness/parameter-range issues, not circularity: even if the union bound is wrong, that would make the proof gap a false lemma, not a derivation that assumes its conclusion.
Axiom & Free-Parameter Ledger
free parameters (2)
- alpha (code rate parameter) =
e.g., 31/32
- epsilon (decoding radius slack) =
e.g., 1/12
axioms (3)
- domain assumption The polynomial distribution satisfies 2-wise independence and shift-invariance
- standard math Reed-Solomon list decoding corrects up to m - sqrt(km) errors (Guruswami-Sudan)
- domain assumption Classical hardness for degree d >= 3
Cite this review
Pith. "Pith review of Quantum Advantage via Solving Multivariate Polynomials." pith.science (2026). https://pith.science/paper/2VHC6VTI
@misc{pith2026250907276,
author = {Pith},
title = {Pith review of: Quantum Advantage via Solving Multivariate Polynomials},
year = {2026},
howpublished = {\url{https://pith.science/paper/2VHC6VTI}},
note = {Machine review of arXiv:2509.07276}
}
read the original abstract
In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case $\mathsf{NP}$ search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field $\mathbb{F}_2$ drawn from a specified distribution. In particular, for any $d \geq 2$, we design a distribution of degree up to $d$ polynomials $\{p_i(x_1,\ldots,x_n)\}_{i\in [m]}$ for $m<n$ over $\mathbb{F}_2$ for which we show that there is a expected polynomial-time quantum algorithm that provably simultaneously solves $\{p_i(x_1,\ldots,x_n)=y_i\}_{i\in [m]}$ for a random vector $(y_1,\ldots,y_m)$. On the other hand, while solutions exist with high probability, we conjecture that for constant $d > 2$, it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage. Our approach begins with the breakthrough Yamakawa-Zhandry (FOCS 2022) quantum algorithmic framework. In our work, we demonstrate that this quantum algorithmic framework extends to the setting of multivariate polynomial systems. Our key technical contribution is a new analysis on the Fourier spectra of distributions induced by a general family of distributions over $\mathbb{F}_2$ multivariate polynomials -- those that satisfy $2$-wise independence and shift-invariance. This family of distributions includes the distribution of uniform random degree at most $d$ polynomials for any constant $d \geq 2$. Our analysis opens up potentially new directions for quantum cryptanalysis of other multivariate systems.
Figures
Forward citations
Cited by 2 Pith papers
-
Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Extends NP-hardness of exceeding r/q + O(1/sqrt(D)) for bounded-degree max-Ek-LINSAT(q,r) over F_q and shows quantum decoding is required for DQI to achieve the hardness-optimal 1/sqrt(D) scaling.
-
Quantum Decoding Algorithms: Quantum Speedups in Optimization
A review describing the Decoded Quantum Interferometry algorithm for quantum speedups in max-LINSAT optimization, with claimed superpolynomial advantage in the OPI problem.
Reference graph
Works this paper leans on
-
[1]
List-decode the noisy codewordz :=x+eto obtain a listLof candidate codewords inC ⊥. 23
-
[2]
If there is a unique codewordx ′ inLsuch thatz−x ′ looks like a “reasonable” error, i.e. theF 2n- Hamming weight is bounded above by 1 2 +ε m, then outputx ′. Otherwise, if there are multiple such candidates, the algorithm fails and returns⊥. List-decoding, rather than unique decoding, must be performed as the worst caseF 2n-hamming weight is well beyond ...
-
[3]
Ife∈T, then there exists a subset of indicesS ∗ ⊆[m]on whiche i =0∈F 2n such that|S ∗| ≥ 1 2 −ε m
-
[4]
Ife/∈G ′, then there exists a codewordy ∗ ∈C ⊥ \ {0}such thathw2n(e−y ∗)≤ 1 2 +ε m. We can rewrite the latter observation as, hw2n(e−y ∗) =hw 2n(eS∗ −y ∗ S∗) +hw 2n(eS∗ −y ∗ S∗)≤ Å 1 2 +ε ã m.(6) 25 where the subscript with a set denotes a restriction to the indices in the set, i.e.e S∗ =e i1ei2 · · ·ei|S∗| for i1 < i2 <· · ·< i|S∗| ∈S ∗, and where S∗ = [...
-
[5]
Therefore, for any 1> α >max 3 4 + 3 2 ε, 7 8 + 3 4 ε , we can apply Lemma 4.8 to guarantee the existence of this negligible functionµ. We can further simplify the condition onαby observing that whenε≥ 1 6 the first term of the maximum operator implies that we needα≥1implying thatε≥ 1 6 does not result in any feasible values of α. Whenε < 1 6 however, the...
-
[6]
In case solutions exist (which would occur with very high probability in case the Reed-Solomon code is replaced by a random linear code of the same dimension), an arbitrary solution can be found in polynomial time and easily extended to a solution ofF. Generalization to higher-degree polynomials.The above algorithm highly relies on the fact that each equa...
work page internal anchor Pith review Pith/arXiv arXiv 2011
-
[8]
Springer, Heidelberg, Germany. 1 [Laz83] Daniel Lazard. Gr ¨obner bases, gaussian elimination and resolution of systems of algebraic equations. In J. A. van Hulzen, editor,Computer Algebra, pages 146–156, Berlin, Heidelberg,
-
[1983]
33 [LN97] Rudolf Lidl and Harald Niederreiter.Finite fields
Springer Berlin Heidelberg. 33 [LN97] Rudolf Lidl and Harald Niederreiter.Finite fields. Number 20. Cambridge university press,
-
[1995]
Springer, Heidelberg, Germany. 1 [Pat96] Jacques Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms. In Ueli M. Maurer, editor,Advances in Cryptol- ogy – EUROCRYPT’96, volume 1070 ofLecture Notes in Computer Science, pages 33–48, Saragossa, Spain, May 12–16, 1996. Springer, Heidelberg, Ge...
Pith/arXiv arXiv 1996
-
[1997]
Beating Brute Force for Systems of Polynomial Equations over Finite Fields, pages 2190–
8, 34, 37 [LPT+17] Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, Ryan Williams, and Huacheng Yu. Beating Brute Force for Systems of Polynomial Equations over Finite Fields, pages 2190–
-
[1999]
1 [KS99] Aviad Kipnis and Adi Shamir
Springer, Heidelberg, Germany. 1 [KS99] Aviad Kipnis and Adi Shamir. Cryptanalysis of the HFE public key cryptosystem by relin- earization. In Michael J. Wiener, editor,Advances in Cryptology – CRYPTO’99, volume 1666 ofLecture Notes in Computer Science, pages 19–30, Santa Barbara, CA, USA, August 15–19,
-
[2021]
UOV-pepper: New public key short signature in degree 3
1 [MRP21b] Gilles Macario-Rat and Jacques Patarin. UOV-pepper: New public key short signature in degree 3. Cryptology ePrint Archive, Paper 2021/1006, 2021. 1 [ON86] E Okamoto and K Nakamura. Evaluation of public key cryptosystems proposed recently. In Proc, 1986. 1 [OSS84] H. Ong, Claus-Peter Schnorr, and Adi Shamir. Efficient signature schemes based on ...
work page 2021
-
[2202]
2 41 [MI88] Tsutomu Matsumoto and Hideki Imai
2017. 2 41 [MI88] Tsutomu Matsumoto and Hideki Imai. Public quadratic polynominal-tuples for efficient signature-verification and message-encryption. In C. G. G¨unther, editor,Advances in Cryptol- ogy – EUROCRYPT’88, volume 330 ofLecture Notes in Computer Science, pages 419–453, Davos, Switzerland, May 25–27, 1988. Springer, Heidelberg, Germany. 1 [MRP21a...
work page 2017
This paper was first reviewed by deepseek-v4-flash on August 4, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.