Гибридный подход к решению задач на квантовых компьютерах

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

Рис. 1. Гибридные алгоритмы комбинируют вычисления на (a) классических и (б) квантовых компьютерах. Эти алгоритмы разработаны для наилучшего раскрытия сильных качеств каждой из технологий с учетом их слабостей. Например, классический компьютер неэффективен для квантового моделирования, тогда как современные квантовые компьютеры не могут работать с многопараметрическими задачами

Гибридизация квантовых и классических алгоритмов — один из возможных способов решения практических задач на уже существующих квантовых системах. Гибридные алгоритмы используют мощь квантовых вычислений, применяя при этом классические машины для преодоления ограничений малых квантовых систем текущего поколения, обозначаемого как NISQ (noisy intermediate-scale quantum — зашумленные квантовые системы умеренного масштаба, рис. 1). Такой подход работает не только для задач оптимизации, но и для других проблематик, включая квантовое моделирование и квантовое машинное обучение [1-4]. Например, классические компьютеры с большим объемом памяти могут содержать всю информацию о какой-либо глобальной задаче, что затруднительно для квантовых машин с небольшим числом кубитов. В то же время в ряде случаев квантовые алгоритмы показывают лучшую производительность. Для четкого отделения частей гибридных алгоритмов, выполняемых на принципиально различных типах оборудования, будем говорить о классических и квантовых этапах вычислений, проводящихся соответственно на стандартной вычислительной технике (включая графические ускорители и программируемые вентильные матрицы) и на квантовых компьютерах (как универсальных, так и работающих на базе квантового отжига).

Здесь мы рассмотрим два класса устройств эпохи NISQ на примерах систем IBM и D-Wave (D-Wave 2000Q), предоставленных Администрацией по национальной ядерной безопасности (NNSA) и размещенных в Лос-Аламосской национальной лаборатории. Системы IBM относятся к классу универсальных квантовых вычислителей, описывающих систему квантовых вентилей посредством языка квантового ассемблера. Системы D-Wave, представляющие класс компьютеров на базе квантового отжига, решают вычислительные задачи с использованием особенностей эволюции квантово-механической системы к основному состоянию, в котором закодирована задача оптимизации. Хотя эти два подхода существенно различаются, у них много общих ограничений и нерешенных проблем.

Разработкой универсальных квантовых компьютеров занимаются также компании Rigetti, Google, Microsoft, IonQ.

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

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

Представленные здесь схемы декомпозиции — естественное развитие вариационных квантовых алгоритмов, таких как квантовый алгоритм решения вариационной задачи на собственные значения (VQE, variational quantum eigensolver) и алгоритм квантового приближения для задачи оптимизации (QAOA, quantum approximate optimization algorithm). Классический компьютер не только находит наиболее подходящие параметры, но и подбирает оптимальный размер подзадач для квантовых этапов. С нынешними возможностями квантовых компьютеров данный подход не дает «квантового превосходства», поскольку ограничен ускорением, получаемым на уровне подзадач. Тем не менее размер подзадач выбирается таким образом, чтобы извлечь максимум из квантовых вычислений — задействовать все доступные кубиты. Очевидно, что два n-кубитных квантовых компьютера менее производительны, чем один 2n-кубитный; таким образом, использование схем декомпозиции дает тем большее ускорение, чем больше размер исходной задачи. Как только квантовое оборудование станет достаточно мощным для решения практических задач, при котором не требуется их разбиение на части, методы декомпозиции с их накладными расходами утратят свое преимущество. Но пока нет физических компьютеров с 2n-кубитами, методы декомпозиции дают реальную возможность воспользоваться вычислительной мощностью имеющегося современного квантового оборудования.

