An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
Crypto 2026
PublishedSource checked
- Time bound
- 20.2846 n + o(n)
- Space bound
- 20.1887 n + o(n)
- Source / version date
- 9 Oct 2025
- Comparison variant
- Quantum · heuristic
- Cost scale
- 2c n + o(n)
- Operation model
- Quantum; 2^{0.1887n} classical and QCRAM bits; 2^{o(n)} qubits
- QRAM / random access
- Coherent access to classical memory; exponent 0.1887
- Quantum memory
- 2^{o(n)}; see the source’s access model
Assumptions and source notes
Two-level amplitude amplification with nearby-center preprocessing improves quantum triple sieving at memory exponent 0.1887. It is a memory-constrained improvement, not a new unrestricted quantum-SVP time record. 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]
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}
}