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

• URL: http://arxiv.org/abs/2002.07955v6
• Date: Sun, 17 Aug 2025 11:17:31 GMT
• Title: Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
• Authors: Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen,
• Abstract summary: We present new algorithms for provable classical/quantum algorithms for the Shortest Vector Problem (SVP)<n>A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement.<n>A quantum algorithm for SVP that runs in time $20.950n+o(n)$ and requires $20.5n+o(n)$ classical memory and poly(n) qubits.
• Score: 4.5686700995634055
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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)}$.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  Gradient descent is one of the most basic algorithms for solving continuous optimization problems. We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$. We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
  arXiv  Detail & Related papers  (2024-07-04T11:03:48Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Do you know what q-means? [42.96240569413475]
  We present a classical $varepsilon$-$k$-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity.<n>We also propose an improved $q$-means quantum algorithm with time complexity.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Quantum Speedups for Bayesian Network Structure Learning [12.02309220445177]
  For networks with $n$ nodes, the fastest known algorithms run in time $O(2n n2)$ in the worst case, with no improvement in two decades.<n>Inspired by recent advances in quantum computing, we ask whether the problem can be solved by a quantum algorithm in time $O(cn)$ for some constant $c$ less than $2$.
  arXiv  Detail & Related papers  (2023-05-31T09:15:28Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
  Collision finding is an ubiquitous problem in cryptanalysis. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters. As an application, we improve the quantum sieving algorithms for the shortest vector problem.
  arXiv  Detail & Related papers  (2022-05-27T14:50:45Z)
• Quantum speedups for treewidth [0.06445605125467573]
  We show three quantum algorithms for computing the exact value of the treewidth of a graph. The fastest known classical algorithm for treewidth uses $O (1.755n)$ time and space. We also give a new classical time-space tradeoff for computing treewidth in $O*(2n)$ time and $O*(sqrt2n)$ space.
  arXiv  Detail & Related papers  (2022-02-16T16:47:47Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Improved Classical and Quantum Algorithms for Subset-Sum [1.376408511310322]
  We present new classical and quantum algorithms for solving random subset-sum instances. We propose new quantum walks for subset-sum, performing better than the previous best time complexity.
  arXiv  Detail & Related papers  (2020-02-12T23:23:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.