Shortest Vector Problem
Find a shortest nonzero lattice vector.
Heuristic · parallel quantum depth
Parallel quantum circuit depth with 2^{0.2075n+o(n)} quantum memory
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice SievingAsiacrypt 2019SourceBibTeX / detailsheuristic parallel depth | 10 Sept 2019 | 20.1037 n + o(n) | 20.2075 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Parallel quantum circuit depth with 2^{0.2075n+o(n)} quantum memory
- Computation
- Quantum parallel
- Rigor
- Heuristic
- Instances
- Heuristic spherical lists
- Cost scale
- 2^{c n + o(n)} depth
- Parameter
- n
- Description
- Parallel quantum circuit depth with 2^{0.2075n+o(n)} quantum memory
- Comparison rules
- This measures parallel depth using exponentially many quantum memory cells, not sequential operations or total work. Never compare its coefficient with a sequential-time leaderboard.
- Tags
- quantum, parallel depth, heuristic