В Бюро научно-технической информации Министерства энергетики США считают, что QAOA превосходит все известные классические алгоритмы оптимизации для особенно трудных вариантов задачи максимального разреза (MAXCUT). Но здесь мы не будем анализировать доказательства квантового превосходства, а ответим на вопрос: если все эти методы работают, как можно находить решения удовлетворительного качества в условиях ограничений оборудования поколения NISQ? Как, исходя из того, что все эти методы дают превосходство лишь на задачах, размер которых позволяет произвести их непосредственное выполнение на доступных нам квантовых компьютерах, получить эффект на практических задачах? Все декомпозиционные методы основываются на предположении о существовании методов квантовой оптимизации, дающих превосходство на системах поколения NISQ, хотя демонстрация такого превосходства — это пока еще область активных исследований.

Существует несколько фреймворков, которые обеспечивают реализацию гибридных алгоритмов. В их числе фреймворк XACC из Окриджской национальной лаборатории, предназначенный как для универсальных квантовых компьютеров, так и для систем D-Wave, и фреймворк от компании Rigetti, предоставляемый в виде облачного сервиса для применения на универсальных квантовых системах. Эти фреймворки используют традиционную сопроцессорную модель, представляя квантовые процессорные устройства как сопроцессоры для выполнения специализированного программного ядра с учетом особенностей взаимодействия между классическим и квантовым оборудованием.

Обзор алгоритмических подходов

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

Квантовый отжиг

Компания D-Wave выпускает системы на базе квантового отжига — 2X (до 1152 кубитов) и 2000Q (до 2048 кубитов), которые посредством квантовой запутанности между кубитами описывают модель Изинга, функция потерь которой — гамильтониан квантово-механической системы — минимизируется в результате квантового отжига. Эти системы способны решать задачи оптимизации, машинного обучения, дискретизации, имитационного моделирования, максимизации и квадратичной неограниченной бинарной оптимизации (QUBO, quadratic unconstrained binary optimization).

Современные системы D-Wave имеют ряд физических ограничений, среди которых недостаточная точность, разреженная связность, ограниченное количество кубитов. Переменные задачи не отображаются взаимно однозначно на доступные кубиты — каждая переменная представляется как цепочка кубитов, получаемых путем вложения задачи в аппаратный граф Chimera перед отжигом. Решения, получаемые только на квантовом процессоре, ограничены наибольшим числом вершин-переменных, которые могут быть представлены на оборудовании D-Wave. На системе 2000Q задачи размером до 64 переменных могут быть вложены в 64 попарно связанных узла-переменных. Для решения более масштабных задач требуются квантово-классические подходы.

Инструмент qbsolv от D-Wave позволяет решать большие задачи квадратичной неограниченной бинарной оптимизации с использованием гибридного квантово-классического алгоритма [4]. В нем используется динамическая декомпозиция: в течение каждой итерации алгоритма осуществляется локальный поиск в достаточно широкой окрестности, в рамках которого на квантовом процессоре решается QUBO-подзадача. Размер подзадачи ограничивается количеством переменных, которые могут быть вложены в оборудование. Цикл qbsolv сходится к решению с наименьшей энергией.

Универсальные квантовые компьютеры

Универсальные квантовые компьютеры в ближайшей перспективе вряд ли превзойдут масштаб в несколько сотен кубитов (без коррекции ошибок). Эти системы поколения NISQ все еще непригодны для выполнения популярных квантовых алгоритмов (например, алгоритма Шора) при решении задач, имеющих практический смысл. Это связано с небольшим количеством кубитов и ограниченным числом вентилей, которые могут быть выполнены до того, как из-за накопленных ошибок выходные данные начнут расходиться. Для преодоления этого ограничения созданы специальные алгоритмы, из которых QAOA и VQE — самые известные. QAOA может использовать как вариационные, так и аналитические стратегии для подбора параметров. Вариационные алгоритмы комбинируют вычисления на небольших квантовых процессорах и на классических вычислительных мощностях с целью выйти на основное состояние для гамильтониана задачи, которая может быть как чисто классической (QUOA), так и квантовой (VQE). Пробная подстановка («анзац») применяется для ряда параметризованных вентилей. Анзац, или пробное состояние, подготавливается на квантовом процессоре, после чего измеряется энергия квантово-механической системы (рис. 2).

