The quantum GapSVP hardness conjecture

Let $\Lambda$ be a lattice of dimension $d$, and let $\lambda_1(\Lambda)$ denote the $\ell_2$-norm of its shortest nonzero vector. In the promise problem $\mathrm{GapSVP}$, given a lattice $\Lambda$ and $t\in\mathbb{R}$, one must distinguish $\lambda_1(\Lambda)<t$ from $\lambda_1(\Lambda)\geq \alpha(d)t$.

Quantum GapSVP hardness conjecture. There is no polynomial-time quantum algorithm that solves $\mathrm{GapSVP}$ to within polynomial factors.

This conjectured hardness is used as a cryptographic and algorithmic-theory basis for the paper's learning hardness results. The source attributes the conjecture to the belief that no polynomial-factor quantum algorithm for GapSVP exists, while noting that known algorithms such as LLL achieve only an exponential approximation factor.