Квантовые вычисления на практике: конкурс от РКЦ и Росатома

Заметка посвящена описанию прошедшего 23-24 октября в России первого открытого конкурса по применению вычислений на квантовых компьютерах для решения практических задач. Дано краткое описание принципов работы квантовых компьютеров и решения с их помощью проблем комбинаторной оптимизации. Приведено задание, представленное на конкурсе, а также решение, выполненное командой GRAPHOMETRICA, в которой участвовал магистр кафедры физики твердого тела Синченко Семён, занявшее 2-е место. Конкурс проводился в рамках президентской программы «Россия — страна возможностей» при поддержке госкорпорации «Росатом» и Российского квантового центра (РКЦ) на федеральной платформе «Цифровой прорыв-2021» (https://leadersofdigital.ru)

О постановке задачи

В рамках конкурса было предложено решение одной из NP-трудных задач комбинаторной оптимизации. К этому классу относятся задачи, для которых не существует эффективных алгоритмов, а решение возможно только лишь перебором вариантов. Сложность перебора растет экспоненциально с ростом размерности задачи и численное решение на классическом компьютере очень быстро становится невозможным. Непосредственно сами задания предоставил «Росатом» совместно с Российским квантовым центром, а участникам конкурса в течении 48 часов предлагалось по выбору решить одну из них. Выполнение первого задания заключалось в решении на квантовом компьютере задачи об оптимальном маршруте: были даны пять станций метро, на которых расположены достопримечательности города, и надо было найти кратчайший маршрут, чтобы объехать их все и вернуться в точку отправления (слайд 1).

Слайд 1. Схема станций метро с достопримечательностями и время в пути

Может показаться, что такую задачу можно решить без компьютера вовсе, но на самом деле сложность этой задачи растет как факториал от числа точек маршрута. Поэтому если для 5-и станций компьютер и правда не нужен, то для 30-и станций это уже почти невозможно — ведь надо будет перебрать порядка 265 тысяч миллиардов миллиардов миллиардов (2.65 х) возможных путей объезда станций. Это известная «задача коммивояжера» (Travelling salesman problem), и она относится к классу описанных ранее NP-трудных задачам оптимизации, которые невозможно эффективно решить на обычном компьютере.

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

О квантовых аннилерах

Квантовые аннилеры (от англ. anneal — отжигать) — это специальная разновидность квантовых компьютеров, созданная как раз для решения NP-трудных оптимизационных задач. Принцип работы квантовых аннилеров основывается на широко известной теореме квантовой механики — адиабатической теореме, которая впервые была сформулирована М. Борном и В. Фоком ещё в 1928 г. Данная теорема говорит нам о том, что физическая система остаётся в своём мгновенном собственном состоянии, если возмущение (например, внешнее поле) действует достаточно медленно. Другими словами, если система в начале была в собственном состоянии гамильтониана, она окажется в соответствующем собственном состоянии конечного гамильтониана. Квантово-механическая система, которая находится внутри квантового аннилера представляет собой систему кубитов, каждый из которых является двухуровневой системой. Система аннилера описывается гамильтонианом из двух частей. Первая часть — это так называемый «начальный» гамильтониан, который соответствует системе, для которой собственное состояние очень легко получить из-за особенностей энергетических конфигураций. Обычно это так называемый tunneling hamiltonian, собственное состояние которого представляет суперпозицию всех кубитов. Вторая часть — это как раз «модельный» гамильтониан, к которому сведена исходная комбинаторная задача. Обе части входят с коэффициентами, которые меняются в процессе отжига. Ниже на слайде приведен график, на котором синем цветом изображена динамика коэффициента начального гамильтониана, а красным — модельного (слайд 2).

Слайд 2. Иллюстрация квантового отжига. Источник — сайт компании D-Wave[1].

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

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

Решение команды GRAPHOMETRICA

Магистр кафедры физики твердого тела С.А. Синченко принимал участие в конкурсе в составе команды GRAPHOMETRICA, занявшей по итогам конкурса 2-е место среди 24 команд. Решив первую задачу об оптимальном маршруте в метро, они приступили к реализации второй, не менее сложной и интересной задачи. Для начала была выбрана тематика будущего сервиса. Это был концепт полноценного туристического навигатора, «под капотом» у которого был бы квантовый аннилер. За 48 часов команде удалось создать полноценный сайт (технологии — JavaScript, TypeScript, React), в который была интегрирована карта метро (слайд 3). Нажав на любую станцию, пользователь мог видеть фотографии достопримечательностей, расположенных вокруг этой станции. Фотографии брались из открытых источников. Пользователь мог выбрать те места, которые хотел посетить, после чего нажимал кнопку «рассчитать маршрут». Backend для этого сайта (технологии — Java, SpringBoot, JGraphT, PostgreSQL, Docker) отвечал за конвертацию станций метро в оптимизационную задачу коммивояжера и передачу этой задачи в очередь задач (очередь на базе Apache Active MQ). Асинхронное взаимодействие с квантовым компьютером через очередь задач — это важный аспект решения, поскольку в силу своей природы квантовый компьютер может выполнять одномоментно лишь одну операцию, то есть принципиально он однопоточный. Поэтому задачи от пользователей складывались в очередь и последовательно выполнялись. Взаимодействие с квантовым компьютером было выполнено как отдельный сервис (Python, NumPy, Docker), который по получению ответа конвертировал его из последовательности спинов, характеризующих конфигурацию основного состояния квантово-механической системы в цикл на графе и отправлял обратно в очередь сообщений. Далее Backend обрабатывал полученное сообщение, после чего оно возвращалось пользователю.

Слайд 3. Архитектура решения

Команде удалось все это отладить и интегрировать, развернув в облачном сервисе Microsoft Azure. Весь сервис был построен исключительно с использованием приложений и технологий на базе открытого исходного кода. Никакие коммерческие программы (кроме аренды облачных мощностей) не использовались. Программный код всех частей решения команды выложен в открытом доступе на GitHub по QR-коду ниже. За второе место команда получила денежный приз и именные сертификаты.

Бажанов Д.И., кафедра физики твердого тела

[1] Johnson, M., Amin, M., Gildert, S. et al.,«Quantum annealing with manufactured spins.» // Nature 473, 194–198 (2011); https://docs.dwavesys.com/docs/latest/doc_getting_started.html

[2] A. Lucas, «Ising formulations of many NP problems.» // Frontiers in Physics 2, 5 (2014).

[3] Leeuwen, Jan van. «Handbook Of Theoretical Computer Science Volume B Formal Models And Semantics.» (1990).

Примечание Главного редактора:

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