Qubo model for the Closest Vector Problem

04/07/2023
by   Eduardo Canale, et al.
0

In this paper we consider the closest vector problem (CVP) for lattices Λ⊆ℤ^n given by a generator matrix A∈ℳ_n× n(ℤ). 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))).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset