Título:
Qubo model for the Closest Vector Problem.
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Canale, Eduardo
Qureshi, Claudio
Viola, Alfredo
Qureshi, Claudio
Viola, Alfredo
Tutor:
Tipo de documento:
Preprint
Editor:
Palabras clave:
CVP
Lattices
Condition number
QUBO
Quantum bridge analytics
Lattices
Condition number
QUBO
Quantum bridge analytics
Descriptores:
Año de publicación:
2023
Contenido:
Resumen:
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))).
Descripción:
metadata.articulos.dc.description.uri:
Editorial:
EN:
Financiadores:
La investigación de los autores fue apoyada en parte por CyTeD (“Programa Iberoamericano de Ciencia y Tecnología para el Desarrollo”) proyecto 522RT0131.
Citación:
Canale, E., Qureshi, C. y Viola, A. Qubo model for the Closest Vector Problem [Preprint] DOI: 10.48550/arXiv.2304.03616.
Citación:
metadata.articulos.cc.license.name:
ISBN:
e-ISBN:
ISSN:
ISMN:
Otros identificadores:
Cobertura geográfica:
Cobertura temporal:
Departamento académico:
Grupo de investigación:
Licencia:
Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| CQV23.pdf | Preprint | 115.03 KB | Adobe PDF |