Recently CHEN Yilei, an assistant professor of the Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University, posted on eprint an important paper titled “Quantum Algorithms for Lattice Problems”. Link: https://eprint.iacr.org/2024/555

The “Approximate Shortest Vector in Lattices” problem (abbr. Lattice problems）and the related “Learning with Errors” (LWE）problem are well-known to be hard to solve, and generally regarded as beyond the computational power of classical computers. This begs the question: “Will quantum computers be able to solve these problems efficiently?” The question has garnered wide interest, without seeing much progress toward a resolution so far. The work of CHEN Yilei proposes a brand-new quantum algorithm for solving LWE and the related Lattice problems. The work is currently under peer review.  If proven correct, it presents an affirmative answer to the above open problem. The scientific significance of this work is two-fold: 1) This could be seen as the greatest breakthrough in quantum algorithms since Peter Shor’s celebrated algorithm for factoring large numbers 30 years ago. 2) The finding may have a disruptive effect on NIST’s efforts over the last decade in designing crypto standards for post-quantum systems, since most selected standards are based on Lattice problems or LWE. The current work would likely cast doubt on their security.

The algorithms and analysis presented in this paper are both novel and deep. Recalling that Andrew Wiles’s 1994 paper on Fermat's Last Theorem and Perelman’s 2002 paper on the Poincaré Conjecture each took a year or more before receiving confirmation, we expect the present paper may also take a few months for the experts to thoroughly check its correctness. Let us await feedback from the scientific community.  Andrew C. Yao, Dean of IIIS remarks: “As a young faculty member, Yilei’s fearless undertaking of a world-class hard scientific problem is to be praised and admired!”