The quantum GapSVP hardness conjecture
Let be a lattice of dimension , and let denote the -norm of its shortest nonzero vector. In the promise problem , given a lattice and , one must distinguish from .
Quantum GapSVP hardness conjecture. There is no polynomial-time quantum algorithm that solves 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.
References
- Shuchen Li, Ilias Zadik and Manolis Zampetakis, “On the Hardness of Learning One Hidden Layer Neural Networks”, arXiv:2410.03477 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.