Shortest Vector Problem
Find a shortest nonzero lattice vector.
Heuristic · quantum · minimal sieve-list space
Sequential quantum sieving; space ≤ 2^{(½log₂(4/3)+o(1))n}
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Search problems in cryptography: from fingerprinting to lattice sievingTechnische Universiteit Eindhoven 2016SourceBibTeX / detailsquantum heuristic bounded memory Nguyen–Vidick | 16 Feb 2016 | (13/9)n/2+o(n) | (4/3)n/2+o(n) | PublishedSource checked |
| 2 | Search problems in cryptography: from fingerprinting to lattice sievingTechnische Universiteit Eindhoven 2016SourceBibTeX / detailsquantum heuristic bounded memory Nguyen–Vidick | 16 Feb 2016 | 20.2671 n + o(n) | (4/3)n/2+o(n) | PublishedSource checked |
| 3 | Search problems in cryptography: from fingerprinting to lattice sievingTechnische Universiteit Eindhoven 2016SourceBibTeX / detailsquantum heuristic bounded memory Nguyen–Vidick | 16 Feb 2016 | 20.286 n + o(n) | (4/3)n/2+o(n) | PublishedSource checked |
| 4 | Search problems in cryptography: from fingerprinting to lattice sievingTechnische Universiteit Eindhoven 2016SourceBibTeX / detailsquantum heuristic bounded memory GaussSieve | 16 Feb 2016 | 20.297454 n + o(n) | (4/3)n/2+o(n) | PublishedSource checked |
| 5 | Solving the Shortest Vector Problem in Lattices Faster Using Quantum SearchPost-Quantum Cryptography 2013SourceBibTeX / detailsquantum heuristic Nguyen–Vidick bounded memory | 25 Jan 2013 | 20.312 n + o(n) | 20.208 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Sequential quantum sieving; space ≤ 2^{(½log₂(4/3)+o(1))n}
- Computation
- Quantum
- Rigor
- Heuristic
- Instances
- Arbitrary input; spherical-list heuristic
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Quantum analogues retaining the baseline pair-sieve list-space exponent.
- Comparison rules
- Compare sequential time with total classical-list storage at most the baseline exponent, allowing displayed rounding 0.2075/0.208. Batch Nguyen–Vidick variants and GaussSieve variants must be identified: sequential hash-table processing is not automatically valid for GaussSieve. Require coherent access where used and record ordinary-qubit requirements separately.
- Tags
- SVP, quantum, heuristic, bounded memory, Nguyen–Vidick, GaussSieve