# What is the explicit best known quantum algorithm for LWE?

Consider the learning with errors(LWE) problem which is known to be hard for quantum computers.

Let $$q \geq 2$$ be a prime integer. Consider us being given (polynomially many samples of) either:

$$A, As + e~~~(\text{mod}~q),~~\text{or}$$ $$A, u~~~(\text{mod}~q),$$

where we have: \begin{align} s &\in \mathbb{Z}_{q}^{m}, \\ A &\in_{U} \mathbb{Z}_{q}^{n \times m}, \\ u &\in_{U} \mathbb{Z}_{q}^{m}, \end{align}

$$\in_U$$ means "sampled uniformly randomly from the set." $$e$$ is sampled from the distribution:

$$$$D_{\mathbb{Z}_q, B^{'}}(x) = \frac{e^{\frac{- \pi ||x||^{2}}{B^{'2}}}}{\sum_{x \in \mathbb{Z}_q^{n}, ||x|| \leq B'} e^{\frac{- \pi ||x||^{2}}{B^{'2}}}},$$$$ where $$B' = \frac{q}{C_{T} \sqrt{mn \log q}},$$ $$C_{T}$$ is a fixed constant. $$q$$ is polynomial in $$n$$.

What is the explicit best-known quantum algorithm for LWE? I could not find a description of any such algorithm but I found a hypothesis that the best-known quantum algorithm runs in exponential time.

• I might have this wrong but I think that many such lattice problems can be reduced to the dihedral hidden subgroup problem, of which the best known quantum algorithms are indeed exponential. Jan 21, 2022 at 13:55