Qubo model for the Closest Vector Problem

Abstract

In this paper we consider the closest vector problem (CVP) for lattices $\Lambda \subseteq {\mathbb{Z}}^n$ given by a generator matrix $A\in {\mathcal{M}}_{n\times n}(\mathbb{Z})$. Let $b>0$ be the maximum of the absolute values of the entries of the matrix $A$. We prove that the CVP can be reduced in polynomial time to a quadratic unconstrained binary optimization (QUBO) problem in $O(n^2(\log (n)+\log (b)))$ binary variables, where the length of the coefficients in the corresponding quadratic form is $O(n(\log (n)+\log (b)))$.