Polynomial-time quantum algorithm for Learning With Errors

Problem

Does the Learning With Errors problem in its standard worst-case-hard parameter regime admit a polynomial-time quantum algorithm?

Let \(n\) be the dimension, let \(q=q(n)\geq 2\) be an integer modulus, and let \(\alpha=\alpha(n)\in(0,1)\) be a noise rate. A search-LWE instance is generated by choosing a secret \(s\in\mathbb Z_q^n\) uniformly at random and providing polynomially many independent samples

\begin{equation} (a_i,b_i)\in\mathbb Z_q^n\times\mathbb Z_q, \qquad b_i=\langle a_i,s\rangle+e_i\pmod q, \tag{1} \end{equation}

where each \(a_i\) is uniform in \(\mathbb Z_q^n\), and each error \(e_i\) is sampled independently from a discrete Gaussian of width \(\alpha q\). For \(x\in\mathbb Z\),

\begin{equation} \Pr[e_i=x]=\frac{\exp\left(-\pi x^2/(\alpha q)^2\right)} {\sum_{z\in\mathbb Z}\exp\left(-\pi z^2/(\alpha q)^2\right)} . \tag{2} \end{equation}

The task is to recover the secret \(s\) from samples satisfying (1). The open question is whether, for standard parameter families for which LWE has worst-case lattice-hardness guarantees, there exists a bounded-error quantum algorithm whose running time is polynomial in \(n\) and \(\log q\).

Source

Contributor: unknown. The statement is a contributor-formulated open question synthesizing the quantum-complexity question studied throughout the LWE literature; it should not be attributed verbatim to Regev, Chen, or any of the other cited authors.

Progress

Reports do not certify correctness or automatically change the problem's status. Progress policy.

Regev introduced LWE and established its central worst-case hardness connection: in appropriate parameter regimes, an efficient algorithm for LWE can be converted, via a quantum reduction, into an efficient quantum algorithm for approximating worst-case GapSVP and SIVP within polynomial approximation factors. The reduction is a worst-case-to-average-case hardness reduction using quantum computation, not a quantum algorithm for solving LWE [Reg09].
Brakerski, Kirshanova, Stehlé, and Wen introduced the Extrapolated Dihedral Coset Problem (EDCP) and established quantum polynomial-time reductions relating LWE to suitable EDCP variants; a polynomial-time quantum algorithm for EDCP in the arising parameter regime would yield a polynomial-time quantum algorithm for LWE [BKSW18].
Chen, Liu, and Zhandry gave polynomial-time quantum algorithms for variants of average-case lattice problems, including LWE-like inputs in which the algorithm receives quantum states rather than ordinary classical LWE samples; the parameter regimes and input models considered are not known to inherit the standard worst-case hardness guarantees [CLZ22].
Chen proposed a polynomial-time quantum algorithm for LWE with certain polynomial modulus-to-noise ratios, based on complex Gaussian states and windowed quantum Fourier transforms; the claim was subsequently withdrawn after a bug in Step 9 of the algorithm was identified [Che24].
Chen, Hu, Liu, Luo, and Tu studied LWE variants with quantum amplitudes, giving a subexponential-time algorithm for certain Gaussian-amplitude LWE states with known phase and polynomial-time algorithms for quadratic-phase variants, together with polynomial-time quantum reductions from standard LWE and worst-case GapSVP to Gaussian-amplitude LWE states carrying a small unknown phase; the unknown phase is identified as the principal obstruction to converting these into an efficient algorithm for standard LWE [CHLLT25].
Bai, Jangir, Kirshanova, Ngo, and Youmans gave a quasi-polynomial-time quantum algorithm for EDCP over power-of-two moduli, using a quasi-polynomial number of EDCP states; known reductions from standard LWE provide only polynomially many relevant states, so this does not currently imply a quasi-polynomial-time algorithm for standard LWE [BJKNY25].

Comment

Several concrete routes remain open: solving the relevant EDCP instances with only polynomially many quantum states; overcoming the unknown-phase obstruction in quantum-amplitude formulations of LWE; repairing or replacing the complex-Gaussian and windowed-QFT approach; or finding a fundamentally different quantum algorithm operating directly on ordinary classical LWE samples.

References

[Reg09]: Oded Regev, “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography,” Journal of the ACM 56, Article 34 (2009).DOI
[BKSW18]: Zvika Brakerski, Elena Kirshanova, Damien Stehlé, and Weiqiang Wen, “Learning With Errors and Extrapolated Dihedral Cosets,” in Public-Key Cryptography – PKC 2018, 702–727 (2018).DOI arXiv
[CLZ22]: Yilei Chen, Qipeng Liu, and Mark Zhandry, “Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering,” in Advances in Cryptology – EUROCRYPT 2022, 372–401 (2022).DOI arXiv
[Che24]: Yilei Chen, “Quantum Algorithms for Lattice Problems,” IACR Cryptology ePrint Archive, Paper 2024/555 (2024). ePrint 2024/555.link
[CHLLT25]: Yilei Chen, Zihan Hu, Qipeng Liu, Han Luo, and Yaxin Tu, “LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling,” in Advances in Cryptology – CRYPTO 2025, 513–544 (2025).DOI arXiv
[BJKNY25]: Shi Bai, Hansraj Jangir, Elena Kirshanova, Tran Ngo, and William Youmans, “A Quasi-polynomial Time Algorithm for the Extrapolated Dihedral Coset Problem over Power-of-Two Moduli,” in Advances in Cryptology – CRYPTO 2025, 416–448 (2025).DOI

Polynomial-time quantum algorithm for Learning With Errors

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems