SVP · Heuristic · quantum · memory ≤ 0.1887n

Heuristic · quantum · memory ≤ 0.1887n

Quantum SVP; classical and quantum-addressable memory at most 2^{0.1887n+o(n)}

5 results · 3 papers

QuantumHeuristicHeuristic spherical lists2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	An Improved Quantum Algorithm for 3-Tuple Lattice SievingLynn Engelberts · Yanlin Chen · Amin Shiraz Gilani · Maya-Iggy van Hoof · Stacey Jeffery · Ronald de WolfCrypto 2026Source BibTeX / detailsheuristic QCRAM triple sieving	9 Oct 2025	2^{0.2846 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
2	Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice SievingElena Kirshanova · Erik Mårtensson · Eamonn W. Postlethwaite · Subhayan Roy MoulikAsiacrypt 2019Source BibTeX / detailsheuristic QRAM tuple sieving	10 Sept 2019	2^{0.29893 n + o(n)}	2^{0.1395 n + o(n)}	PublishedSource checked
3	Classical and quantum 3 and 4-sieves to solve SVP with low memoryAndré Chailloux · Johanna LoyerPQCrypto 2023Source BibTeX / detailsquantum heuristic triple sieving QCRAM	2 Aug 2023	2^{0.3098 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
4	Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice SievingElena Kirshanova · Erik Mårtensson · Eamonn W. Postlethwaite · Subhayan Roy MoulikAsiacrypt 2019Source BibTeX / detailsquantum heuristic triple sieving QCRAM	10 Sept 2019	2^{0.3266 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked
5	Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice SievingElena Kirshanova · Erik Mårtensson · Eamonn W. Postlethwaite · Subhayan Roy MoulikAsiacrypt 2019Source BibTeX / detailsquantum heuristic triple sieving QCRAM	10 Sept 2019	2^{0.3349 n + o(n)}	2^{0.1887 n + o(n)}	PublishedSource checked

Comparison definition & assumptions

Regime: Quantum SVP; classical and quantum-addressable memory at most 2^{0.1887n+o(n)}
Computation: Quantum
Rigor: Heuristic
Instances: Heuristic spherical lists
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Quantum SVP; classical and quantum-addressable memory at most 2^{0.1887n+o(n)}
Comparison rules: Compare sequential quantum time, not parallel circuit depth. Record classical, QCRAM and qubit costs separately. Total memory exponent must not exceed 0.1887.
Tags: quantum, heuristic, bounded memory