Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving

Elena Kirshanova · Erik Mårtensson · Eamonn W. Postlethwaite · Subhayan Roy Moulik

Asiacrypt 2019

Time bound

2^{0.29893 n + o(n)}

Space bound

2^{0.1395 n + o(n)}

Source / version date

10 Sept 2019

Comparison variant

Quantum · heuristic

Cost scale

2^{c n + o(n)}

Operation model

Sequential QRAM time; representative tuple size k=30; classical memory 2^{0.1395n+o(n)} and poly(n) qubits

QRAM / random access

Coherent access to classical memory; exponent 0.1395

preprocessing

Included

reference

Table 2, k=28–30; Algorithms 4.1/4.2

Quantum memory

2^{o(n)}; see the source’s access model

Assumptions and source notes

Quantum approximate k-list search supplies a new low-memory tuple-sieving framework. The representative k=30 point is included without claiming an improvement over the unrestricted quantum pair-sieve record. Heuristic low-memory tuple sieve in the QRAM model. Audit: Correctly classified as sequential time, not parallel depth. Added precision .29893 is not a new milestone.

Source location

Abstract; Table 2, k=28–30; Section 4 QRAM model
Version: ePrint 2019/1016, 10 September 2019

Primary source ↗

@inproceedings{kirshanova-et-al-2019,
  author = {Elena Kirshanova and Erik Mårtensson and Eamonn W. Postlethwaite and Subhayan Roy Moulik},
  title = {{Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving}},
  booktitle = {ASIACRYPT 2019},
  year = {2019},
  url = {https://eprint.iacr.org/2019/1016},
  keywords = {SVP, quantum, tuple sieving, QRAM},
  cr_date = {2019-09-10},
  cr_status = {published},
  cr_venue = {ASIACRYPT 2019},
  cr_author_ids = {elena-kirshanova; erik-martensson; eamonn-w-postlethwaite; subhayan-roy-moulik}
}