Exponential quantum speedup for F 3 n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
quant-ph, cs.CR, cs.DS
Submitted: 2026-09-30
Updated: 2026-09-30
Terminology
Sources
- Thresholds for families of multisets, with an application to graph pebbling
- TCitH- and VOLEitH-based Signatures from Restricted Decoding
- The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction
- Strength is bounded linearly by Birch rank
- Generic Decoding of Restricted Errors
- Classical and Quantum algorithms for generic Syndrome Decoding problems and applications to the Lee metric
- Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering
- The Quantum Decoding Problem
- Quantum advantage from soft decoders
- Quantum Reduction of Finding Short Code Vectors to the Decoding Problem
- Hidden Translation and Translating Coset in Quantum Computing
- Zero sum subsequences and hidden subgroups
- On learning linear functions from subset and its applications in quantum computing
- On solving systems of diagonal polynomial equations over finite fields
- An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
- On solving systems of random linear disequations
- An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
- No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore
- An upper bound for the solving degree in terms of the degree of regularity
- AI co-mathematician: Accelerating mathematicians with agentic AI
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity