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:

\begin{equation} 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}}}}, \end{equation} 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.

  • $\begingroup$ 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. $\endgroup$ Jan 21, 2022 at 13:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.