Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
Post-Quantum Cryptography 2013
PublishedSource checked
- Time bound
- 21.799 n + o(n)
- Space bound
- 21.286 n + o(n)
- Source / version date
- 25 Jan 2013
- Comparison variant
- Quantum · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- Probability exponentially close to 1
- Computation model
- Sequential quantum search
- QRAM / coherent access
- Quantum-addressable classical lists; O(n) ordinary qubits
Assumptions and source notes
Original public bound predates the 2015 journal version.
Source location
Theorem 2, p. 10; Section 1.3 memory model
Version: arXiv:1301.6176v1, 25 January 2013
Selected earlier references
Selected sources cited by this paper.
- Sieve Algorithms for the Shortest Vector Problem are Practical
Phong Q. Nguyen · Thomas Vidick · 2008
Quantum search applied to the earlier heuristic sieve. Section 2.1, Lemma 1 and Theorem 1; reference [41]
- Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)
Xavier Pujol · Damien Stehlé · 2009
Quantum speedup of the birthday saturation algorithm. Section 3.1, Lemma 2 and Theorem 2; reference [44]
- Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem
Xiaoyun Wang · Mingjie Liu · Chengliang Tian · Jingguo Bi · 2011
Studies a two-level sieve and finds no quantum exponent gain over the baseline. Section 2.2; reference [57]
BibTeXDownload .bib
@inproceedings{paper-1873724e57d1,
author = {Thijs Laarhoven and Michele Mosca and Joop van de Pol},
title = {{Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search}},
booktitle = {Post-Quantum Cryptography},
year = {2013},
pages = {83--101},
doi = {10.1007/978-3-642-38616-9_6},
url = {https://arxiv.org/abs/1301.6176},
cr_date = {2013-01-25},
cr_status = {published},
cr_venue = {Post-Quantum Cryptography},
cr_author_ids = {thijs-laarhoven; michele-mosca; joop-van-de-pol}
}