Рис. 2. Основная схема вариационных гибридных алгоритмов. Вариационный цикл стартует с некоторым начальным предположением θ0 (а). Далее пробное состояние |ψ(θ) готовится на квантовом компьютере для каждого шага, замеряется, а результаты передаются на классический компьютер (б). Классическая оптимизационная ветвь алгоритма использует эти измерения для выбора нового набора параметров θ, и цикл продолжается, завершаясь при получении решения удовлетворительного качества

Преимущество вариационных алгоритмов в том, что анзац-подстановка может быть выбрана сообразно количеству вентилей, доступных на системе поколения NISQ. Это приводит к необходимости различных компромиссов в вопросах качества пробных состояний, сложности классической задачи оптимизации, количества накопленных ошибок. Например, в работе [5] использован недавно представленный аппаратно-эффективный анзац (рис. 3, б), который использует особенности естественного запутывания, доступного в квантовой системе, что уменьшает количество ошибок; однако для классического компьютера в этом случае становится сложнее подобрать оптимальные параметры.

Рис. 3. Схема квантового локального поиска в применении к задаче выявления двух сетевых сообществ (кластеризация графа на два кластера). Алгоритмы на квантовых системах (б), в свою очередь, могут быть гибридными, как, например, QAOA, представленный на рис. 2

Общий гибридный подход

Поскольку системы поколения NISQ ограничены по качеству и по числу кубитов, они не могут непосредственно обрабатывать задачи практически значимого размера. Вариационные алгоритмы решают только первую часть проблемы — определение числа кубитов. С использованием анзац-техники можно как снизить потребности в числе вентилей, так и обойти проблему быстрого накопления ошибок. Тем не менее это целиком не снимает проблему размера задачи. Естественный выход в этой ситуации — проводить декомпозицию задачи (статическую или динамическую), решать вычислительно трудные подзадачи на квантовых компьютерах (универсальных или на базе квантового отжига) и объединять результаты на классическом компьютере с целью получения общего для этой задачи решения. Недавно опубликованный метод квантового локального подбора (QLS, quantum local search) [5] — один из вариантов использования такого подхода. Появлению QLS способствовал ряд успешных применений локально-поисковых эвристик для вычислительно сложных задач (таких как задача выполнимости булевых формул и задача коммивояжера), которые проблематично решить целиком напрямую за разумное время. Метод квантового локального подбора стартует со случайного начального решения, и затем на каждом шаге исследуется окрестность текущего решения на предмет нахождения решения, минимизирующего функцию потерь. Если такая окрестность невелика, то требуемый подбор может быть осуществлен на квантовом компьютере. Если найдено более подходящее решение, то текущие параметры обновляются и цикл повторяется, продолжаясь до тех пор, пока функция потерь не перестает улучшаться. Аналогичные подходы применены для решения задач оптимизации на системах на базе квантового отжига [2].

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

Квантовый локальный подбор достигает глобального оптимума на рассмотренной задаче, то есть находит оптимальную кластеризацию вершин. Существуют и другие эвристики с более быстрым временем выполнения, чем у QLS. Отрицательная особенность этого метода заключается в том, что в общем случае он склонен к «застреванию» на локальном оптимуме: если на некоторой итерации все доступные для рассмотрения окрестности слишком малы и не дают улучшения функции потерь, то алгоритм не сможет выбраться за пределы локально-оптимальной ямы.

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

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

Приложения

Рассмотрим два приложения, использующих технику решения больших задач на системах поколения NISQ: приложение по обнаружению сетевых сообществ с применением локального квантового подбора [5], реализованное на IBM Q и на системах D-Wave; и приложение по выявлению подструктуры белка имидазолглицеролфосфат-синтазы (IGPS) с использованием инструмента qbsolv на системах D-Wave.

