{"id":"arxiv/2609.40321","url":"https://arxiv.org/abs/2609.40321","tags":["quant-ph","cs.CR","cs.DS"],"score":0,"title":"Exponential quantum speedup for $\\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE","domain":"quant-ph","source":"arxiv","authors":["Robin Kothari","Tony Metger","Ryan O'Donnell","Noah Shutty","Kewen Wu"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}