Space-efficient classical and quantum algorithms for the shortest vector problem. (arXiv:1709.00378v2 [cs.DS] UPDATED)

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 is to find the shortest non-zero 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 with only $2^{0.5n+o(n)}$
space. We then modify 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.

Article web page: