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:2002.07955 · SIAM Journal on Computing

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

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen

Published Mar 3, 2025• 25 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/22m1486959

Related papers

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

Lattice Problems: New Lower and Upper Bounds

Yi Tang

In the upcoming era of quantum computation, those successful classical, number-theoretical public-key cryptosystems that get widely deployed nowadays, such as RSA or ElGamal, all face severe insecurity if the adversary gets access to quantum computers. More urgently, time-insensitive secrets on today’s systems are facing immediate threats of the same level due to the “harvest now, decrypt later” attack. The field of post-quantum cryptography aims at building quantum-safe systems to prepare for the future. Among all candidate post-quantum proposals, lattice-based cryptography, which builds cryptosystems based on lattice problems, so far provides the best results in terms of performance, simplicity, and versatility. It is thus important to better understand the complexity of lattice problems. In this thesis, we study a couple of new lower and upper bounds for various lattice problems under various complexity notions. These new results include: 1. (Fine-grained hardness/lower bounds.) The fine-grained (exponential-time) complexity studies the precise constant c in the 2^{n^c} or 2^{c·n} running time for solving a computational problem, usually based on (variants of) the exponential time hypothesis (ETH) or the strong exponential time hypothesis (SETH). Under this complexity notion, for the bounded distance decoding problem (BDD), we give quantitatively improved bounds on the approximation factor α for which BDD_α cannot be solved in 2^{o(n)} or 2^{c·n} time, assuming variants of ETH or SETH, respectively, and for part of our results also assuming a geometric conjecture known as exponential lattice kissing number. For the shortest vector problem (SVP), we show a qualitatively improved result that for some constant approximation factor γ>1, SVP_γ cannot be solved in 2^{c·n} time, assuming a variant of SETH; previously, only analogous result for non-approximate, exact SVP was known. 2. (“Standard” NP-hardness.) The NP-hardness is a classical flag for identifying a computational problem as being hard. For SVP, previously only NP-hardness results under randomized reductions are known (except in corner cases), and whether SVP is “standardly” NP-hard under deterministic reductions is a notoriously longstanding open problem. We propose conjectures about ways to derandomize existing reductions, which would lead to the “standard” NP-hardness of approximate SVP. We also present empirical evidences that support the conjectures. 3. (Parallel algorithms/upper bounds.) The parallel complexity/sequentiality of a computational problem is crucial for its applications in time-release/timed cryptography. We show logarithmic-depth parallel algorithms for a sequential version of the short integer solution problem (SIS), which is used in a certain proof of sequential work (PoSW) timed-cryptographic protocol. This means that sequential SIS has low parallel complexity, as opposed to its previous conjecture. Moreover, we show a polylogarithmic-depth parallel attack that (almost) breaks that PoSW protocol.

•Jan 1, 2025•0 citations

Quantum Time-Space Tradeoffs for Matrix Problems

Paul W. Beame, Niels Kornerup, Michael Whitmeyer

Abstract. We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.

arXiv:2401.05321•SIAM Journal on Computing•May 20, 2026•5 citations

Space-efficient classical and quantum algorithms for the shortest vector problem

Yanlin Chen, Kai-Min Chung, Ching–Yi Lai

A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conjectured hardness. The Shortest Vector Problem (SVP), which asks to find a shortest nonzero vector in a lattice, is one of the well-known problems that are believed to be hard to solve, even with a quantum computer. In this paper we propose space-efficient classical and quantum algorithms for solving SVP. Currently the best time-efficient algorithm for solving SVP takes 2^{n+o(n)} time and 2^{n+o(n)} space. Our classical algorithm takes 2^{2.05n+o(n)} time to solve SVP and it requires only 2^{0.5n+o(n)} space. We then adapt our classical algorithm to a quantum version, which can solve SVP in time 2^{1.2553n+o(n)} with 2^{0.5n+o(n)} classical space and only poly(n) qubits.

arXiv:1709.00378•Quantum Information and Computation•Mar 1, 2018•5 citations

Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina +1 more

We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in $\widetilde O(1.859^n)$ time and $\widetilde O(1.315^n)$ QRAM space.

quant-pharXiv:2604.02233•Leibniz international proceedings in informatics•Apr 3, 2026•2 citations

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
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.
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}.
In the upcoming era of quantum computation, those successful classical, number-theoretical public-key cryptosystems that get widely deployed nowadays, such as RSA or ElGamal, all face severe insecurity if the adversary gets access to quantum computers. More urgently, time-insensitive secrets on today’s systems are facing immediate threats of the same level due to the “harvest now, decrypt later” attack. The field of post-quantum cryptography aims at building quantum-safe systems to prepare for the future. Among all candidate post-quantum proposals, lattice-based cryptography, which builds cryptosystems based on lattice problems, so far provides the best results in terms of performance, simplicity, and versatility. It is thus important to better understand the complexity of lattice problems. In this thesis, we study a couple of new lower and upper bounds for various lattice problems under various complexity notions. These new results include: 1. (Fine-grained hardness/lower bounds.) The fine-grained (exponential-time) complexity studies the precise constant c in the 2^{n^c} or 2^{c·n} running time for solving a computational problem, usually based on (variants of) the exponential time hypothesis (ETH) or the strong exponential time hypothesis (SETH). Under this complexity notion, for the bounded distance decoding problem (BDD), we give quantitatively improved bounds on the approximation factor α for which BDD_α cannot be solved in 2^{o(n)} or 2^{c·n} time, assuming variants of ETH or SETH, respectively, and for part of our results also assuming a geometric conjecture known as exponential lattice kissing number. For the shortest vector problem (SVP), we show a qualitatively improved result that for some constant approximation factor γ>1, SVP_γ cannot be solved in 2^{c·n} time, assuming a variant of SETH; previously, only analogous result for non-approximate, exact SVP was known. 2. (“Standard” NP-hardness.) The NP-hardness is a classical flag for identifying a computational problem as being hard. For SVP, previously only NP-hardness results under randomized reductions are known (except in corner cases), and whether SVP is “standardly” NP-hard under deterministic reductions is a notoriously longstanding open problem. We propose conjectures about ways to derandomize existing reductions, which would lead to the “standard” NP-hardness of approximate SVP. We also present empirical evidences that support the conjectures. 3. (Parallel algorithms/upper bounds.) The parallel complexity/sequentiality of a computational problem is crucial for its applications in time-release/timed cryptography. We show logarithmic-depth parallel algorithms for a sequential version of the short integer solution problem (SIS), which is used in a certain proof of sequential work (PoSW) timed-cryptographic protocol. This means that sequential SIS has low parallel complexity, as opposed to its previous conjecture. Moreover, we show a polylogarithmic-depth parallel attack that (almost) breaks that PoSW protocol.
Abstract. We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.
A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conjectured hardness. The Shortest Vector Problem (SVP), which asks to find a shortest nonzero vector in a lattice, is one of the well-known problems that are believed to be hard to solve, even with a quantum computer. In this paper we propose space-efficient classical and quantum algorithms for solving SVP. Currently the best time-efficient algorithm for solving SVP takes 2^{n+o(n)} time and 2^{n+o(n)} space. Our classical algorithm takes 2^{2.05n+o(n)} time to solve SVP and it requires only 2^{0.5n+o(n)} space. We then adapt our classical algorithm to a quantum version, which can solve SVP in time 2^{1.2553n+o(n)} with 2^{0.5n+o(n)} classical space and only poly(n) qubits.
We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in O~(1.859n)\widetilde O(1.859^n)O(1.859n) time and O~(1.315n)\widetilde O(1.315^n)O(1.315n) QRAM space.
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.