Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1301.6176 · Lecture notes in computer science

Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

Published Jan 1, 2013• 28 citations
arXivHTMLPDF
DOI
10.1007/978-3-642-38616-9_6

Related papers

Quantum nested search for the shortest vector problem

Runxi Cao, Baocang Wang, Juntao Gao

Physical Review A•Jul 3, 2025•0 citations

A Faster Lattice Reduction Method Using Quantum Search

Christoph Ludwig

Lecture notes in computer science•Jan 1, 2003•27 citations

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time $$2^{1.799n + o(n)}$$ , improving upon the classical time complexities of $$2^{2.465n + o(n)}$$ of Pujol and Stehlé and the $$2^{2n + o(n)}$$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $$2^{0.268n + o(n)}$$ , improving upon the classical time complexity of $$2^{0.298n + o(n)}$$ of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.

Designs Codes and Cryptography•Apr 13, 2015•97 citations

Analysis of the shortest vector problems with quantum annealing to search the excited states

Katsuki Ura, Takashi Imoto, Tetsuro Nikuni +2 more

Abstract The shortest vector problem (SVP) is one of the lattice problems and is the mathematical basis for lattice-based cryptography, which is expected to be post-quantum cryptography. The SVP can be mapped onto the Ising problem, which in principle can be solved by quantum annealing (QA). However, one issue in solving the SVP using QA is that the solution of the SVP corresponds to the first excited state of the problem Hamiltonian. Therefore, QA, which searches for ground states, cannot provide a solution with high probability. In this paper, we propose to adopt an excited-state search of the QA to solve the shortest vector problem. We numerically show that the excited-state search provides a solution with a higher probability than the ground-state search.

arXiv:2209.03721•Japanese Journal of Applied Physics•Feb 8, 2023•7 citations

Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian

Minki Hhan

We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.

arXiv:2608.02478•Aug 3, 2026•4 citations

Better algorithms for search by quantum walks on two-dimensional grid

Andris Ambainis, Artūrs Bačkurs, Nikolajs Nahimovs +1 more

•Jan 1, 2012•0 citations
By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time 21.799n+o(n)2^{1.799n + o(n)}21.799n+o(n) , improving upon the classical time complexities of 22.465n+o(n)2^{2.465n + o(n)}22.465n+o(n) of Pujol and Stehlé and the 22n+o(n)2^{2n + o(n)}22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.268n+o(n)2^{0.268n + o(n)}20.268n+o(n) , improving upon the classical time complexity of 20.298n+o(n)2^{0.298n + o(n)}20.298n+o(n) of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.
Abstract The shortest vector problem (SVP) is one of the lattice problems and is the mathematical basis for lattice-based cryptography, which is expected to be post-quantum cryptography. The SVP can be mapped onto the Ising problem, which in principle can be solved by quantum annealing (QA). However, one issue in solving the SVP using QA is that the solution of the SVP corresponds to the first excited state of the problem Hamiltonian. Therefore, QA, which searches for ground states, cannot provide a solution with high probability. In this paper, we propose to adopt an excited-state search of the QA to solve the shortest vector problem. We numerically show that the excited-state search provides a solution with a higher probability than the ground-state search.
Solving the Shortest Vector Problem in 20.6039n2^{0.6039n}20.6039n Time via Mid-point Hessian
We present randomized algorithms for the shortest vector problem (SVP). For the nnn-dimensional lattice L\mathcal LL, our algorithms solve SVP in time 20.6039n+o(n)2^{0.6039n+o(n)}20.6039n+o(n) classically and 20.5411n+o(n)2^{0.5411n+o(n)}20.5411n+o(n) quantumly and space 20.5n+o(n)2^{0.5n+o(n)}20.5n+o(n), improving the previous best algorithm running in 2n+o(n)2^{n+o(n)}2n+o(n) time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector v∈Lv \in \mathcal Lv∈L, the Hessian at v/2v/2v/2 has the eigenvector close to vvv, which can be used to recover vvv using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo L\mathcal LL, the candidate midpoints are indexed by the parity classes in L/2L\mathcal L/2\mathcal LL/2L. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.