Paper 2024/583

A Note on Quantum Algorithms for Lattice Problems

Abstract

Recently, a paper by Chen (eprint 2024/555) has claimed to construct a quantum polynomial-time algorithm that solves the Learning With Errors Problem (Regev, JACM 2009), for a range of parameters. As a byproduct of Chen's result, it follows that Chen's algorithm solves the Gap Shortest Vector Problem, for gap $g(n) = \tilde{O}\left( n^{4.5} \right)$. In this short note we point to an error in the claims of Chen's paper.