2 problems

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

Let $\mathrm{SVP}$ denote the Shortest Vector Problem on lattices, and let a polynomial-factor approximation mean an approximation within a factor bounded by a polynomial in the la…