arXiv:2609.40321
Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
Robin Kothari, Tony Metger, Ryan O'Donnell, Noah Shutty, Kewen Wu
Abstract
We study vector subset sum over $\mathbb{F}_3^n$: given $m$ random vectors from $\mathbb{F}_3^n$, find a nonempty subset that sums to zero; the smaller $m$, the more difficult it is to find such a subset. Chen, Liu, and Zhandry (EUROCRYPT'22) introduced an efficient quantum algorithm that solves this problem when $m\approx n^2/2$, where a naive classical algorithm would require exponential time. Subsequently, Kothari, O'Donnell, and Wu (STOC'2026) gave an efficient classical algorithm that only requires $m \approx n^2/3$ vectors, thus removing the hope for an exponential quantum advantage in this parameter regime. Using the framework of Chen, Liu, and Zhandry, we give quantum algorithms that require much fewer input vectors, renewing the possibility of an exponential quantum speedup: for any fixed $ε>0$, our quantum algorithm solves $\mathbb{F}_3$-subset sum in polynomial time with $m=ε\cdot n^2$ vectors. More generally, we establish a full sample--time tradeoff that interpolates between exponential and polynomial runtime. The main ingredient is a deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest. For this, we rigorously establish a sample--time tradeoff that was predicted by earlier algebraic heuristics. For vector subset sums over larger fields, we also significantly improve classical algorithms in Kothari, O'Donnell, and Wu (STOC'2026).
AI Summary
The paper studies average-case vector subset sum over $\mathbb F_3^n$: given $m$ random vectors, find a nonempty subset summing to zero. It asks whether this explicit-input search problem supports an exponential quantum advantage after classical algorithms reached the previously proposed quantum regime, $m\approx n^2/3$. Its main quantum result gives runtime $(m/n)^{O_\kappa(\lceil n^2/m\rceil)}$ and failure probability $2^{-\Omega_\kappa(m)}$ for every $m\ge\kappa n$, with fixed $\kappa>\log_2 3$. Consequently, polynomial time suffices for $m=\epsilon n^2$ for every fixed $\epsilon>0$; intermediate sample counts yield quasipolynomial and subexponential runtimes. The new ingredient is a deterministic classical binary-error LWE decoder over any fixed prime field $\mathbb F_q$, $q\ge3$, with the same tradeoff above the uniqueness threshold $m>\log_{q/2}(q)n$. Recovery holds for each fixed secret and binary error vector, with probability over the random matrix. The analysis encodes decoding as quadratic equations with field equations, proves degree-$D$ surjectivity for $D=O(n^2/m)$ using symbolic-rank bounds, algebraic shifting, multiset shadows and martingale concentration, then computes the quotient algebra by linear algebra. An existing coherent quantum reduction transfers this decoder to subset sum. Additional classical results reduce larger-field average-case sample requirements to $O_q(n^{1+\lfloor(q+3)/4\rfloor})$ and worst-case requirements to $O_q(n^{q-1})$. No classical lower bound establishes an exponential separation. A claimed classical $\mathbb F_3$ threshold of approximately $0.1022n^2$, obtained through LLM-assisted gadget optimization, is stated without a complete algorithm or proof; practical cryptographic attacks are not established.
We note that this value of $\eps$ is the result of an LLM-assisted optimization of existing classical algorithmic ideas.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.