ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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

Quantum GapSVP hardness conjecture. There is no polynomial-time quantum algorithm that solves GapSVP\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.