Shortest Vector Problem
Find a shortest nonzero lattice vector.
Quantum · heuristic
Quantum lattice sieving with random access
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Finding many Collisions via Reusable Quantum WalksEurocrypt 2023SourceBibTeX / details | 27 May 2022 | 20.2563 n + o(n) | — | PublishedSource checked |
| 2 | Lattice sieving via quantum random walksAsiacrypt 2021SourceBibTeX / details | 12 May 2021 | 20.2570 n + o(n) | — | PublishedSource checked |
| 3 | Improved Quantum Hypercone Locality Sensitive Filtering in Lattice SievingePrint 2021/1295SourceBibTeX / detailsquantum heuristic locality-sensitive filtering | 27 Sept 2021 | 20.2571 n + o(n) | — | PreprintSource checked |
| 4 | Search problems in cryptography: from fingerprinting to lattice sievingTechnische Universiteit Eindhoven 2016SourceBibTeX / detailsquantum heuristic QCRAM LSF | 16 Feb 2016 | (13/9)n/2 + o(n) | (13/9)n/2 + o(n) | PublishedSource checked |
| 5 | Finding shortest lattice vectors faster using quantum searchDesigns, Codes and Cryptography 2015SourceBibTeX / details | 14 Apr 2015 | 20.268 n + o(n) | 20.268 n + o(n) | PublishedSource checked |
| 6 | An Improved Quantum Algorithm for 3-Tuple Lattice SievingCrypto 2026SourceBibTeX / detailsheuristic QCRAM triple sieving memory tradeoff | 9 Oct 2025 | 20.2846 n + o(n) | 20.1887 n + o(n) | PublishedSource checked |
| 7 | Finding shortest lattice vectors faster using quantum searchDesigns, Codes and Cryptography 2015SourceBibTeX / detailsquantum heuristic angular LSH | 4 Nov 2014 | 20.286 n + o(n) | — | PublishedSource checked |
| 8 | Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice SievingAsiacrypt 2019SourceBibTeX / detailsheuristic QRAM tuple sieving memory tradeoff | 10 Sept 2019 | 20.29893 n + o(n) | 20.1395 n + o(n) | PublishedSource checked |
| 9 | Classical and quantum 3 and 4-sieves to solve SVP with low memoryPQCrypto 2023SourceBibTeX / detailsquantum heuristic triple sieving QCRAM memory tradeoff | 2 Aug 2023 | 20.3098 n + o(n) | 20.1887 n + o(n) | PublishedSource checked |
| 10 | Solving the Shortest Vector Problem in Lattices Faster Using Quantum SearchPost-Quantum Cryptography 2013SourceBibTeX / details | 25 Jan 2013 | 20.312 n + o(n) | 20.208 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Quantum lattice sieving with random access
- Computation
- Quantum
- Rigor
- Heuristic
- Instances
- Heuristic random lists
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Quantum SVP sieve exponents, with quantum memory and access assumptions attached to each result.
- Comparison rules
- Keep the random-list heuristic explicit. State QRAM access, quantum memory, and the operation-count model. Results in different access models need separate categories.
- Tags