Привет, Хабр! На связи снова Михаил Ремнев, аналитик Cloud.ru и ученый-физик. В этой статье я собираюсь немного поспорить с популярным тезисом о том, что универсальные квантовые компьютеры нужны для высоких материй типа квантовой химии, факторизации чисел и искусственного интеллекта, а квантовые симуляторы (в частности — отжигатели типа D-Wave) годятся лишь для задач оптимизации и логистики.

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

Микроволновка против шеф-повара

В предыдущей статье была ссылка на рекорд в разложении числа на множители. Квантовый компьютер разложил на множители число 35 при помощи алгоритма Шора. С тех пор появились новые исследования, где смогли факторизировать число 253 при помощи вариационного алгоритма. Более того, в этой работе приведен список предыдущих достижений, в которых раскладываются на множители еще большие числа. Подвох в том, что все эти достижения сделаны при помощи классических вычислений, которые проводят часть поиска. Мы же рассматриваем полностью квантовые алгоритмы. А теперь шьямалановский «вот это поворот»: это максимум для универсального квантового компьютера, а вот на квантовом симуляторе (квантовом отжигателе D-Wave) разложили на множители большее число — 8 219 999.

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

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

Квантовые симуляторы имитируют при помощи одной квантовой системы другую. Квантовый отжигатель D-Wave имитирует систему, описываемую моделью Изинга. Это математическая модель, которая описывает взаимодействие магнитных спинов. Каждый спин может быть направлен «вверх» (+1) или «вниз» (-1) и влиять тем самым на соседний: соседи могут «дружить» (стремиться к одинаковому направлению) или «враждовать» (стремиться к разным направлениям). Энергия системы зависит от этих взаимодействий и описывается следующей формулой:

Любую задачу поиска оптимального решения можно примерно переписать в виде: «Найди такие значения спинов, чтобы энергия системы была минимальной». Этим и занимается отжигатель: он перекодирует задачу в свою систему, где каждый кубит приравнивается к спину (σ_i), а связи между кубитами к — взаимодействиям (J_ij). Далее запускается отжиг: спины начинают в случайных состояниях, но постепенно «охлаждаются», находя конфигурацию с минимальной энергией. Работает это примерно как потрясти коробку с кучей магнитов: конфигурация, которая получится в итоге, и есть самая энергетически выгодная. 

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

Получается, если универсальный квантовый вычислитель — это шеф-повар, то квантовый отжигатель типа D-Wave — это своего рода микроволновка: выполняет только одну функцию (разогревать), но делает это чертовски хорошо и быстро. Но разве может микроволновка сотворить шедевр? Смотря что в нее положить. 

QUBO: учимся говорить с отжигателем на его языке

Существует такая штука как QUBO (Quadratic unconstrained binary optimization —  квадратичная неограниченная бинарная оптимизация) это такой класс задач, где нужно найти комбинацию бинарных переменных (0 или 1), которая минимизирует или максимизирует квадратичную функцию. А поскольку модель Изинга как раз описывает минимизацию энергии системы, мы можем «поженить» эти две концепции и «скормить» квантовому отжигателю задачу в QUBO-формулировке, предварительно заменив переменные.

Итак, чтобы решить задачу квадратичной неограниченной бинарной оптимизации, нужно задать матрицу Q и найти бинарный вектор x, который удовлетворяет минимальному значению функции:

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

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

Пусть нам дано число N, которое нужно разложить на простые числа p и q. Запишем следующее уравнение:

.

Формулировка QUBO не подразумевает равенства, она только минимизирует функцию. Поэтому перепишем произведение в функцию: , минимум которой будет соответствовать равенству . Наша задача свести полученную функцию к QUBO-матрице. Тогда ее можно будет свести к модели Изинга и решить на квантовом отжигателе. 

Оптимизатору необходимо подобрать p и q. Запишем неизвестные величины p и q через бинарные переменные x_i в двоичном коде:  

и .

Здесь в младшем регистре стоят единицы, поскольку простые числа всегда нечетные. Величины n и k равны логарифмам по основании 2: и , округленные до целого вверх.

Таким образом, целевая функция будет зависеть от n+k бинарных переменных:

.

Раскрываем скобки, возводим в квадрат и видим, что в сумму входят слагаемые более второго порядка, вида и , что никак не согласуется с приведенной ранее квадратичной формой в QUBO-формулировке.

В работе Quantum Annealing for Prime Factorization разработаны два метода преодоления этой трудности. Рассмотрим первый из них, так называемый прямой метод. Он более громоздкий, но и более простой для понимания. Наша задача — превратить выражение, состоящее из трех множителей, в слагаемые, состоящие из двух множителей (квадратичную форму). Делается это за счет ввода дополнительных переменных и за счет того, что переменные x могут принимать значения только 0 и 1.

Из псевдобулевой оптимизации нам даны выражения для бинарных переменных x,y,z ∈{0;1} xy = z если xy-2xz-2yz+3z = 0 и xy≠z если xy-2xz-2yz+3z > 0. Т.е. неравенство выступает в роли штрафной функции: если xy≠z, то оно добавляет свой вклад. Тогда мы можем в выражении заменить на дополнительную переменную и добавить к равенству штрафную функцию, которая будет давать свой вклад, если равенство не выполняется:

, если ,

, если .

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

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

Затем необходимо составить матрицу Q, элементами которой будут численные коэффициенты квадратичной формы.

