Yilei Chen from Tsinghua University presents a groundbreaking quantum algorithm for solving the learning with errors problem (LWE) by introducing new techniques involving complex Gaussian functions and quantum Fourier transforms. By leveraging these methods, the algorithm achieves polynomial time solutions for lattice problems, such as the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP). This innovative approach fills a gap in the field as no previous quantum algorithms had been able to efficiently solve these problems for all lattices within specific approximation factors. The paper provides a significant contribution to the advancement of quantum algorithms for lattice problems.
https://eprint.iacr.org/2024/555