Short answer: In April 2024 a preprint claimed a polynomial-time quantum algorithm for the Learning With Errors (LWE) problem, which would have been a major result for lattice cryptography. Within days the author reported a bug he did not know how to fix, and a separate note pointed to an error in the claims. As of that correction the preprint does not provide a polynomial-time algorithm for LWE. Separate research on quantum attacks on lattice problems finds the gains over classical methods are modest. This post records both, and it matters because the claim is still easy to find.
The April 2024 claim
A preprint by Yilei Chen, ePrint 2024/555, claimed a polynomial-time quantum algorithm for LWE with certain polynomial modulus-noise ratios. Combined with Regev's 2009 reductions, the abstract said this gave polynomial-time quantum algorithms for the decisional shortest vector problem and the shortest independent vector problem within approximation factors of about n to the power 4.5, where earlier work knew of no polynomial or even subexponential time quantum algorithm for any polynomial factor. The abstract described two new techniques: Gaussian functions with complex variances in quantum algorithm design, and a windowed quantum Fourier transform with complex Gaussian windows.
What happened next
A short note, ePrint 2024/583, says it points to an error in the claims of the Chen paper. A blog post by cryptographer Matthew Green, written when the preprint appeared, carries an update dated April 19, 2024: Chen announced the discovery of a bug in the algorithm which he does not know how to fix, found independently by Hongxun Wu and Thomas Vidick. The update states that at present the paper does not provide a polynomial-time algorithm for solving LWE. The blog post had also noted that even if correct, the vulnerable parameters were very specific and the concrete complexity unclear.
What the quantum cryptanalysis record shows otherwise
A separate paper, arXiv 2205.13983, presents a quantum-augmented variant of the dual lattice attack on LWE, built on classical techniques. Applied to lattice parameters from the literature, the authors find it outperforms previous algorithms, under the assumption of unit-cost access to quantum random access memory. The paper also describes the general picture: known quantum speedups for lattice problems are tenuous at best, and while Grover's search gives a near-quadratic speedup against, for example, AES, the gains against lattice problems are significantly more modest because of the structure of the search space in lattice reduction. It adds that, as a consequence, the state of the art at the time was that quantum algorithms on lattice problems could effectively be ignored when setting parameters.
What this does not tell you
The unit-cost QRACM assumption is a strong one, and the comparison is relative to earlier algorithms in that model. A retracted claim does not prove that no quantum attack on LWE exists, and an older statement that quantum gains are modest can change with new results.
FAQ
Is there a polynomial-time quantum algorithm for LWE?
Not from the 2024 preprint. Its author reported a bug he could not fix.
Who found the bug?
Chen announced it, and Hongxun Wu and Thomas Vidick found it independently, according to a blog update dated April 19, 2024.
How much do quantum computers help against lattice problems?
The 2022 paper describes the gains as modest compared with the Grover speedup against AES.
Does it mean lattice cryptography is proven secure?
No. These are cryptanalysis results and corrections, not proofs of security.
Why keep a post on a withdrawn claim?
Because the original preprint remains online and is still cited.
All field notes