Space-efficient classical and quantum algorithms for the shortest vector problem

Yanlin Chen, Kai Min Chung, Ching-Yi Lai

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conjectured hardness. The Shortest Vector Problem (SVP), which asks to find a shortest nonzero vector in a lattice, is one of the well-known problems that are believed to be hard to solve, even with a quantum computer. In this paper we propose space-efficient classical and quantum algorithms for solving SVP. Currently the best time-efficient algorithm for solving SVP takes 2n+o(n) time and 2n+o(n) space. Our classical algorithm takes 22:05n+o(n) time to solve SVP and it requires only 20:5n+o(n) space. We then adapt our classical algorithm to a quantum version, which can solve SVP in time 21:2553n+o(n) with 20:5n+o(n) classical space and only poly(n) qubits.

Original languageEnglish
Pages (from-to)283-305
Number of pages23
JournalQuantum Information and Computation
Volume18
Issue number3-4
StatePublished - 1 Mar 2018

Keywords

  • Bounded distance decoding
  • Grover search
  • Quantum computation
  • Shortest vector problem

Fingerprint Dive into the research topics of 'Space-efficient classical and quantum algorithms for the shortest vector problem'. Together they form a unique fingerprint.

Cite this