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

Lecture notes in computer science

Quantum Algorithms for the Approximate k-List Problem and Their Application to Lattice Sieving

Elena Kirshanova, Erik Mårtensson, Eamonn W. Postlethwaite, Subhayan Roy Moulick

Published Jan 1, 2019• 21 citations
Publisher
DOI
10.1007/978-3-030-34578-5_19

Related papers

An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani +3 more

arXiv:2510.08473•Lecture notes in computer science•Jan 1, 2026•1 citation

On the Practicality of Quantum Sieving Algorithms for the Shortest Vector Problem

João Fernando Doriguello, George Giapitzakis, Alessandro Luongo +1 more

arXiv:2410.13759•Lecture notes in computer science•Jan 1, 2026•7 citations

Finding Many Collisions via Reusable Quantum Walks: Application to Lattice Sieving

Xavier Bonnetain, André Chailloux, André Schrottenloher +1 more

arXiv:2205.14023•Lecture notes in computer science•Jan 1, 2023•29 citations

Lattice Sieving via Quantum Random Walks

André Chailloux, Johanna Loyer

arXiv:2105.05608•Lecture notes in computer science•Jan 1, 2021•46 citations

Estimating Quantum Speedups for Lattice Sieves

Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite +1 more

Lecture notes in computer science•Jan 1, 2020•46 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
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.