Квантовую магию в жизнь06.02.2017 19:07

Адиабатический компьютер компании D-Wave

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

Что же такое адиабатический алгоритм?

Известно, что полноценных квантовых компьютеров, оперирующих регистрами с запутанными кубитами, пока не существует. Есть только экспериментальные установки, которые могут что-то делать со считанным числом кубитов. Например говорят, что еще в 2001 IBM сумела разложить число 15 на два простых сомножителя с помощью алгоритма Шора, используя 7 кубитов. Но я не встречал информации о том, что еще какие-то числа поддались этому устройству. Может быть плохо искал, но, как мне представляется, правильней называть его не компьютером, а уникальным, физическим экспериментом.

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

Примерами такого компьютера являются изделия D-Wave. Известно, что процессоры с регистрами из 128, 512, 1024 и даже 2048 кубитов, которые D-Wave эффектно презентует, не образуют запутанных состояний. Хотя группы по 8 кубитов (кубайты), как утверждается, запутаны внутри себя и есть еще запутанность между отдельными (немногими) кубитами. О черном ящике, которым в буквальном смысле является компьютер D-Wave, известно мало.

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

Что же такое адиабатический алгоритм? Попробую объяснить это на примере, который я придумал сам. Может быть алгоритмы в D-Wave работают совсем не так. Но я не могу себе представить, как иначе употребить процесс перераспределения энергии в системе кубитов. Судите сами, насколько это выглядит правдоподобно. Во всяком случае, как оптимизационный алгоритм должно быть небезинтересным. Технически вполне осуществимо!

В этой связи термин «кубит» не вполне годится, т.к. желательно иметь больше состояний. Есть подходящее слово «кудит». В принципе это — тот же кубит, только имеет не 2, а произвольное число $d$ базовых состояний. В случае с кубитом ( $d=2$ ) адиабатически считать тоже можно, но все же предположим, что D-Wave использует кудиты при каком-то $d\geq 2$ . И пойдем еще дальше, утверждая, что суперпозиции базовых состояний в данном случае не нужны. Для реализации адиабатического алгоритма достаточно иметь элементы данных, каждый из которых может находиться в одном из $d$ энергетических (стационарных) состояний и переходить из одного в другое при взаимодействиях с достаточно близкими к нему элементами («кубайты» у D-Wave?). Регистр состоит из $n$ таких «кудитов» (так и будем называть их в дальнейшем).

Пусть нужно найти максимум функции $z_1+z_2+\ldots+z_n$ при условиях

$\sum_{j=1}^n m_j\cdot z_j=K\qquad z_j\geq 0\qquad z_j\in{\mathbb Z}$

Коэффициенты $m_j$ и $K$ являются целыми, неотрицательными числами. Нужно найти (целочисленное) решение этой оптимизационной задачи. Ниже дан пример того, как она может возникать.

Преобразуем ее, введя новые переменные $x_j=z_j/M$ , где $M=НОК(m_1, m_2, \ldots, m_n)$ . Обозначая $Q=K/M$ получаем эквивалентную задачу: найти максимум $x_1+x_2+\ldots+x_n$ при условиях

$\sum_{j=1}^n m_j\cdot x_j=Q\qquad x_j\geq 0\qquad\qquad(1)$

Предполагаем, что уровни энергии являются равноотстоящими на $\Delta E$ . Для запуска алгоритма следует для всех $j$ установить кудит номер $j$ в состояние с энергией $m_j\Delta E$ , т.е., перебросить его на $m_j$ — й энергетический уровень (начиная с нулевого).

Пусть текущее значение переменной $x_j$ определяется из уравнения $E_j=m_j\Delta E\cdot x_j$ , где $E_j$ — энергия $j$ — го кудита. Тогда все начальные значения $x_j=1$ . В процессе перераспределения энергии между кудитами значения $E_j$ меняются, что эмулирует изменения величин $x_j=E_j/(m_j\Delta E)$ .

Теперь предоставим регистру возможность самостоятельно прийти в состояние термодинамического равновесия. В процессе этого кудиты с большей энергией будут передавать ее близким к ним кудитам с меньшей энергией порциями кратными $\Delta E$ . Рассмотрим парное взаимодействие, когда энергия $k\Delta E$ переходит от элемента с энергией $E_p$ к элементу с энергией $E_q$ . Тогда новые значения переменных $x_p$ и $x_q$ даются выражениями:

$x_p'=x_p-\frac{k}{m_p}\qquad x_q'=x_q+\frac{k}{m_q}\qquad\qquad(2)$

Очевидно, что для таких «транзакций» в большинстве случаев $m_p>m_q$» />, т.е., начальная энергия <img src= — го кудита больше, чем $q$ — го. Тогда из (2) следует, что $x_p'+x_q'>x_p+x_q$» />, т.е., значение целевой функции увеличилось от <img src= до $\sum_j x'_j$ . При этом $z'_p=Mx'_p=M\left(x_p-\frac{k}{m_p}\right)=z_p-k\frac{M}{m_p}$ является целым, если целым было $z_p$ .

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

$\sum_{j=1}^n m_j\cdot x_j'\cdot\Delta E=\sum_{j=1}^n E'_j=\sum_{j=1}^n E_j=\sum_{j=1}^n m_j\cdot x_j\cdot\Delta E=Q\Delta E$

откуда видно, что новые значения $x'_j$ удовлетворяют ограничению (1).

После того, как в системе установится термодинамическое равновесие (это произойдет очень быстро), останется cчитать значения энергии кудитов $E_j$ , поделить их на $m_j\Delta E$ и умножить на $M$ . Получится решение исходной задачи $z_1,z_2,\ldots,z_n$ . Заметим, что на каждом шаге алгоритма числа $z_j=Mx_j$ являются целыми, т.е., решается именно задача целочисленной оптимизации. Заметим также, что полученное решение будет локально оптимальным, но, возможно, на практике это нас устроит.

Реальным примером рассмотренной задачи служит следующая (придумана навскидку). Пусть требуется обслужить наибольшее число клиентов в $n$ пунктах, в каждый из которых следует пригласить $z_j$ человек. При этом компания располагает денежной суммой $K$ , которая должна быть потрачена на эту операцию согласно бюджету, а расходы на обслуживание одного клиента в пункте $j$ равны $m_j$ .

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

Квантовый радар из Поднебесной

Окончание следует