Выявление сетевых сообществ

Данная задача состоит в объединении сходных вершин в группы, где сходство обычно выражается через количество общих и отдаленных вершин. Как правило, для вершины в выявленной группе характерны плотная связность с вершинами своей группы и разреженная связность с вершинами, находящимися вне группы. Уплотнение внутригрупповых связей и разрежение внешних используются для большого класса подходов в задаче выявления сетевых сообществ. Один из наиболее широко используемых методов — максимизация модулярности с целью разделить множество вершин заданного графа на два подмножества (сообщества) таким образом, чтобы прийти к наибольшему различию (модулярности) между количеством ребер внутри полученного сообщества и ожидаемым количеством ребер (если бы ребра были равномерно и случайно распределены между тем же количеством вершин). Иными словами, высокая, максимизированная модулярность выглядит как статистически неожидаемое распределение ребер.

Сложность выявления сетевых сообществ на системах поколения NISQ в том, что практически значимые сети слишком велики для современного оборудования, поэтому необходимо применение методов локального подбора (рис. 3). Квантовый локальный подбор начинается с некоторого начального решения, в данном случае — некоторого случайного выбора сообществ, но, вообще говоря, начальное решение можно выбирать исходя из эвристик, учитывающих приемлемое соотношение требуемого времени к ожидаемому качеству [5].

На каждом шаге квантового локального подбора исследуется окрестность решения. Для задачи выявления двух сообществ в качестве окрестностей рассматриваются варианты выбора сообществ, отличающиеся от текущего решения на небольшое количество вершин. Подмножество вершин, перемещаемых между сообществами, выбирается на основе некоторого оптимизационного критерия (в данном случае берется критерий наибольшего выигрыша от изменения [5]). Подзадача оптимизации на этом шаге формулируется с граничным условием инвариантности — сохранением выбора сообществ для оставшихся вершин, не вошедших в перемещаемое подмножество.

Ограничивая размер окрестности, то есть количество вершин в подмножестве, можно сократить количество переменных в подзадаче оптимизации до такого уровня, чтобы выполнить ее на системе поколения NISQ. При этом необходим сознательный компромисс между экономией квантовых ресурсов и полем подбора, поскольку увеличение размера окрестности улучшает сходимость алгоритма [5].

Дополнительное преимущество метода квантового локального подбора — фундаментальная независимость от аппаратного решения. Метод применим с любым квантовым компьютером, лишь бы подзадача оптимизации могла быть на нем выполнена. В задаче выявления сетевых сообществ подзадачи могут быть переданы на вычисление как на систему на базе квантового отжига, так и на квантово-вентильную машину, выполняющую квантовый алгоритм приближения для задачи оптимизации. Алгоритм квантового локального поиска способен находить оптимальные решения для подзадач с 16 переменными как на 16-кубитной системе IBM Q, так и на системе D-Wave 2000Q [5]. Мощнейший из доступных на данный момент универсальных квантовых компьютеров IBM Q20 Tokyo позволяет формировать подзадачи размером до 20 переменных.

Выявление множественных сетевых сообществ на D-Wave

Реализована k-параллельная задача выявления до k сетевых сообществ на компьютере D-Wave. Система на базе квантового отжига в большинстве случаев находит наиболее подходящие из известных решения задачи выявления множественных сетевых сообществ в случае, если графы невелики.

Практическая ценность выявления множественных сообществ состоит, например, в решении активно изучаемой биофизиками проблемы кластеризации динамически коррелированных аминокислотных остатков белка IGPS. Матрица модулярности вычисляется на основании α-углеродных попарных корреляций, получаемых путем молекулярно-динамического имитационного моделирования: 454 аминокислотных остатка белка IGPS формируют граф, веса ребер которого соответствуют данным корреляционной матрицы.

