Learning With Errors: a polynomial-time quantum algorithm at polynomial modulus-to-noise ratio?

No efficient quantum algorithm is known. The best attacks, classical and quantum, are lattice-reduction algorithms with exponential cost; for heuristic sieving the running time is about $2^{0.292n}$ classically (Becker, Ducas, Gama and Laarhoven, 2016) and about $2^{0.257n}$ quantumly (Chailloux and Loyer, 2021, improving Laarhoven's $2^{}$), so known quantum speedups only shrink the constant in the exponent. Concrete parameters of ML-KEM (FIPS 203) and ML-DSA (FIPS 204), published 13 August 2024, are set from these costs. The FIPS 203 page carries a November 2025 note about potential errata; no cryptanalytic break of the standardised parameter sets has been reported.

A polynomial-time quantum algorithm for LWE at standard parameters would break ML-KEM, ML-DSA, most lattice-based fully homomorphic encryption and many protocols built on them, forcing another migration of public-key cryptography to a non-lattice basis such as code-based HQC (selected by NIST in March 2025) or hash-based signatures. A proof, or strong new evidence, of quantum hardness would justify continued deployment at the current parameters and smaller margins. Partial progress, such as algorithms that work only for unusual parameter regimes (very small modulus, special noise distributions), directly tells designers which regimes to avoid.

Either (a) a quantum algorithm with a complete proof or heuristic analysis that is verified by independent experts and, ideally, run on small instances, solving LWE (or DCP together with an accepted reduction) for the parameters above; or (b) a convincing hardness result. Unconditional hardness is out of reach (it would prove $\mathsf{NP}\not\subseteq\mathsf{BQP}$, and in particular $\mathsf P\ne\mathsf{NP}$), so in practice (b) means a reduction from a well-studied problem or a proved limitation on large algorithm families, such as the Gupte–Ragavan–Zhandry no-go note for Regev-template DCP algorithms. Expert acceptance of a claim requires scrutiny of the full proof; a preprint alone, as the 2024 episode showed, is not enough.