  A fundamental computational problem is to find a shortest non-zero vector in
Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This
problem is believed to be hard even on quantum computers and thus plays a
pivotal role in post-quantum cryptography. In this work we explore how
(efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to
solve SVP. Specifically, we map the problem to that of finding the ground state
of a suitable Hamiltonian. In particular, (i) we establish new bounds for
lattice enumeration, this allows us to obtain new bounds (resp.~estimates) for
the number of qubits required per dimension for any lattices (resp.~random
q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the
optimization space by proposing (a) a different classical optimisation loop or
alternatively (b) a new mapping to the Hamiltonian. These improvements allow us
to solve SVP in dimension up to 28 in a quantum emulation, significantly more
than what was previously achieved, even for special cases. Finally, we
extrapolate the size of NISQ devices that is required to be able to solve
instances of lattices that are hard even for the best classical algorithms and
find that with approximately $10^3$ noisy qubits such instances can be tackled.
