Paper 2024/555 Quantum Algorithms for Lattice Problems , Tsinghua University, Shanghai Artificial Intelligence Laboratory, Shanghai Qi Zhi Institute Abstract We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the ...