Пример разложения на множители

Проиллюстрируем разложение числа на множители для случая N = 15. Определим и . Выражение для оптимизационной функции тогда примет следующий вид:

.

Раскроем скобки и возведем в квадрат. Также воспользуемся тем, что x могут принимать значения только 0 и 1, т.е. . Мы получим следующее выражение:

.

Как видно, здесь только одно слагаемое с тремя множителями. Сделаем замену . Тогда получим следующее выражение с еще одной переменной x4:

.

Константу можно смело откидывать, так как она не влияет на минимизацию, и записать матрицу QUBO: коэффициенты слагаемых будут соответствовать элементам матрицы с индексами, равными индексам бинарных переменных:

.

Итак, мы получили QUBO-матрицу, теперь ее можно преобразовать в коэффициенты модели Изинга и передать квантовому компьютеру. 

Если у вас в тумбочке не завалялся квантовый вычислитель, не огорчайтесь: всегда можно воспользоваться его симулятором (не путать с квантовым симулятором D-Wave, в данном случае это просто программа), выложенным в открытый доступ на github. Если всегда мечтали заиметь что-то квантовое, — вот он ваш шанс! Для этого нам потребуется python с установленным симулятором. Его можно установить из консоли: 

pip install dwave-samplers

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

принимает наименьшее значение. Мы будем использовать решатель с алгоритмом Simulated Annealing (имитации отжига).

Итак, загружаем соответствующий модуль:

from dwave.samplers import SimulatedAnnealingSampler

Вводим руками полученную матрицу:

Q = [[-52, 200, -48, -512],
 	[0,-52,16,-512],
 	[0,0,-96,128],
 	[0,0,0,768]]

Загружаем решатель и запускаем его:

sampler = SimulatedAnnealingSampler()
sample_set = sampler.sample_qubo(Q, num_reads = 10, num_sweeps = 10**3)

Извлекаем полученное решение в виде списка:

sol = sample_set.first[0]
list(sol.values())

В итоге получим следующий список:

[1, 0, 1, 0]

Это означает, что , , , . Теперь вспоминаем, что , и . Получается, что p=3 и q=5.  Все сходится.

Мы рассмотрели крошечный пример, разложили на множители число 15. Квантовый отжигатель D-Wave раскладывает гораздо большие числа. Для факторизации требуется серьезная подготовительная работа. В общем виде в функцию f входят слагаемые третьей и четвертой степени по x. Например, слагаемых четвертой степени, т.е. тех, куда входят слагаемые вида , будет порядка . В каждом таком слагаемом необходимо сделать две замены для понижения степени, что усложняет выражение и добавляет по две переменных. Вручную на листе бумаги это делать слишком долго, поэтому процесс лучше автоматизировать при помощи библиотеки sympy. Чтобы расписать, как это сделать, нужно написать еще одну статью на Хабр. Если есть необходимость в статье о том, как автоматизировать работу с формулами при помощи sympy, дайте знать в комментариях.

От вычислений к прикладным вопросам

Авторы статьи Quantum Annealing for Prime Factorization приводят оценку количества кубитов, необходимых для факторизации числа N. Оно растет как . Для сравнения факторизация числа N при помощи алгоритма Шора . Как видно, факторизация числа на квантовом отжигателе требует квадратично большее число кубитов, чем алгоритм Шора для универсального квантового компьютера. 

Здесь у внимательного читателя возникнет вопрос: «Подождите, но мы же знаем, что у современных квантовых компьютеров с кубитами все так плохо, что алгоритмом Шора удалось разложить только число 35. Как же так вышло, что для факторизации требуется больше кубитов, а разложить все равно удалось большее число?!». А дело опять в идеальности кубитов: если бы они были идеальными, то масштабирование было бы , но мы имеем дело с физическими кубитами. Для небольших чисел это работает, но точность падает с ростом размера задачи, поэтому масштабировать квантовый отжиг, например, для того, чтобы взломать алгоритм шифрования RSA, не получится, ведь это ≈ 600-значное число. Однако, 7-значное число — это мелочь, с которой такой фокус прокатывает. А значит, пока мы можем попрактиковаться «в песочнице», а когда квантовые вычисления станут достаточно сильны для решения прикладных задач, мы сможем сделать капельку счастливее:

• Дата-сайентистов. Когда есть нужда в кластеризации данных или подборе гиперпараметров.

• ИБ-шников. Например, когда нужно придумать, как лучше распределить ресурсы защиты или найти лучшие патчи для системы.

• Логистов. Если надо решить задачу коммивояжера, оптимальным образом распределить курьеров для доставки груза или продумать расписание транспорта.

• Финансистов. Если нужно минимизировать риски при заданной доходности или выстроить выгодные цепочки сделок.

…а еще инженеров, генетиков, биоинформатиков. Главное придумать, как записать свою задачу в QUBO-формате. 

Кстати, научиться этому можно на курсе «Основы работы с квантовым симулятором Cloud.ru». Там же можно потренироваться в решении задач о разрезе графа и упаковке рюкзака. И да, курс писал я с коллегами, и он бесплатный. Выполнять упражнения можно на все в том же бесплатном сэмплере с github, а если вдруг захочется своего родного — у нас есть свой квантовый симулятор дома. Опять же не путать наш квантовый симулятор, который является программным обеспечением, с квантовым симулятором D-Wave, в котором одна квантовая система имитирует другую.