Shortest Vector Problem
Find a shortest nonzero lattice vector.
Quantum · no QRAM
Exact Euclidean SVP without coherent random access to an exponential classical database
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance DecodingSIAM Journal on Computing 2025SourceBibTeX / detailsprovable quantum No QRAM | 10 May 2022 | 20.95 n + o(n) | 20.5 n + o(n) | PublishedSource checked |
| 2 | Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance DecodingSTACS 2021SourceBibTeX / detailsprovable no QRAM | 10 Mar 2021 | 20.9533 n + o(n) | 20.5 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact Euclidean SVP without coherent random access to an exponential classical database
- Computation
- Quantum without QRAM
- Rigor
- Model dependent
- Instances
- Arbitrary lattices
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Worst-case quantum SVP with no quantum random access to an exponential classical database.
- Comparison rules
- Record the exact parameter regime, cost unit, distribution and access assumptions. A source and BibTeX are required for new submissions. This template makes no claim to a universal exponent.
- Tags
- quantum, no QRAM, arbitrary lattices, access model