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

Designs Codes and Cryptography

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

Published Apr 13, 2015• 91 citations
Publisher

Abstract

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.

DOI
10.1007/s10623-015-0067-5

Related papers

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

Abstract 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), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehle ́ and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.286n+o(n), improving upon the classical time complexity of 20.337n+o(n) of Laarhoven. 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. Keywords lattices · shortest vector problem · sieving · quantum search 1

•Jan 1, 2014•1 citation

Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

Miloš Prokop, Petros Wallden

Finding the shortest non-zero vector on a lattice is a fundamental problem in lattices that is believed to be hard both for classical and quantum computers. Two of the three standardised by NIST post-quantum cryptosystems rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve the Shortest Vector Problem (SVP) is crucial to establish confidence in those new standards. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on Noisy Intermediate Scale Quantum (NISQ) devices have in solving SVP has been an active area of research. The qubit-requirement for doing so has been analysed and demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian in an efficient way. Due to the heuristic nature of VQAs no analysis of the performance and specifically of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. In this paper, motivated by Boulebnane and Montanaro [1] work on the k-SAT problem, we propose to use angle pretraining of the Quantum Approximate Optimisation Algorithm (QAOA) for SVP and we demonstrate that QAOA with fixed angles performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and we observe the probability of success scaling as$2^{-0.695n}$with$n$being dimensionality of the search space for a depth$p=3$pre-trained QAOA algorithm. By repeating the algorithm, we get heuristic time complexity$O(2^{0.695n})$to solve the problem with high probability, a bit worse than the fault-tolerant Grover approach of$O(2^{0.5n})$. On the other hand, both the number of qubits, and most importantly the depth of each quantum computation, are considerably better in our approach – Grover requires exponential depth, while each run of constant$p$fixed-angles QAOA requires polynomial depth. Further, we analyse the performance of QAOA in solving approximate-SVP, a version of the problem that one seeks a multiplicative approximation to the shortest vector. As a side result, we propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.

arXiv:2502.05284•IEEE Transactions on Quantum Engineering•Jan 1, 2025•2 citations

Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1 more

