О решении задач бинарной оптимизации с использованием алгоритма QAOA

Аннотация

Рассматривается решение задачи 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
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover