Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. (arXiv:2002.07955v5 [cs.DS] UPDATED)

The most important computational problem on lattices is the Shortest Vector
Problem (SVP). In this paper, we present new algorithms that improve the
state-of-the-art for provable classical/quantum algorithms for SVP. We present
the following results. $\bullet$ A new algorithm for SVP that provides a smooth
tradeoff between time complexity and memory requirement. For any positive
integer $4\leq q\leq \sqrt{n}$, our algorithm takes $q^{13n+o(n)}$ time and
requires $poly(n)\cdot q^{16n/q^2}$ memory. This tradeoff which ranges from
enumeration ($q=\sqrt{n}$) to sieving ($q$ constant), …

algorithms ds problem quantum