Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
Quantum algorithms solve ternary vector subset-sum with fewer samples, backed by rigorous classical binary-error LWE methods.
The paper gives quantum algorithms for vector subset-sum over F_3^n that, for any fixed ε>0, run in polynomial time using m=ε·n² random vectors, reopening a possible exponential quantum advantage below earlier thresholds. The main tool is a deterministic classical algorithm for binary-error Learning with Errors, with a sample-time tradeoff that earlier algebraic heuristics only predicted. The authors also improve the classical subset-sum algorithms of Kothari, O'Donnell, and Wu for larger fields.
- Quantum polynomial time for any fixed ε with m=ε·n² vectors
- Prior classical algorithm needed about n²/3 vectors
- Rigorous sample-time tradeoff for binary-error LWE
- Classical subset-sum algorithms improved for larger fields
Full article202 words · extracted from arxiv.org · click to collapse
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).
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.40321