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 language | English |
---|---|
Pages (from-to) | 283-305 |
Number of pages | 23 |
Journal | Quantum Information and Computation |
Volume | 18 |
Issue number | 3-4 |
State | Published - 1 Mar 2018 |
Keywords
- Bounded distance decoding
- Grover search
- Quantum computation
- Shortest vector problem