Skip to content
DraconiticResearch
Search Sources API
194,161 studies31 sourcesUpdated 56 min ago
PreprintarXiv licencearXiv

Exponential quantum speedup for 𝔽3n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

  • Robin Kothari
  • Tony Metger
  • Ryan O'Donnell
  • Noah Shutty
  • Kewen Wu
Open at sourcePDFDOICite

Abstract

We study vector subset sum over 𝔽3n: given m random vectors from 𝔽3n, 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β‰ˆ n2/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 β‰ˆ n2/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 𝔽3-subset sum in polynomial time with m=Ρ· n2 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).

Related

  1. Exponential speedup of polarization stabilization for long distance DWDM quantum networks
    Jinyi Du, En Teng Lim, Xingjian Zhang +4
    arXivPreprintCC BY-NC-ND 4.0Full textApplied physics & instrumentationOptics & photonicsarXiv
  2. Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders
    Stuart Wayland, Zackary Jorquera, Alexandra Kolla
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
    Gino Kwun, Dhanvi Bharadwaj, Gokul Subramanian Ravi
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  4. Provable Classical and Quantum Local Algorithms for Max-k-Cut and Quantum Advantage at Moderate Girth
    Anuj Apte, Abid Khan, Edward Farhi +3
    arXivPreprintarXiv licenceFull textOptimisation & controlQuantum physics & quantum informationarXiv
  5. Exponential Advantage of Quantum over Classical References in Leakage Detection
    Zheng An
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{kothari2026exponential,
  title = {{Exponential quantum speedup for $\mathbbF_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE}},
  author = {Robin Kothari and Tony Metger and Ryan O'Donnell and Noah Shutty and Kewen Wu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40321},
  eprint = {2609.40321},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40321},
}
RIS
TY  - UNPB
TI  - Exponential quantum speedup for 𝔽_3^n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
AU  - Robin Kothari
AU  - Tony Metger
AU  - Ryan O'Donnell
AU  - Noah Shutty
AU  - Kewen Wu
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40321
UR  - https://arxiv.org/abs/2609.40321
AB  - We study vector subset sum over 𝔽_3^n: given m random vectors from 𝔽_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β‰ˆ 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 β‰ˆ 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 𝔽_3-subset sum in polynomial time with m=Ρ· 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).
ER  -