Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.12008/49748
How to cite
| Title: | Qubo model for the Closest Vector Problem. |
| Authors: | Canale, Eduardo Qureshi, Claudio Viola, Alfredo |
| Type: | Preprint |
| Keywords: | CVP, Lattices, Condition number, QUBO, Quantum bridge analytics |
| Issue Date: | 2023 |
| Abstract: | In this paper we consider the closest vector problem (CVP) for lattices Λ⊆Zn given by a generator matrix A∈Mn×n(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(n2(log(n)+log(b))) binary variables, where the length of the coefficients in the corresponding quadratic form is O(n(log(n)+log(b))). |
| Sponsors: | La investigación de los autores fue apoyada en parte por CyTeD (“Programa Iberoamericano de Ciencia y Tecnología para el Desarrollo”) proyecto 522RT0131. |
| Citation: | Canale, E., Qureshi, C. y Viola, A. Qubo model for the Closest Vector Problem [Preprint] DOI: 10.48550/arXiv.2304.03616. |
| License: | Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) |
| Appears in Collections: | Publicaciones académicas y científicas - IMERL (Instituto de Matemática y Estadística Rafael Laguardia) |
This item is licensed under a Creative Commons License
