Space-efficient classical and quantum algorithms for the shortest vector problem (pp0283-0305)
          Yanlin Chen, Kai-Min Chung, and Ching-Yi Lai
          doi: https://doi.org/10.26421/QIC18.3-4-7
Abstracts: 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 2^{n+o(n)} time and 2^{n+o(n)} space. Our classical algorithm takes 2^{2.05n+o(n)} time to solve SVP and it requires only 2^{0.5n+o(n)} space. We then adapt our classical algorithm to a quantum version, which can solve SVP in time 2^{1.2553n+o(n)} with 2^{0.5n+o(n)} classical space and only poly(n) qubits.
Key words: shortest vector problem, bounded distance decoding, quantum computation, Grover search