Квантовые симуляторы научили искать самые плотные области графов

Канадские физики теоретически показали, что бозонные семплеры можно использовать для поиска наиболее плотных подграфов, а затем проверили предложенный способ с помощью численного моделирования. Как и ожидалось, бозонные семплеры — квантовые компьютеры, которые работают с распределениями вероятности фотонов, — работают в несколько раз быстрее, чем классические алгоритмы. Статья опубликована в Physical Review Letters, препринт работы выложен на сайте arXiv.org.

Считается, что в скором времени квантовые компьютеры достигнут квантового превосходства — позволят моделировать системы, которые невозможно обсчитать с помощью обычного, классического компьютера. В идеале квантовый компьютер должен быть универсальным, то есть способным смоделировать любую систему и реализовать любой алгоритм. Как бы то ни было, существующие универсальные квантовые компьютеры страдают от высокой частоты ошибок и имеют сильно ограниченные возможности. Поэтому физики параллельно работают над «специальными» (неуниверсальными) квантовыми вычислителями, которые призваны моделировать один конкретный алгоритм или систему, например, цепочку частиц с ненулевыми спинами. В частности, 51-кубитный компьютер группы Лукина или 53-кубитный компьютер группы Кристофера Монро заточены именно под эту задачу. Другим широко известным примером неуниверсального квантового вычислителя является компьютер D-wave, который умеет обсчитывать алгоритм квантового отжига (и больше ничего). Можно сказать, что такие компьютеры уже достигли квантового превосходства, поскольку смоделировать их на классическом компьютере нельзя. К сожалению, в большинстве случаев неуниверсальные квантовые компьютеры призваны решать довольно специфические задачи, которые сложно адаптировать под полезные на практике нужды (хотя в некоторых случаях это удается сделать). Получается, что от узкоспециализированного квантового превосходства не так уж много пользы.

Физики Хуан Мигель Арразола (Juan Miguel Arrazola) и Томас Брумли (Thomas Bromley) сосредоточились в своей работе на менее специфической задаче, которая, на первый взгляд, довольно слабо связана с физикой, — задаче поиска наиболее плотного подграфа (задача DkS, densest k-subgraph). Заключается эта задача в следующем. Предположим, что у нас есть некоторый граф, который содержит n вершин, связанных между собой ребрами, — например, картина связей в социальной сети. Для простоты будем считать, что граф неориентированный, то есть все связи в нем двусторонние. Как выделить из этого графа подграф размера k < n с наибольшей плотностью? Плотным называется граф, число связей в котором близко к максимальному — в таком графе практически все точки связаны друг с другом. Например, плотными подграфами в социальной сети будут группы одноклассников или другие группы близких друзей, в которых все друг друга знают. Следовательно, наиболее плотный подграф, содержащий k вершин, — это подграф с наибольшим числом ребер. Задача поиска наиболее плотного подграфа встречается во всех областях, в которых требуется искать корреляции между наборами данных — в частности, в Data mining, биоинформатике или работе с финансами. Задача DkS является NP-трудной, то есть проверка, что ответ на нее является верным, потребует по меньшей мере полиномиальное время от входных данных.

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

Чтобы показать, что бозонные семплеры можно применять для решения задачи DkS, ученые приводят следующую цепочку рассуждений. Во-первых, каждому графу можно сопоставить некоторую оптическую сеть. Во-вторых, вероятность получить некоторое распределение фотонов на выходе, которое отвечает определенному подграфу в исходном графе, пропорциональна хафниану (Hafnian) этого подграфа, то есть числу его совершенных паросочетаний. В третьих, число совершенных паросочетаний графа приближенно связано с числом его ребер — этот результат ученые дополнительно проверили с помощью прямых вычислений. Таким образом, вероятность конфигураций, отвечающих наиболее плотным подграфам, оказывается повышенной по сравнению с другими подграфами — чем плотнее подграф, тем больше его хафниан и тем больше вероятность появления соответствующей ему конфигурации. Например, хафниан графа, в котором все вершины соединены между собой, равен (k−1)!!, а хафнианы графов, в которых содержится всего несколько ребер, блики к нулю. Это позволяет разработать алгоритм, который будет решать задачу DkS путем имитации отжига, то есть постепенного «оседать» в наиболее энергетически выгодной (наиболее вероятной) комбинации. Более того, можно поступить еще хитрее и модифицировать классические алгоритмы поиска наиболее плотного подграфа, которые выбирают подграфы не случайно (как в алгоритме имитации отжига), а на основании некоторых параметров. В этом случае использование бозонного семплера дополняет алгоритм, не давая ему «застрять» в локальных минимумах.

В качестве примера ученые рассмотрели задачу поиска наиболее плотного подграфа из 10 вершин в конкретном графе из 30 вершин (оба графа изображены на рисунке снизу, число ребер в максимальном подграфе равно 42), и сравнили на ней работу классических алгоритмов и алгоритмов с использованием бозонного семплера. Бозонный семплер, работающий с десятью запутанными фотонами, ученые моделировали с помощью классического компьютера. Как и ожидалось, бозонные семплеры находили плотные подграфы гораздо быстрее, чем классические компьютеры. Например, классический алгоритм имитации отжига обнаружил подграф с 34 вершинами после перебора 400 образцов, а бозонный семплер оказался в два раза быстрее. Алгоритм поиска, дополненный семплером, достиг того же уровня за 600 образцов, тогда как классический алгоритм поиска вообще не мог добраться до таких значений. Таким образом, ученые заключают, что использование бозонных семплеров для решения задачи DkS вполне оправдано на практике.

За последние несколько лет скорость генерации и число одновременно запутанных фотонов в бозонных семплерах — а вместе с ними и сложность вычислений — заметно выросли. Так, в ноябре 2016 года скорость генерации достигала 11 фотонов в час, а число одновременно запутанных фотонов равнялось десяти. В мае 2017 году физикам удалось повысить число одновременно запутанных фотонов до 14, сохраняя ту же скорость генерации, и обогнать по вычислительной мощности первый компьютер, созданный человеком, — ENIAC. А в июне 2018 года ученые придумали способ, который существенно ускоряет (на несколько порядков) вычисления бозонных семплеров, используя процессы с потерями. Теоретически, этот способ позволяет без особых трудностей довести число фотонов, которыми оперирует семплер, до пятидесяти. Напомним, что бозонный семплер, рассмотренный в новой статье, работает всего с десятью фотонами.

Дмитрий Трунин