Quantum complexity of specified lattice regimes
Determine the quantum running-time frontier for search and decision LWE with explicitly specified dimension , modulus , error distribution and sample access, and for SVP/CVP with stated approximation factor. A focal LWE regime has polynomial modulus and
Problem statement
Determine the quantum running-time frontier for search and decision LWE with explicitly specified dimension , modulus , error distribution and sample access, and for SVP/CVP with stated approximation factor. A focal LWE regime has polynomial modulus and inverse-polynomial relative Gaussian error; hardness must be assessed for each concrete parameter family.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
LWE samples have the form ; decision distinguishes these from uniform, while search recovers the secret. The noise width, modulus, number of samples and algebraic structure are part of the problem. Plain LWE, module/ring variants, and worst-case approximate lattice problems should not be treated as interchangeable.
What is known: Regev's reduction relates suitable LWE regimes to worst-case approximate lattice problems using quantum computation. It is a conditional hardness reduction, not a quantum algorithm breaking LWE. Known quantum techniques can improve exponential running-time constants, so “no quantum improvement” would be too strong; such improvements are different from a polynomial-time algorithm.
Chen's 2024 claimed polynomial-time quantum LWE algorithm developed an acknowledged error and is not an established attack. Security conclusions require the exact parameter family and reduction; this catalogue does not infer the safety or failure of deployed cryptographic schemes from the unresolved broad programme. Related: A2, A14.
Progress & source assessment
Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.