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• 18 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•0 citations

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•1 citation

Lattice Sieving via Quantum Random Walks

André Chailloux, Johanna Loyer

arXiv:2105.05608•Lecture notes in computer science•Jan 1, 2021•39 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•39 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

A practically scalable approach to the closest vector problem for sieving via QAOA with fixed angles

Ben Priestley, Petros Wallden

Abstract The NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography, in much the same way that integer factorisation’s conjectured hardness is at the foundation of cryptosystems like RSA. Recent work with heuristic quantum algorithms (Yan et al 2022 arXiv: 2212.12372 [quant-ph]) indicates the possibility to find close approximations to (constrained) CVP instances that could be incorporated within fast sieving approaches for factorisation. This work explores both the practicality and scalability of the proposed heuristic approach to explore the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims. We also extend the proposal to include an antecedent ‘pre-training’ scheme to find and fix a set of parameters that generalise well to increasingly large lattices, which both optimises the scalability of the algorithm, and permits direct numerical analyses. Our results further indicate a noteworthy quantum speed-up for lattice problems obeying a certain ‘prime’ structure, approaching fifth order advantage for quantum approximate optimisation algorithm of fixed depth p = 10 compared to classical brute-force, motivating renewed discussions about the necessary lattice dimensions for quantum-secure cryptosystems in the near-term.

arXiv:2503.08403•Quantum Science and Technology•Mar 3, 2026•1 citation
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.
Abstract The NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography, in much the same way that integer factorisation’s conjectured hardness is at the foundation of cryptosystems like RSA. Recent work with heuristic quantum algorithms (Yan et al 2022 arXiv: 2212.12372 [quant-ph]) indicates the possibility to find close approximations to (constrained) CVP instances that could be incorporated within fast sieving approaches for factorisation. This work explores both the practicality and scalability of the proposed heuristic approach to explore the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims. We also extend the proposal to include an antecedent ‘pre-training’ scheme to find and fix a set of parameters that generalise well to increasingly large lattices, which both optimises the scalability of the algorithm, and permits direct numerical analyses. Our results further indicate a noteworthy quantum speed-up for lattice problems obeying a certain ‘prime’ structure, approaching fifth order advantage for quantum approximate optimisation algorithm of fixed depth p = 10 compared to classical brute-force, motivating renewed discussions about the necessary lattice dimensions for quantum-secure cryptosystems in the near-term.