An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

• URL: http://arxiv.org/abs/2510.08473v1
• Date: Thu, 09 Oct 2025 17:13:07 GMT
• Title: An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
• Authors: Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani, Maya-Iggy van Hoof, Stacey Jeffery, Ronald de Wolf,
• Abstract summary: Shortest Vector Problem is one of the cornerstones of post-quantum cryptography.<n>The fastest known attacks on SVP are via so-called sieving methods.<n>In this paper we improve the quantum time complexity of 3-tuple sieving from $20.3098 d$ to $20.2846 d$.
• Score: 1.5327973773729056
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these ''sieving steps'' sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098 d}$ to $2^{0.2846 d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby ''center points'' to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.

Related papers

• A fast and exact approach for stabilizer Rényi entropy via the XOR-FWHT algorithm [0.5735035463793009]
  Quantum advantage is widely understood to rely on key quantum resources beyond entanglement.<n>However, a direct brute-force of all Pauli strings and the corresponding expectation values from a length-$2N$ state vector, where $N$ is the system size, yields an overall computational cost scaling as $O(8N)$.<n>Here we reformulate the second-order stabilizer Rényi entropy in a bitstring language, expose an underlying XOR-convolution structure on $mathbb ZN$, and reduce the computation to $2N$ fast Walsh-Hadamard transforms of length
  arXiv  Detail & Related papers  (2025-12-31T07:35:47Z)
• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  We present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting.<n>Our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified.
  arXiv  Detail & Related papers  (2025-02-13T12:04:39Z)
• A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
  Finding a good approximation of the top eigenvector of a given $dtimes d$ matrix $A$ is a basic and important computational problem. We give two different quantum algorithms that output a classical description of a good approximation of the top eigenvector.
  arXiv  Detail & Related papers  (2024-05-23T16:33:13Z)
• 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)
• 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)
• Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization [43.74656748515853]
  Non-stationary multi-block bilevel optimization problems involve $mgg 1$ lower level problems and have important applications in machine learning. We aim to achieve three properties for our algorithm: a) matching the state-of-the-art complexity of standard BO problems with a single block; (b) achieving parallel speedup by sampling $I$ samples for each sampled block per-iteration; and (c) avoiding the computation of the inverse of a high-dimensional Hessian matrix estimator.
  arXiv  Detail & Related papers  (2023-05-30T04:10:11Z)
• Quantum Lattice Sieving [0.0]
  A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. We present a quantum sieving algorithm that has memory complexity in the size of the length of the sampled vectors at the initial step of the sieve.
  arXiv  Detail & Related papers  (2021-10-26T01:50:48Z)
• Lattice sieving via quantum random walks [0.0]
  lattice-based cryptography is one of the leading proposals for post-quantum cryptography. Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography. We present an algorithm that has a (heuristic) running time of $20.2570 d + o(d)$ where $d$ is the lattice dimension.
  arXiv  Detail & Related papers  (2021-05-12T11:59:30Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding [4.5686700995634055]
  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.
  arXiv  Detail & Related papers  (2020-02-19T01:38:34Z)

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.