Глобальная задача квантовой неограниченной бинарной оптимизации для нахождения до k сообществ содержит k×n переменных (k — наибольшее количество выявляемых сообществ, n — число вершин) и передается на вход инструменту qbsolv. Инструмент формирует подзадачи согласно заданному ограничению — до 64 переменных. Разделение на два сообщества позволило выявить две молекулы, составляющие IGPS (рис. 4). Решение для k = 4 идентифицировало четыре области (по две на молекулу), которые, по-видимому, связаны с функциями белка (рис. 4).

Рис. 4. Выявление сетевых сообществ на графе кислотных остатков белка IGPS: а — две различные молекулы; б — четыре области (по две на молекулу)

Эти результаты служат основанием для практически значимых выводов, главный из которых состоит в том, что показана применимость квантово-классического алгоритма с использованием системы на базе квантового отжига к графовым задачам «неигрушечного» масштаба. При этом увеличение k требует задействования большего числа кубитов, что в очередной раз подтверждает потребность в гибридных квантово-классических алгоритмах.

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

***

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

Вместе с тем гибридные подходы с применением декомпозиции — отнюдь не «серебряная пуля». Они позволяют применить малые квантовые компьютеры для практических задач, но по-прежнему ограничены возможностями систем поколения NISQ. Если считать, что малые квантовые компьютеры дают квантовое превосходство, то и методы на основе декомпозиции дают эффект при решении больших задач оптимизации с небольшими накладными расходами. С другой стороны, если нет квантового превосходства на компьютерах поколения NISQ, то и методы декомпозиции его не создадут. Эти же соображения применимы и к другим гибридным алгоритмам: если квантовая часть квантово-классического алгоритма не дает ускорения на системе поколения NISQ, то и гибридизация сама по себе его не покажет.

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

Литература

1. J. Biamonte et al. Quantum machine learning // Nature. — 2017. — Vol. 549, N. 7671. — P. 195.

2. Z. Bian, F. Chudak, R. B. Israel, B. Lackey, W. G. Macready, A. Roy. Mapping constrained optimization problems to quantum annealing with application to fault diagnosis // Frontiers ICT. — 2016. — Vol. 3. — P. 14. DOI:10.3389/fict.2016.00014.

3. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, H. Neven. Barren plateaus in quantum neural network training landscapes // Nature Commun. — 2018. — Vol. 9 (Nov. 2018). URL: https://arxiv.org/abs/1803.11173 (дата обращения: 29.08.2019)

4. J. R. McClean, J. Romero, R. Babbush, A. Aspuru-Guzik. The theory of variational hybrid quantum-classic algorithms // New J. Phys.— 2016. — Vol. 18, N. 2. — P. 023023.

5. R. Shaydulin, H. Ushijima-Mwesigwa, I. Safro, S. Mniszewski, Y. Alexeev. Network community detection on small quantum computers. URL: https://arxiv.org/abs/1810.12484 (дата обращения: 29.08.2019).

Руслан Шайдулин (rshaydu@g.clemson.edu) — аспирант Клемсонского университета; Хаято Усидзима-Мвесигва (hushiji@g.clemson.edu) — научный сотрудник Fujistu Laboratories (США); Кристиан Негре (cnegre@lanl.gov), Сьюзен Мнишевски (smm@lanl.gov) — сотрудники Лос-Аламосской национальной лаборатории; Илья Сафро (isafro@g.clemson.edu) — доцент информатики Школы здравоохранения Клемсонского университета; Юрий Алексеев (yuri@anl.gov) — ведущий специалист Аргоннской национальной лаборатории.

Ruslan Shaydulin, Hayato Ushijima-Mwesigwa, Christian F. A. Negre, Ilya Safro, Susan M. Mniszewski, Yuri Alexeev, A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers. IEEE Computer, June 2019, IEEE Computer Society. All rights reserved. Reprinted with permission.