Алгоритмы квантовой оптимизации в исследовании операций: методы, приложения и перспективы развития

Реальная ценность квантовых компьютеров может быть раскрыта только благодаря новым приложениям, особенно в операционных исследованиях, где многие сложные проблемы представляют практический интерес и трудно решаемы из-за их вычислительной сложности. Особого внимания в данном контексте заслуживают методы квантовой оптимизации, которые стали важным инструментом для эффективного решения задач в текущем поколении шумных квантовых компьютеров среднего масштаба. Оптимизация повсеместно используется в современных технологиях для молекулярных преобразований, высокоточного зондирования, защиты коммуникационных систем, революционных вычислений и т.д. [1].

Квантовое преимущество заключается в том, что квантовые компьютеры используют квантовые биты или кубиты, которые существуют в суперпозиции и могут представлять несколько состояний одновременно. Эта особенность позволяет квантовым компьютерам исследовать экспоненциально большее пространство решений по сравнению с классическими аналогами, что потенциально приводит к ускорению оптимизации и повышению производительности. За последние два десятилетия было достигнуто большое количество успехов в области квантового управления, и новые приложения продолжают появляться. В другой, но тесно связанной области, вариаци- онные алгоритмы, работающие на квантовых схемах, также предполагают оптимизацию классических параметров управления, что, как ожидается, позволит достичь вычислительных преимуществ с приложениями во многих областях.

Несмотря на то, что подавляющее большинство задач оптимизации можно представить в виде формулировок квадратичной неограниченной бинарной оптимизации, исследователи продолжают изучать и совершенствовать также другие подходы. С одновременным улучшением качества универсальных квантовых компьютеров лидер в квантовой оптимизации еще не определен. С учетом того, что последние достижения в области создания квантовых компьютеров выходят на стадию индустриализации, алгоритмы оптимизации на основе квантовых технологий становятся все более актуальными, что и предопределило выбор темы данной статьи.

Особенности применения квантового приближенного алгоритма оптимизации и квантового адиабатического алгоритма для решения задач нахождения оптимума в различных предметных областях детально исследуют Гушанский С.М., Божич В.И., Потапов В.С., Ветрова Н.А., Филяев А.А., P. William, Vivek Parganiha, D.B. Pardeshi, David E. Bernal, Akshay Ajageka.

Подходы к созданию, использованию и применению алгоритмов квантового машин- ного обучения для решения задач оптимизации описывают Боряев Р.О., Чуваков А.В., Ахмаров А.В., Байдарова А.У., Потапов А.А., Rolando P. Hong Enriquez, Rosa M. Badia, Barbara Chapman, Kirk Bresniker, Scott Pakin, David E. Bernal, Akshay Ajagekar

Высоко оценивая имеющиеся на сегодняшний день наработки, следует отметить, что хотя учеными было доказано, что квантовые алгоритмы оптимизации улучшают качество решения с увеличением глубины, эту закономерность трудно масштабировать на реальном квантовом оборудовании NISQ из-за ошибок, вызванных несовершенством кубитов, таких как перекрестные помехи или деко-геренция, а также ошибок, связанных с неисправными затворами и неточными измерениями.

Итак, цель статьи заключается в изучении особенностей алгоритмов квантовой оптимизации, а также их методов, приложений и перспектив развития.

Большинство алгоритмов квантовой оптимизации предполагают формализацию задачи оптимизации в виде гамильтониана. В физике гамильтониан представляет энергию системы и управляет ее временной эволюцией. В квантовых вычислениях он часто служит важнейшим компонентом для определения измеримых величин и нахождения наиболее благо-

Рис. 1. Квантовые оптимизаторы

(a) общая схема гибридной квантовоклассической системы оптимизации; (b) оптимизация классических полей при управлении молекулой или другой квантовой системой скромного размера; (c) обучение ва- приятных решений путем поиска основного состояния системы [2]. Хотя были установлены некоторые общие рекомендации по построению таких гамильтонианов единого универсального метода пока не существует.

В целом эффективные вариационные гибридные квантово-классические подходы включают два ведущих алгоритма оптимизации, а именно вариационный квантовый решатель (VQE) и QAOA – гибридный (квантово-классический) алгоритм, аппроксимирующий значение оптимального решения бинарной задачи оптимизации, точность которого контролируется гиперпараметром p , являющимся небольшим положительным целым числом. Функция стоимости задачи отображается на гамильтониан, представленный квантовой схемой с глубиной (длиной), зависящей от p . Квантовая схема, реализующая алгоритм, состоит из унитарных вентилей и оценивается несколько раз на квантовом устройстве относительно классически предварительно вычисленных переменных параметров, обновляемых на каждой итерации [3].

Квантовое оптимальное управление (QOC) и вариационный квантовый алгоритм (VQA), как показано на рис. 1(b) и (c) соответственно, также можно отнести к квантовым алгоритмам оптимизации на рис. 1(a).

