Большие системы

Приведение задач дискретной оптимизации к форме QUBO

А. М. Семенов^ab, С. Р. Усманов^ab, А. К. Федоров<sup>ab

a</sup> Российский квантовый центр (ООО “МЦКТ”), Москва
^b ООО “Облачные квантовые технологии”, Москва

Аннотация: Практические задачи дискретной оптимизации часто содержат многомерные массивы переменных с линейными ограничениями, что осложняет их приведение к форме QUBO (квадратичной бинарной оптимизации без ограничений). В статье предложен систематический подход к преобразованию таких задач, включающий три ключевых этапа: переход от многомерного представления переменных к одномерному с использованием произведения Кронекера матриц, приведение смешанных переменных к бинарным и введение линейных ограничений в целевую функцию через квадратичные штрафы. Для каждого этапа получены явные вычислительные формулы, упрощающие их программную реализацию. Разработанный метод проиллюстрирован на примерах задач теории графов и комбинаторной оптимизации, включая классические постановки, что подтверждает его универсальность. Результаты статьи позволяют стандартизировать процесс адаптации задач для решения на квантовых алгоритмах отжига (например, D-Wave) и классических QUBO-решателях.

Ключевые слова: квадратичная бинарная оптимизация без ограничений (QUBO), модель Изинга, адиабатические квантовые вычисления, комбинаторная оптимизация.

УДК: 621.391 : 519.854

Поступила в редакцию: 30.04.2025
После переработки: 14.05.2025
Принята к печати: 18.08.2025

DOI: 10.31857/S0555292325020041