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.799 n+ o (n) 2 1.799 n+ o (n), improving upon the classical time complexities of 2^
2.465 n+ o (n) 2 2.465 n+ o (n) of Pujol and Stehlé and the 2^ 2n+ o (n) 2 2 n+ o (n) of
Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 2 …

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.799 n+ o (n)} $, improving upon the classical time complexities of $2^{2.465 n+ 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.286 n+ o (n)} $, improving upon …