SVP / Quantum · worst case

Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal · Yanlin Chen · Rajendra Kumar · Yixin Shen

SIAM Journal on Computing 2025

PublishedSource checked

Time bound: 2^{0.835 n + o(n)}
Space bound: 2^{0.5 n + o(n)}

Source / version date: 10 May 2022
Comparison variant: Quantum · worst case
Cost scale: 2^{c n + o(n)}
Computation model: Quantum; polynomially many qubits
QRAM / coherent access: QRAM size 2^{0.293n+o(n)}
classical-memory: 2^{0.5n+o(n)}

Assumptions and source notes

Version 5 contains this bound; the journal article appeared in 2025.

Source location

Abstract, quantum SVP result
Version: 2022-05-10

Primary source ↗

BibTeXDownload .bib

@misc{accs-arxiv-2022,
  author = {Divesh Aggarwal and Yanlin Chen and Rajendra Kumar and Yixin Shen},
  title = {{Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding}},
  booktitle = {SIAM Journal on Computing 54(2):233–278 (2025)},
  year = {2025},
  url = {https://arxiv.org/abs/2002.07955v5},
  keywords = {SVP, BDD, quantum, time-space tradeoffs},
  cr_date = {2022-05-10},
  cr_status = {published},
  cr_venue = {SIAM Journal on Computing 54(2):233–278 (2025)},
  cr_author_ids = {divesh-aggarwal; yanlin-chen; rajendra-kumar; yixin-shen}
}