Metraipolis › archive › dc_9bb696164f68

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE — arXiv:2609.40321

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.40321
License (as archived)
CC0-1.0
Archived
2026-10-07T13:43:36.799Z
SHA-256 of the archived text
903144cb596adcb0665eb7db15df073fb7c96608d80ec5c6e2f509fcad839f8f
Stable URL of this page
https://metraipolis.com/documento/dc_9bb696164f68

How to cite

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE — arXiv:2609.40321 — arXiv (en), https://arxiv.org/abs/2609.40321 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9bb696164f68 (Metraipolis archive dc_9bb696164f68, sha256 903144cb596adcb0665eb7db15df073fb7c96608d80ec5c6e2f509fcad839f8f)
BibTeX
@misc{dc9bb696164f68,
  title = {Exponential quantum speedup for $mathbbF_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE — arXiv:2609.40321},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40321},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9bb696164f68; sha256 903144cb596adcb0665eb7db15df073fb7c96608d80ec5c6e2f509fcad839f8f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40321. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\epsilon>0$, our quantum algorithm solves $\mathbb{F}_3$-subset sum in polynomial time with $m=\epsilon\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).

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-10-01 in cs.CR).
Categorie arXiv: Quantum Physics (quant-ph) ; Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.40321 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T13:16:25.287Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).