On the reduction of the closest vector problem for integet lattices to Ising problem

I. V. Lysakov

Lomonosov Moscow State University

Abstract: We study a reduction from solving closest vector problem (CVP) and bounded distance decoding problem (BDD) in integer lattices to the problem of finding minimum of function defined over a set of binary variables taking values $1$ and $-1$ (Ising problem). We provide estimates for the maximum number of variables sufficient to solve CVP and BDD problems which determine mentioned higher function.

Keywords: integer lattice, closest vector problem, bounded distance decoding, quantum annealing.

UDC: 519.719.2

Received: 15.05.2025

DOI: 10.4213/dm1876