Space-efficient classical and quantum algorithms for the shortest vector problem
Quantum Information and Computation 2018
PublishedSource checked
- Time bound
- 21.2553 n + o(n)
- Space bound
- 20.5 n + o(n)
- Source / version date
- 31 Aug 2017
- Comparison variant
- Quantum · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- Randomized; high success probability
- Computation model
- Elementary quantum-gate complexity; sequential
- QRAM / coherent access
- Classical advice and poly(n) qubits; see circuit construction
Assumptions and source notes
Classical discrete-Gaussian advice; polynomial quantum workspace.
Source location
arXiv v1 abstract; final Theorem 12, pp. 18–19
Version: arXiv:1709.00378v1, 31 August 2017; final theorem checked in v2
Selected earlier references
Selected sources cited by this paper.
- Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2015
compares the smaller-space algorithm with the 2^n baseline v1 introduction, PDF p. 1, reference [16]
- Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!
Divesh Aggarwal · Daniel Dadush · Noah Stephens-Davidowitz · 2015
Uses discrete-Gaussian sampling and BDD reductions. Theorems 9–10 and bibliography [45]
BibTeXDownload .bib
@article{chen-chung-lai-2017,
author = {Yanlin Chen and Kai-Min Chung and Ching-Yi Lai},
title = {{Space-efficient classical and quantum algorithms for the shortest vector problem}},
journal = {Quantum Information and Computation},
year = {2018},
volume = {18},
number = {3--4},
pages = {285--307},
url = {https://arxiv.org/abs/1709.00378},
cr_date = {2017-08-31},
cr_date_precision = {day},
cr_status = {published},
cr_venue = {Quantum Information and Computation},
cr_author_ids = {yanlin-chen; kai-min-chung; ching-yi-lai},
note = {arXiv:1709.00378, first submitted 31 August 2017}
}