Polynomial-time quantum algorithm for approximate Shortest Vector Problem

Problem

Does the polynomial-factor approximate Shortest Vector Problem admit a polynomial-time quantum algorithm?

Let \(B\in\mathbb Q^{n\times n}\) be a nonsingular lattice basis whose entries have polynomially bounded bit length, and let

\begin{equation} \mathcal L(B)=\{Bz:z\in\mathbb Z^n\}\subset\mathbb R^n . \tag{1} \end{equation}

Define the length of a shortest nonzero lattice vector by

\begin{equation} \lambda_1(\mathcal L)=\min_{v\in\mathcal L\setminus\{0\}}|v|_2 . \tag{2} \end{equation}

For an approximation factor \(\gamma=\gamma(n)\geq 1\), the \(\gamma\)-approximate Shortest Vector Problem asks for a nonzero vector \(v\in\mathcal L(B)\) satisfying

\begin{equation} |v|_2\leq\gamma(n)\lambda_1(\mathcal L(B)). \tag{3} \end{equation}

The open question is whether, for polynomial approximation factors such as \(\gamma(n)=n^c\) for a fixed constant \(c>0\), there exists a bounded-error quantum algorithm that outputs a vector satisfying (3) in time polynomial in the bit length of \(B\).

Source

Contributor: unknown. The opening question is a contributor-formulated synthesis of a standard open algorithmic problem in the lattice and quantum-algorithms literature. Biasse, Bonnetain, Kirshanova, Schrottenloher, and Song explicitly identify polynomial-factor approximate SVP as a principal regime of interest and survey the known quantum algorithms [Bia23], but do not state the opening sentence verbatim as a named open question. It should not be attributed verbatim to any of the cited authors.

Progress

Classical polynomial-time lattice reduction does not reach the polynomial-factor regime in general: the LLL algorithm gives only an approximation factor exponential in \(n\) for arbitrary lattices, so a polynomial approximation factor in polynomial time would be a qualitatively stronger result rather than an improvement of the approximation constant in LLL [LLL82].
Known algorithms obtain substantially better approximation factors by spending exponential time: Aggarwal, Li, and Stephens-Davidowitz gave a \(2^{n/2+o(n)}\)-time algorithm achieving an approximation factor \(\widetilde O(\sqrt{n})\) for both SVP and Hermite SVP (the tilde suppresses polylogarithmic factors), together with broader time–approximation tradeoffs. Polynomial approximation factors are therefore accessible significantly faster than exact SVP in some regimes, but not in polynomial time [ALS21].
Quantum computation provides speedups for exponential-time SVP approaches but no known technique reaches polynomial time: quantum lattice-sieving algorithms use amplitude amplification and quantum walks to reduce the exponential constant, and Bonnetain, Chailloux, Schrottenloher, and Shen obtained heuristic quantum sieving complexity \(2^{0.2563n+o(n)}\) for SVP [BCSS23].
There are also provable quantum algorithms outside the heuristic-sieving framework: Aggarwal, Chen, Kumar, and Shen gave a provable quantum algorithm for exact SVP running in \(2^{0.950n+o(n)}\) time with exponential classical memory and polynomially many qubits, and in the QRAM model in \(2^{0.835n+o(n)}\) time; since an exact-SVP solver also solves the approximate problem, these are quantum upper bounds for approximate SVP but remain exponential [ACKS25].
The problem is distinct from the unique Shortest Vector Problem: Regev showed that an efficient solution to the relevant dihedral coset problem — in particular an appropriate coset-sampling solution of the Dihedral Hidden Subgroup Problem — would yield a polynomial-time quantum algorithm for polynomial-factor unique-SVP. The uniqueness promise is absent in the arbitrary-lattice problem here, so the DHSP–lattice reduction does not give a polynomial-time algorithm for general approximate SVP [Reg04].
Approximate SVP is likewise distinct from GapSVP and SIVP: Regev’s worst-case-to-average-case reduction for Learning With Errors is a quantum hardness reduction from worst-case approximate GapSVP and SIVP to LWE, not an algorithm for the search problem here. The LWE, DHSP, and approximate-SVP questions are closely related but remain logically distinct open problems [Reg09].
A survey of quantum cryptanalysis by Biasse, Bonnetain, Kirshanova, Schrottenloher, and Song treats polynomial-factor approximate SVP as the principal approximation regime relevant to lattice-based cryptographic constructions and surveys the known quantum enumeration, sieving, and BDD-based approaches; these methods provide at most exponential-time speedups in the general setting [Bia23].

Comment

The open question is whether any quantum algorithm breaks the polynomial-time barrier for polynomial approximation factors. Known quantum algorithms for SVP and its variants remain exponential in the lattice dimension, and the LWE and DHSP reductions provide hardness reductions or require structural promises (uniqueness of the shortest vector) absent here. The related LWE and Dihedral Hidden Subgroup Problem records are given related problem links (Progress above).

References

[LLL82]: Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász, “Factoring Polynomials with Rational Coefficients,” Mathematische Annalen 261, 515–534 (1982).DOI
[Reg04]: Oded Regev, “Quantum Computation and Lattice Problems,” SIAM Journal on Computing 33, 738–760 (2004).DOI arXiv
[Reg09]: Oded Regev, “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography,” Journal of the ACM 56, Article 34 (2009).DOI
[ALS21]: Divesh Aggarwal, Zeyong Li, and Noah Stephens-Davidowitz, “A \(2^{n/2}\)-Time Algorithm for \(\sqrt{n}\)-SVP and \(\sqrt{n}\)-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP,” in Advances in Cryptology – EUROCRYPT 2021, Part I, 467–497 (2021).DOI arXiv
[BCSS23]: Xavier Bonnetain, André Chailloux, André Schrottenloher, and Yixin Shen, “Finding Many Collisions via Reusable Quantum Walks – Application to Lattice Sieving,” in Advances in Cryptology – EUROCRYPT 2023, Part V, 221–251 (2023).DOI arXiv
[ACKS25]: Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen, “Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding,” SIAM Journal on Computing 54, 233–278 (2025).DOI arXiv
[Bia23]: Jean-François Biasse, Xavier Bonnetain, Elena Kirshanova, André Schrottenloher, and Fang Song, “Quantum Algorithms for Attacking Hardness Assumptions in Classical and Post-Quantum Cryptography,” IET Information Security 17, 171–209 (2023).DOI

Polynomial-time quantum algorithm for approximate Shortest Vector Problem

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems