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

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