The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. 1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 ≤ q ≤ √n, our algorithm takes q^{13n+o(n)} time and requires poly(n)⋅ q^{16n/q²} memory. This tradeoff which ranges from enumeration (q = √n) to sieving (q constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. 2) A quantum algorithm that runs in time 2^{0.9533n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [Divesh Aggarwal et al., 2015] that has a time and space complexity 2^{n+o(n)}. 3) A classical algorithm for SVP that runs in time 2^{1.741n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [Yanlin Chen et al., 2018] that has the same space complexity. The time complexity of our classical and quantum algorithms are expressed using a quantity related to the kissing number of a lattice. A known upper bound of this quantity is 2^{0.402n}, but in practice for most lattices, it can be much smaller and even 2^o(n). In that case, our classical algorithm runs in time 2^{1.292n} and our quantum algorithm runs in time 2^{0.750n}.

Leibniz international proceedings in informatics•Jan 1, 2021•1 citation

Quantum Lattice Sieving

Nishant Rodrigues, Brad Lackey

Lattices are very important objects in the effort to construct cryptographic primitives that are secure against quantum attacks. A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. Asymptotically, sieving is the best known technique for solving the shortest vector problem, however, sieving requires memory exponential in the dimension of the lattice. As a consequence, enumeration algorithms are often used in place of sieving due to their linear memory complexity, despite their super-exponential runtime. In this work, we present a heuristic quantum sieving algorithm that has memory complexity polynomial in the size of the length of the sampled vectors at the initial step of the sieve. In other words, unlike most sieving algorithms, the memory complexity of our algorithm does not depend on the number of sampled vectors at the initial step of the sieve.

arXiv:2110.13352•Oct 26, 2021•0 citations

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1 more

The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. $\bullet$ A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer $4\leq q\leq \sqrt{n}$, our algorithm takes $q^{13n+o(n)}$ time and requires $poly(n)\cdot q^{16n/q^2}$ memory. This tradeoff which ranges from enumeration ($q=\sqrt{n}$) to sieving ($q$ constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. $\bullet$ A quantum algorithm for SVP that runs in time $2^{0.950n+o(n)}$ and requires $2^{0.5n+o(n)}$ classical memory and poly(n) qubits. In Quantum Random Access Memory (QRAM) model this algorithm takes only $2^{0.835n+o(n)}$ time and requires a QRAM of size $2^{0.293n+o(n)}$, poly(n) qubits and $2^{0.5n}$ classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity $2^{n+o(n)}$. $\bullet$ A classical algorithm for SVP that runs in time $2^{1.669n+o(n)}$ time and $2^{0.5n+o(n)}$ space. This improves over an algorithm of [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is $2^{0.402n}$. We conjecture that for most lattices this quantity is a $2^{o(n)}$. Assuming that this is the case, our classical algorithm runs in time $2^{1.292n+o(n)}$, our quantum algorithm runs in time $2^{0.750n+o(n)}$ and our quantum algorithm in QRAM model runs in time $2^{0.667n+o(n)}$.

arXiv:2002.07955•Feb 19, 2020•6 citations

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1 more

Abstract. The most important computational problem on lattices is the shortest vector problem ([Formula: see text]). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for [Formula: see text]. We present the following results: (1) A new algorithm for [Formula: see text] that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer [Formula: see text], our algorithm takes [Formula: see text] time and requires [Formula: see text] memory. This tradeoff, which ranges from enumeration ([Formula: see text]) to sieving ([Formula: see text] constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for [Formula: see text] that runs in time [Formula: see text] and requires [Formula: see text] classical memory and [Formula: see text] qubits. In a quantum random access memory (QRAM) model, this algorithm takes only [Formula: see text] time and requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2 n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 733–742] that has a time and space complexity [Formula: see text]. (3) A classical algorithm for [Formula: see text] that runs in time [Formula: see text] time and [Formula: see text] space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285–306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is [Formula: see text]. We conjecture that for most lattices this quantity is a [Formula: see text]. Assuming that this is the case, our classical algorithm runs in time [Formula: see text], our quantum algorithm runs in time [Formula: see text], and our quantum algorithm in a QRAM model runs in time [Formula: see text]. As a direct application of our result, using the reduction in [L. Ducas, Des. Codes. Cryptogr., 92 (2024), pp. 909–916], we obtain a provable quantum algorithm for the lattice isomorphism problem in the case of the trivial lattice [Formula: see text] ([Formula: see text] LIP ) that runs in time [Formula: see text]. Our algorithm requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space.

SIAM Journal on Computing•Mar 3, 2025•2 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 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), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehle ́ and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.286n+o(n), improving upon the classical time complexity of 20.337n+o(n) of Laarhoven. 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. Keywords lattices · shortest vector problem · sieving · quantum search 1
Finding the shortest non-zero vector on a lattice is a fundamental problem in lattices that is believed to be hard both for classical and quantum computers. Two of the three standardised by NIST post-quantum cryptosystems rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve the Shortest Vector Problem (SVP) is crucial to establish confidence in those new standards. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on Noisy Intermediate Scale Quantum (NISQ) devices have in solving SVP has been an active area of research. The qubit-requirement for doing so has been analysed and demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian in an efficient way. Due to the heuristic nature of VQAs no analysis of the performance and specifically of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. In this paper, motivated by Boulebnane and Montanaro [1] work on the k-SAT problem, we propose to use angle pretraining of the Quantum Approximate Optimisation Algorithm (QAOA) for SVP and we demonstrate that QAOA with fixed angles performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and we observe the probability of success scaling as2−0.695n2^{-0.695n}2−0.695nwithnnnbeing dimensionality of the search space for a depthp=3p=3p=3pre-trained QAOA algorithm. By repeating the algorithm, we get heuristic time complexityO(20.695n)O(2^{0.695n})O(20.695n)to solve the problem with high probability, a bit worse than the fault-tolerant Grover approach ofO(20.5n)O(2^{0.5n})O(20.5n). On the other hand, both the number of qubits, and most importantly the depth of each quantum computation, are considerably better in our approach – Grover requires exponential depth, while each run of constantpppfixed-angles QAOA requires polynomial depth. Further, we analyse the performance of QAOA in solving approximate-SVP, a version of the problem that one seeks a multiplicative approximation to the shortest vector. As a side result, we propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. 1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 ≤ q ≤ √n, our algorithm takes q^{13n+o(n)} time and requires poly(n)⋅ q^{16n/q²} memory. This tradeoff which ranges from enumeration (q = √n) to sieving (q constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. 2) A quantum algorithm that runs in time 2^{0.9533n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [Divesh Aggarwal et al., 2015] that has a time and space complexity 2^{n+o(n)}. 3) A classical algorithm for SVP that runs in time 2^{1.741n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [Yanlin Chen et al., 2018] that has the same space complexity. The time complexity of our classical and quantum algorithms are expressed using a quantity related to the kissing number of a lattice. A known upper bound of this quantity is 2^{0.402n}, but in practice for most lattices, it can be much smaller and even 2^o(n). In that case, our classical algorithm runs in time 2^{1.292n} and our quantum algorithm runs in time 2^{0.750n}.
Lattices are very important objects in the effort to construct cryptographic primitives that are secure against quantum attacks. A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. Asymptotically, sieving is the best known technique for solving the shortest vector problem, however, sieving requires memory exponential in the dimension of the lattice. As a consequence, enumeration algorithms are often used in place of sieving due to their linear memory complexity, despite their super-exponential runtime. In this work, we present a heuristic quantum sieving algorithm that has memory complexity polynomial in the size of the length of the sampled vectors at the initial step of the sieve. In other words, unlike most sieving algorithms, the memory complexity of our algorithm does not depend on the number of sampled vectors at the initial step of the sieve.
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. ∙\bullet∙ A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4≤q≤n4\leq q\leq \sqrt{n}4≤q≤n​, our algorithm takes q13n+o(n)q^{13n+o(n)}q13n+o(n) time and requires poly(n)⋅q16n/q2poly(n)\cdot q^{16n/q^2}poly(n)⋅q16n/q2 memory. This tradeoff which ranges from enumeration (q=nq=\sqrt{n}q=n​) to sieving (qqq constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. ∙\bullet∙ A quantum algorithm for SVP that runs in time 20.950n+o(n)2^{0.950n+o(n)}20.950n+o(n) and requires 20.5n+o(n)2^{0.5n+o(n)}20.5n+o(n) classical memory and poly(n) qubits. In Quantum Random Access Memory (QRAM) model this algorithm takes only 20.835n+o(n)2^{0.835n+o(n)}20.835n+o(n) time and requires a QRAM of size 20.293n+o(n)2^{0.293n+o(n)}20.293n+o(n), poly(n) qubits and 20.5n2^{0.5n}20.5n classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity 2n+o(n)2^{n+o(n)}2n+o(n). ∙\bullet∙ A classical algorithm for SVP that runs in time 21.669n+o(n)2^{1.669n+o(n)}21.669n+o(n) time and 20.5n+o(n)2^{0.5n+o(n)}20.5n+o(n) space. This improves over an algorithm of [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is 20.402n2^{0.402n}20.402n. We conjecture that for most lattices this quantity is a 2o(n)2^{o(n)}2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n)2^{1.292n+o(n)}21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n)2^{0.750n+o(n)}20.750n+o(n) and our quantum algorithm in QRAM model runs in time 20.667n+o(n)2^{0.667n+o(n)}20.667n+o(n).
Abstract. The most important computational problem on lattices is the shortest vector problem ([Formula: see text]). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for [Formula: see text]. We present the following results: (1) A new algorithm for [Formula: see text] that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer [Formula: see text], our algorithm takes [Formula: see text] time and requires [Formula: see text] memory. This tradeoff, which ranges from enumeration ([Formula: see text]) to sieving ([Formula: see text] constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for [Formula: see text] that runs in time [Formula: see text] and requires [Formula: see text] classical memory and [Formula: see text] qubits. In a quantum random access memory (QRAM) model, this algorithm takes only [Formula: see text] time and requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2 n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 733–742] that has a time and space complexity [Formula: see text]. (3) A classical algorithm for [Formula: see text] that runs in time [Formula: see text] time and [Formula: see text] space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285–306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is [Formula: see text]. We conjecture that for most lattices this quantity is a [Formula: see text]. Assuming that this is the case, our classical algorithm runs in time [Formula: see text], our quantum algorithm runs in time [Formula: see text], and our quantum algorithm in a QRAM model runs in time [Formula: see text]. As a direct application of our result, using the reduction in [L. Ducas, Des. Codes. Cryptogr., 92 (2024), pp. 909–916], we obtain a provable quantum algorithm for the lattice isomorphism problem in the case of the trivial lattice [Formula: see text] ([Formula: see text] LIP ) that runs in time [Formula: see text]. Our algorithm requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space.