Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
Post-Quantum Cryptography 2013
- Time bound
- 20.312 n + o(n)
- Space bound
- 20.208 n + o(n)
- Source / version date
- 25 Jan 2013
- Comparison variant
- Quantum · heuristic
- Cost scale
- 2c n + o(n)
- QRAM / random access
- Quantum-addressable classical lists
- Quantum memory
- O(n) ordinary qubits
- Operation model
- Sequential quantum search under the sieve-distribution heuristic
- reference
- LMvP13
Assumptions and source notes
PQCrypto 2013. The original arXiv abstract gives heuristic quantum SVP time 0.312 and separately provable time 1.799. This row records only the heuristic result. Uses Grover search within sieve algorithms; coherent lookup and memory details must be checked in the algorithm model. Audit: The original theorem supplies space and distinguishes classical coherent storage from ordinary qubits.
Source location
Theorem 1; Section 1.3.2
Version: arXiv:1301.6176v1
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]
@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}
}