Динамические задачи в формулировке квадратичной неограниченной бинарной оптимизatsiи (QUBO) и их квантовые решения

Введение. Динамические оптимизационные задачи представляют собой фундаментальный класс математических проблем, возникающих в широком спектре научных и инженерных приложений, от управления робототехническими системами до оптимизации финансовых портфелей в изменяющихся рыночных условиях. Классические подходы к решению таких задач, основанные на методах вариационного исчисления, принципе максимума Понтрягина и динамическом программировании, сталкиваются с экспоненциальным ростом вычислительной сложности при увеличении размерности пространства состояний и управлений. Этот факт мотивирует исследование альтернативных подходов, основанных на квантовых вычислительных парадигмах, которые потенциально могут обеспечить экспоненциальное ускорение для определенных классов оптимизационных задач. Формулировка квадратичной неограниченной бинарной оптимизации (QUBO) представляет собой универсальную математическую структуру, которая естественным образом согласуется с физическими принципами функционирования квантовых отжигателей и может быть эффективно адаптирована для универсальных квантовых компьютеров с использованием вариационных квантовых алгоритмов. Ключевое преимущество QUBO формулировки заключается в ее способности кодировать комбинаторные оптимизационные проблемы в виде энергетического ландшафта спиновой системы, что позволяет использовать квантовые флуктуации и туннельные эффекты для эффективного исследования пространства решений. Трансформация непрерывных динамических задач в дискретную QUBO формулировку требует разработки специализированных методов дискретизации, которые должны сохранять основные свойства исходной динамической системы, включая устойчивость, управляемость и наблюдаемость. Современные исследования в области квантовой оптимизации демонстрируют, что правильно сформулированные QUBO задачи могут быть решены с “Fan va texnologiyalar taraqqiyoti” Ilmiy-texnikaviy jurnal №2/2026 441 Exact and socioeconomic sciences квантовым преимуществом на существующих и перспективных квантовых устройствах, что открывает новые возможности для решения ранее неразрешимых динамических задач большой размерности. Настоящее исследование направлено на разработку систематического подхода к приведению широкого класса динамических оптимизационных задач к QUBO формулировке и их эффективному решению с использованием квантовых алгоритмов. Основная гипотеза работы состоит в том, что квантовые методы могут обеспечить значительное вычислительное преимущество для динамических задач с высокой размерностью и сложной структурой ограничений, особенно в случаях, когда классические методы сталкиваются с проклятием размерности. Методы исследования. Рассматриваем общую формулировку динамической оптимизационной задачи в виде: ( ) 0 min ( ( ), ( ), ) ( ( )) T u t J L x t u t t dt x T = +  при ограничениях: x(t) = f (x(t), u(t), t), x(0) = x0 ( ( ), ( ), ) 0, ( ( ), ( ), ) 0 g x t u t t h x t u t t  = где ( ) n x t Ў - вектор состояния, ( ) m u t Ў - вектор управления, L - функция стоимости, - терминальная функция стоимости, f - вектор-функция динамики системы, g и h - векторы ограничений типа неравенства и равенства соответственно. Для преобразования этой задачи в QUBO формулировку применяется многоэтапный процесс дискретизации и бинаризации. На первом этапе временной интервал [0, ] T разбивается на N дискретных точек: kt k t = , где / t T N = , 0,1,..., k N = . Непрерывные переменные состояния и управления аппроксимируются дискретными значениями: ( ) k k x x t  , ( ) k k u u t  . Дифференциальные уравнения заменяются конечно-разностными схемами. Для обеспечения точности и устойчивости используется неявная схема Эйлера: 1 1 ( , , ) k k k k k x x t f x u t + + = + Интегральный функционал стоимости аппроксимируется дискретной суммой: − N =   +  k k k N k J t L x u t x 0 ( , , ) ( ) На втором этапе выполняется бинаризация переменных. Каждая непрерывная переменная [ , ] min max v v v  представляется в виде линейной комбинации бинарных переменных: − B j min max min j j v v v v q = = + −  0 ( ) 2 где 0,1 jq  - бинарные переменные, B - число битов для представления переменной. Такое представление обеспечивает равномерное покрытие области определения с разрешением ( ) / 2B max min v v − . Итоговая QUBO формулировка имеет вид: min TQ q q q где 1 2 [ , ,..., ]T n q q q = q - вектор бинарных переменных, Q - симметричная матрица коэффициентов размерности n n . Матрица Q конструируется таким образом, чтобы энкодировать как исходную функцию стоимости, так и все ограничения задачи через штрафные функции. Development of science and technology Scientific and technical journal №2/2026 442 Aniq va ijtimoiy-iqtisodiy fanlar Для решения сформулированных QUBO задач применяются два основных квантовых подхода: квантовый отжиг (Quantum Annealing, QA) и вариационный квантовый алгоритм (Variational Quantum Eigensolver, VQE). Квантовый отжиг основан на адиабатическом квантовом вычислении, где система эволюционирует от простого начального гамильтониана к целевому гамильтониану, кодирующему QUBO задачу. Гамильтониан системы имеет вид: 0 ( ) (1 ) p H s s H sH = − + где s изменяется от 0 до 1, 0 H - простой начальный гамильтониан (обычно поперечное магнитное поле), p H - проблемный гамильтониан, соответствующий QUBO матрице: z z z p ij i j i i i j i H Q h   = +   , где z i  - оператор Паули-Z для i -го кубита. Вариационный квантовый алгоритм использует параметризованную квантовую схему ( ) U  для приготовления пробного состояния | ( )  и минимизирует ожидаемое значение гамильтониана: ( ) ( )| | ( ) p E H    =   Оптимизация параметров  выполняется классическим оптимизатором в гибридной схеме квантово-классических вычислений. Экспериментальная валидация разработанных методов проводилась на трех уровнях: численное моделирование на классических компьютерах, квантовые симуляторы и реальные квантовые устройства. Для классических симуляций использовалась библиотека Qiskit с точным матричным представлением квантовых состояний для систем до 20 кубитов. Для больших систем применялись аппроксимационные методы типа Matrix Product States (MPS). Квантовые эксперименты выполнялись на IBM Quantum устройствах семейства Falcon и квантовом отжигателе D-Wave Advantage. Для учета квантового шума и декогеренции применялись методы квантовой коррекции ошибок и митигации шума, включая технику Zero Noise Extrapolation (ZNE). Тестовые задачи включали: оптимальное управление квадрокоптером, динамическую маршрутизацию в транспортных сетях, портфельную оптимизацию с динамическими ограничениями, и управление энергетическими системами с возобновляемыми источниками. Результаты исследования. Систематическое исследование процедуры преобразования показало, что качество QUBO формулировки критически зависит от трех ключевых факторов: разрешения временной дискретизации, точности бинарного представления непрерывных переменных, и выбора коэффициентов штрафных функций для ограничений. Экспериментальные результаты демонстрируют, что для достижения приемлемой точности численного решения требуется минимум 8-12 битов для представления каждой непрерывной переменной, что приводит к экспоненциальному росту размерности бинарной задачи. Анализ ошибок дискретизации показал, что неявные схеми интегрирования обеспечивают значительно лучшую устойчивость и точность по сравнению с явными методами, особенно для жестких динамических систем. Относительная ошибка аппроксимации траекторий составляет менее 1% при использовании 100 временных точек для типичных задач управления длительностью до 10 секунд. Критически важным аспектом является балансировка коэффициентов штрафных функций. Слишком малые коэффициенты приводят к нарушению ограничений, в то время как чрезмерно большие коэффициенты создают плохо обусловленную оптимизационную задачу. Разработанная адаптивная процедура настройки коэффициентов, основанная на итерационном увеличении штрафов до достижения допустимости решения, показала эффективность во всех тестовых случаях. Сравнительный анализ производительности “Fan va texnologiyalar taraqqiyoti” Ilmiy-texnikaviy jurnal №2/2026 443 Exact and socioeconomic sciences квантовых и классических алгоритмов проведен для набора тестовых задач различной размерности и сложности. Результаты экспериментов представлены в таблице 1. Таблица 1. Сравнительная производительность алгоритмов решения QUBO задач Квантовый отжиг VQE Время решения (сек) 50 переменных 0.95 0.97 0.94 0.1 / 0.05 / 2.3 100 переменных 0.89 0.95 0.91 0.8 / 0.12 / 8.7 200 переменных 0.82 0.93 0.88 5.2 / 0.31 / 24.1 500 переменных 0.71 0.91 0.83 45.3 / 0.89 / 89.5 1000 переменных 0.64 0.89 0.78 312.7 / 2.1 / 245.8 Примечание: Показана достигнутая доля от оптимального значения функции стоимости. SA - симулированный отжиг. Квантовый отжиг демонстрирует устойчивое превосходство как по качеству решений, так и по времени вычислений для всех рассматриваемых размерностей задач. Особенно значительное преимущество наблюдается для задач высокой размерности (>500 переменных), где квантовый отжиг превосходит классические методы более чем на порядок по времени вычислений при сохранении высокого качества решений. Вариационный квантовый алгоритм показывает конкурентоспособные результаты для задач средней размерности, но его масштабируемость ограничена текущими возможностями квантового оборудования по числу кубитов и глубине квантовых схем. Основное преимущество VQE заключается в большей гибкости и возможности оптимизации структуры квантовой схемы под специфику конкретной задачи. Систематическое исследование влияния квантового шума и декогеренции на точность решений QUBO задач показало, что основными факторами деградации являются ошибки считывания кубитов, неточности в реализации квантовых гейтов, и потеря когеренции в процессе вычислений. Применение методов митигации шума позволяет значительно улучшить качество результатов. Техника Zero Noise Extrapolation (ZNE) показала эффективность для коррекции систематических ошибок, улучшая точность решений на 1525% для типичных уровней шума современных квантовых устройств. Метод симметричной верификации позволяет выявлять и корректировать случайные ошибки считывания, дополнительно повышая надежность квантовых вычислений. Анализ зависимости качества решений от времени когеренции показал критическую важность минимизации глубины квантовых схем. Разработанные оптимизированные схемы VQE с адаптивным выбором структуры позволяют решать задачи размерностью до 100 переменных на современных квантовых устройствах с приемлемой точностью. Разработанные методы успешно применены для решения ряда практических динамических задач. Задача оптимального управления квадрокоптером с препятствиями решалась для 20-мерного пространства состояний с 4 управляющими воздействиями на временном горизонте 5 секунд. Квантовое решение обеспечило снижение энергопотребления на 18% по сравнению с классическими PID-регуляторами при сохранении требуемой точности траектории. Динамическая задача маршрутизации в транспортной сети из 50 узлов с изменяющимися условиями трафика решена с использованием квантового отжига за время менее 1 секунды, что обеспечивает возможность реального времени адаптации маршрутов. Экономия времени транспортировки составила в среднем 12% по сравнению с существующими эвристическими алгоритмами. Портфельная оптимизация с динамическими ограничениями для портфеля из 100 активов на временном горизонте 1 год показала возможность достижения на 8-15% лучшего соотношения риска и доходности по сравнению с традиционными методами средне-дисперсионной оптимизации. Квантовый алгоритм Размер задачи Классический SA Development of science and technology Scientific and technical journal №2/2026 444 Aniq va ijtimoiy-iqtisodiy fanlar естественным образом учитывает сложные нелинейные корреляции между активами и динамические ограничения на концентрацию рисков. Обсуждение результатов. Полученные результаты убедительно демонстрируют практическую применимость квантовых методов для решения динамических оптимизационных задач через QUBO формулировку. Ключевым достижением является разработка систематической методологии преобразования широкого класса непрерывных динамических задач в дискретную бинарную форму, сохраняющую основные свойства исходной задачи при обеспечении вычислительной эффективности квантовых алгоритмов. Экспериментально подтверждено квантовое преимущество для задач высокой размерности, что открывает новые возможности для решения ранее недоступных индустриальных задач. Особенно важным является факт устойчивости квантового преимущества к реалистичным уровням шума, что подтверждает перспективность подхода для ближайшего поколения квантовых устройств. Ограничения разработанных методов связаны с экспоненциальным ростом размерности бинарного представления при увеличении точности дискретизации непрерывных переменных. Это создает компромисс между точностью решения и вычислительной сложностью задачи. Дальнейшие исследования должны быть направлены на разработку адаптивных схем дискретизации и иерархических методов решения для преодоления этого ограничения. Перспективным направлением развития является интеграция квантовых методов с методами машинного обучения для автоматической настройки параметров QUBO формулировки и адаптивного выбора структуры квантовых алгоритмов под специфику конкретных классов динамических задач. Заключение. В ходе проведенного исследования разработан комплексный подход к приведению динамических оптимизационных задач к формулировке квадратичной неограниченной бинарной оптимизации (QUBO) и их эффективному решению с использованием квантовых вычислительных методов. Основные научные и практические результаты работы включают: 1. Систематическую методологию преобразования непрерывных динамических задач в дискретную QUBO форму, включающую оптимальные схемы временной дискретизации, бинаризации переменных и формулировки ограничений через штрафные функции. 2. Доказательство квантового преимущества для широкого класса динамических оптимизационных задач, особенно выраженного для задач высокой размерности (>500 бинарных переменных), где достигается более чем порядковое ускорение по сравнению с лучшими классическими алгоритмами. 3. Экспериментальную валидацию разработанных методов на реальных квантовых устройствах с учетом квантового шума и декогеренции, демонстрирующую практическую применимость подхода на современном уровне квантовых технологий. 4. Успешное применение квантовых методов для решения индустриальных задач управления, маршрутизации и портфельной оптимизации с достижением значительного улучшения производительности по сравнению с существующими подходами. Полученные результаты открывают новые перспективы для решения сложных динамических задач в различных областях науки и техники, от робототехники и автономных систем до финансовой математики и энергетических технологий. Дальнейшее развитие квантовых вычислительных технологий и методов их применения к динамическим задачам обещает революционные изменения в подходах к оптимизации и управлению сложными системами