SVP / Heuristic · quantum · memory ≤ 0.1887n

An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

Lynn Engelberts · Yanlin Chen · Amin Shiraz Gilani · Maya-Iggy van Hoof · Stacey Jeffery · Ronald de Wolf

Crypto 2026

PublishedSource checked

Time bound: 2^{0.2846 n + o(n)}
Space bound: 2^{0.1887 n + o(n)}

Source / version date: 9 Oct 2025
Comparison variant: Heuristic · quantum · memory ≤ 0.1887n
Cost scale: 2^{c n + o(n)}
Computation model: Quantum; 2^{0.1887n} classical and QCRAM bits; 2^{o(n)} qubits

Assumptions and source notes

Version 1 already states the bound; publication followed at CRYPTO 2026.

Source location

Abstract
Version: 2025-10-09

Selected earlier references

Selected sources cited by this paper.

Classical and quantum 3 and 4-sieves to solve SVP with low memory
André Chailloux · Johanna Loyer · 2023
Improves the .3098 quantum triple-sieving baseline. Table 1; reference [CL23]
Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving
Elena Kirshanova · Erik Mårtensson · Eamonn W. Postlethwaite · Subhayan Roy Moulik · 2019
Earlier low-memory quantum tuple-sieving baseline. Table 1; reference [KMPM19]

Primary source ↗

BibTeXDownload .bib

@inproceedings{engelberts-et-al-2025,
  author = {Lynn Engelberts and Yanlin Chen and Amin Shiraz Gilani and Maya-Iggy van Hoof and Stacey Jeffery and Ronald de Wolf},
  title = {{An Improved Quantum Algorithm for 3-Tuple Lattice Sieving}},
  booktitle = {CRYPTO 2026},
  year = {2026},
  url = {https://arxiv.org/abs/2510.08473},
  keywords = {SVP, quantum, triple sieving, QCRAM},
  cr_date = {2025-10-09},
  cr_status = {published},
  cr_venue = {CRYPTO 2026},
  cr_author_ids = {lynn-engelberts; yanlin-chen; amin-shiraz-gilani; maya-iggy-van-hoof; stacey-jeffery; ronald-de-wolf}
}