О решении задач бинарной оптимизации с использованием алгоритма QAOA
Получена: 09.10.2026 Доработана: 16.10.2026 Принята: 20.10.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 298–301
Аннотация
Рассматривается решение задачи QUBO с использованием QAOA с фиксированными параметрами и числом слоев, линейно растущим с размером задачи. Результаты численного эксперимента показывают, что при увеличении размера задачи медианное число запусков схемы, необходимое для получения решения с заданным коэффициентом аппроксимации, вопреки ожиданию не возрастает. В ходе анализа запутанности обнаружено неожиданное убывание её пикового значения с ростом глубины. На основе этого наблюдения построен полностью классический квантово-вдохновлённый алгоритм, в котором запутанность отсутствует. На тестовых наборах GSet MaxCut размером до 20 000 переменных отношение найденного разреза к наилучшему известному превышает 0.95 в подавляющем большинстве случаев.
Ключевые слова: QAOA, QUBO, MaxCut, фиксированные параметры, запутанность.
BibTeX
@article{IS-Chernyavskiy-Bantysh-Kulikov-Kiktenko2026,
author = {Чернявский, Андрей Юрьевич and Бантыш, Борис Игоревич and Куликов, Денис Александрович and Киктенко, Евгений Олегович},
title = {{О решении задач бинарной оптимизации с использованием алгоритма QAOA}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {298--301},
}
AMSBIB
\RBibitem{IS-Chernyavskiy-Bantysh-Kulikov-Kiktenko2026}
\by А.\,Ю.~Чернявский, Б.\,И.~Бантыш, Д.\,А.~Куликов, Е.\,О.~Киктенко
\paper О решении задач бинарной оптимизации с использованием алгоритма QAOA
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 298--301
EN