Variational quantum solutions to the Shortest Vector Problem. (arXiv:2202.06757v2 [quant-ph] UPDATED)

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, …

problem quantum solutions