Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven · Michele Mosca · Joop van de Pol

Designs, Codes and Cryptography 2015

Time bound

2^{0.268 n + o(n)}

Space bound

2^{0.268 n + o(n)}

Source / version date

14 Apr 2015

Comparison variant

Quantum · heuristic

Cost scale

2^{c n + o(n)}

QRAM / random access

Quantum-addressable classical hash tables and sieve lists; see Sections 1.3 and 6.3

Quantum memory

Quantum search workspace; the displayed space exponent counts the classical data structures with coherent access

Operation model

Sequential quantum search with SphereSieve; balanced time/space parameters from Theorem 4

reference

LMvP15

Assumptions and source notes

Journal extension published online 14 April 2015. Theorem 4 explicitly gives heuristic quantum time and space exponents approximately 0.268 for the balanced SphereSieve parameters. This is journal rounding of the same result, not a separate later improvement. Quantum random access to classical hash tables and the underlying sieve-list heuristic remain part of the model.

Source location

Theorem 4, Section 6.3
Version: DCC version, 14 April 2015

Primary source ↗

@article{paper-caa5f6c38871,
  author = {Thijs Laarhoven and Michele Mosca and Joop van de Pol},
  title = {{Finding shortest lattice vectors faster using quantum search}},
  journal = {Designs, Codes and Cryptography},
  year = {2015},
  volume = {77},
  pages = {375--400},
  doi = {10.1007/s10623-015-0067-5},
  url = {https://doi.org/10.1007/s10623-015-0067-5},
  cr_date = {2015-04-14},
  cr_status = {published},
  cr_venue = {Designs, Codes and Cryptography},
  cr_author_ids = {thijs-laarhoven; michele-mosca; joop-van-de-pol}
}