Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering

Yilei Chen, Qipeng Liu, Mark Zhandry

We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the m…