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)))$.
翻译：在本文中，我们考虑了 $\Lambda \subseteq \mathbb{Z}^n$ 的晶格最近向量问题 (CVP)，其中 $\Lambda$ 由 $A\in \mathcal{M}_{n\times n}(\mathbb{Z})$ 的生成矩阵给出。令 $b>0$ 为矩阵 $A$ 中元素的绝对值最大值。我们证明，CVP 可以在多项式时间内降至一个二次无约束二元优化 (QUBO) 问题，其二进制变量的数量为 $O(n^2(\log(n)+\log(b)))$，相应二次形式中系数的长度为 $O(n(\log(n)+\log(b)))$。
相关内容
微信扫码咨询专知VIP会员