Об оценке временной сложности адиабатических вычислений для одного класса целочисленных решеток

И. В. Лысаков

Московский государственный университет имени М. В. Ломоносова

Аннотация: Рассматривается алгоритм решения задачи декодирования с ограниченным расстоянием (BDD) в целочисленных решетках специального вида с использованием адиабатического вычислителя. Получена верхняя оценка необходимого количества кубитов для его выполнения. Выводится асимптотическая оценка времени работы данного алгоритма в зависимости от битовой длины одного из параметров генерации решеток.

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

УДК: 519.712.4+519.719.2

Получено 31.VII.2024

DOI: 10.4213/mvk490