Finding shortest lattice vectors faster using quantum search

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 [Formula: see text] , improving upon the classical time complexities of [Formula: see text] of Pujol and Stehlé and the [Formula: see text] of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time [Formula: see text] , improving upon the classical time complexity of [Formula: see text] 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.