Сведение задачи поиска ближайшего вектора для целочисленных решеток к задаче Изинга

И. В. Лысаков

МГУ имени М. В. Ломоносова

Аннотация: Рассматривается алгоритм сведения задач поиска ближайшего вектора (CVP) и декодирования с ограниченным расстоянием (BDD) в целочисленных решетках к задаче минимизации функционала, определенного над множеством переменных, принимающих значения $1$ и $-1$ (задача Изинга). Доказаны оценки для максимального количества переменных, требуемых для определения упомянутого выше функционала, достаточных для решения задач CVP и BDD.

Ключевые слова: целочисленная решетка, задача поиска ближайшего вектора, декодирование с ограниченным расстоянием, квантовый отжиг.

УДК: 519.719.2

Статья поступила: 15.05.2025

DOI: 10.4213/dm1876