риативных квантовых схем с помощью классического оптимизатора

И QOC, и VQA вписываются в рамки рис. 1(a), которые можно понимать, как частные случаи ранней парадигмы квантовой оп- тимизации, отличающейся тем, является ли квантовая система естественной (например, молекула) или искусственной (например, соединенные кубиты). Оптимизируемая объективная функция оценивается квантовым ансацем U(θ), но оптимизатор для обновления управляющих переменных является классическим.

Отдельного внимания заслуживает семейство гибридных квантово-классических алгоритмов, получивших название квантовоинформационной рекурсивной оптимизации (QIRO). В QIRO информация, генерируемая квантовыми ресурсами, используется для рекурсивного уменьшения размера оптимизационной задачи с помощью специфических для данной задачи классических оптимизационных процедур (рис. 2).

Рис. 2. Схематическая визуализация основных принципов квантово-информированного алгоритма рекурсивной оптимизации (QIRO)

По мнению авторов QIRO, эта схема позволяет использовать результаты десятилетий исследований в области (классической) комбинаторной оптимизации и адаптировать классические подпрограммы к конкретной задаче оптимизации, тем самым повышая производительность алгоритма. Более того, включение правил обновления, специфичных для конкретной задачи, дает дополнительные преимущества. Оно позволяет расширить область применения алгоритма за пределы архитектур на основе затворов, включая аналоговые устройства. Этот подход напоминает предыдущие подходы, использующие схемы спиновой заморозки в квантовых отжигах и в различных методах Монте-Карло. Более того, для задач с жесткими ограничениями правила обновления могут предложить варианты обеспечения выполнимости за счет дизайна, даже в присутствии шума [4].

Очевидно, что, обладая широким спектром преимуществ, алгоритмы оптимизации, основанные на квантовых вычислениях, способны найти и уже частично находят широкое применение в реальных приложениях. В таблице 1 приведен краткий список основных областей, на которые с большой вероятностью повлияет использование алгоритмов квантовой оптимизации в будущем. Все описанные в таблице 1 прикладные области имеют небольшие размеры задач, которые варьируются между игровыми моделями, например, финансовой сети и более мелкими прикладными моделями, такими как проблемы управления запасами или последовательности процессов комплектования.

Таблица 1. Области применения квантовых оптимизационных алгоритмов

Область применения	Решаемая проблема	Сектор
Составление последовательности	1.    Последовательность комплектации заказов 2.    Последовательность действий в цехе покраски нескольких автомобилей	Автомобильная  промышлен ность Розничная торговля
Маршрутизация	1.    Проблема маршрутизации запасов 2.    Проблема маршрутизации транспортных средств с раздельным спросом 3.    Навигация автобусного парка в реальном времени 4.    Оптимизация маршрутов 5.    Задача маршрутизации транспортных средств с большой емкостью 6.    Прогнозирование транспортных потоков	«Зеленое» распределение Автобусный транспорт Производство Транспорт Умные города Автомобильная  промышлен ность Розничная торговля
Планирование	1.    Параллельное гибкое планирование работы цеха 2.    Задача перестановочного цеха 3.    Планирование взлетно-посадочных полос 4.    Планирование ресурсов порта 5.    Планирование работы цеха без ожидания 6.    Проблема назначения ворот для рейсов 7.    Планирование интервалов времени загрузки	Производство Портовые операции Деятельность аэропорта Портовые операции Авиация Зарядка электромобилей
Дозировка и погрузка	1.    Определение размеров партии 2.    Погрузка авиационных грузов	Производство Авиация
Управление запасами	1.    Проблема управления запасами 2.    Проблема поставки точно в срок	Складское хозяйство Управление операциями
Финансы	1.    Оптимизация портфеля 2.    Прогнозирование рисков/катастроф 3.    Ценообразование	Управление инвестициями Управление рисками

Что касается перспектив развития квантовых алгоритмов оптимизации, то следует отметить, что на сегодняшний день не существует еще алгоритмов с известным экспоненциальным ускорением, поэтому при разработке новых вариантов основное внимание должно уделяется ускорению, превышающему квадратичное. Также отдельного внимания заслуживает улучшение когерентности кубитов и минимизация ошибок, возникающих во время вычислений. Также хотелось бы отметить, что масштабирование количества кубитов и развитие методов, которые позволяют исправлять ошибки – это очень важные задачи с целью усовершенствования функций оп-

И в завершении, можно сказать следующее.

В статье рассмотрены различные алгоритмы квантовой оптимизации, которые могут быть использованы для решения задач оптимизации. Отдельное внимание уделено квантовому оптимальному управлению и вариационному квантовому алгоритму. Также особый акцент сделан на принципах и схемах квантово-информированного алгоритма рекурсивной оптимизации. В разрезе основных областей применения, решаемых проблем и секторов экономики приведены примеры использования кантовых оптимизационных алгоритмов.

тимизации.