Алгоритм Дойча#

Автор(ы):

Ширкин Сергей

Алгоритм Дойча (в английском варианте – Deutsch’s algorithm) – это один из первых алгоритмов, показавших, что квантовый компьютер может решать задачи особым способом, отличающимся как от алгоритмов классического компьютера, так и от интуиции и здравого смысла человека. При этом такое решение может занимать меньшее количество шагов.

Нужно прежде всего сказать, что алгоритм Дойча не имеет практического применения в силу своей предельной простоты, зато является простейшим примером, с помощью которого можно понять, в чем состоит отличие квантовых алгоритмов от классических. Данный алгоритм был предложен в 1985 году, когда квантовых компьютеров еще не было, а практически он был реализован в 1998 году на 2-кубитном квантовом компьютере, работавшем на принципах ядерно-магнитного резонанса.

Дэвид Дойч

Помимо занятий теоретической физикой в Оксфордском университете, Дэвид Дойч – автор книг “Структура реальности” и “Начало бесконечности”, в которых он популярно излагает идеи квантовых вычислений с точки зрения многомировой интерпретеции (сторонником которой является) и философствует о будущем науки и человечества. Так что можно сказать, что работа алгоритма, согласно замыслу создателя, производится в параллельных вселенных. Так это или нет, пока проверить невозможно, но вычисления работают, и это главное.

Итак, в чем состоит задача, которую решает алгоритм? Представьте, что у вас есть функция, которая представляет собой “черный ящик”, принимающий на вход число из множества ${0, 1}$ . Функция неким образом обрабатывает входное значение и возвращает число из этого же множества, то есть либо $0$ , либо $1$ . Нам известно, что эта функция принадлежит либо к классу сбалансированных функций, либо к классу константных функций (которые мы также можем называть несбалансированными). Задача алгоритма – установить, к какому классу принадлежит функция.

Рассмотрим все варианты этих двух классов. Всего их четыре, то есть по две функции в каждом классе. Начнем с несбалансированных:

$f_{1} (x) = 0$

Это функция, всегда возвращающая $0$ , независимо от входного значения. Для нее справедливы выражения:

f_{1} (0) = 0

f_{1} (1) = 0

$f_{2} (x) = 1$

Такая функция всегда возвращает $1$ , то есть верно следующее:

f_{2} (0) = 1

f_{2} (1) = 1

Ну а теперь посмотрим на сбалансированные функции. Для них характерно то, что они могут возвращать как $0$ , так и $1$ . В этом и заключается “баланс”.

$f_{3} (x) = x$

Это тождественная функция, которая ничего не делает с входным значением. Для нее справедливо следующее:

f_{3} (0) = 0

f_{3} (1) = 1

$f_{4} (x) = \overset{―}{x}$

А вот эта функция инвертирует входное значение, то есть возвращает не то число, которое было подано на вход, а другое:

f_{4} (0) = 1

f_{4} (1) = 0

Классический компьютер справляется с задачей за два шага. Например, нам дана некоторая функция-“черный ящик”, и мы должны установить, сбалансирована ли она. На первом шаге мы отправляем в функцию входное значение $0$ . Допустим, мы получили на выходе также $0$ . Мы можем сказать, что данная функция – либо $f_{1}$ (константная функция, всегда возвращающая $0$ ), либо $f_{3}$ (сбалансированная функция, не меняющая входное значение). Для окончательного решения мы должны сделать еще один шаг – отправить в функцию значение $1$ . Если при этом мы получим опять $0$ , то это функция $f_{1}$ , а если получили на выходе $1$ , то искомая функция – $f_{3}$ .

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

Для начала рассмотрим простейшую схему, с помощью которой можно отправлять число на вход и получать ответ от черного ящика:

../../../_images/scheme_1.png — Fig. 29 Схема 1#

$U_{f}$ на данной схеме – это неизвестная функция (ее также часто называют “оракул”), являющаяся унитарным оператором. Обратите внимание, что в квантовой схеме используются два кубита. Это нужно для того, чтобы информация, с которой работает квантовый компьютер, не стиралась. В квантовом компьютере важно, чтобы все действия с кубитами (кроме операции измерения) были обратимыми, а для этого информация должна сохраняться. В верхнем кубите будет записано входное значение, а в нижнем – выходное значение функции. Таким образом, входное значение не будет перезаписано значением, которое вернет функция.

Но нам важно будет не только сохранить значение $| x ⟩$ , но также и не разрушить $| y ⟩$ . Так как кубит $y$ очевидно имеет некоторое изначальное значение, мы не можем его просто перезаписать тем числом, которое выдаст функция $f (x)$ . Здесь на помощь приходит операция исключающее ИЛИ - $X O R$ (также ее можно называть сложением по модулю 2), обозначенная на схеме как $\oplus$ . В процессе работы черный ящик $U_{f}$ не только находит значение $f (x)$ , но и применяет исключающее ИЛИ к значениям $y$ и $f (x)$ .

Операции $X O R$ соответствует такая таблица истинности:

a	b	a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

Операция $X O R$ хороша для нас тем, что она не разрушает значение $| y ⟩$ , так как является обратимой. Убедиться в этом можно, проверив тождество:

(a \oplus b) \oplus b = a

Схема 1 пока что не дает преимущества по сравнению с классическим компьютером, но мы можем ее немного усовершенствовать:

../../../_images/scheme_2.png — Fig. 30 Схема 2#

В новой схеме оба кубита вначале будут находиться в состоянии $| 0 ⟩$ . Затем мы применим к верхнему кубиту оператор Адамара, а к нижнему – гейт $X$ , а затем так же, как и к верхнему, оператор Адамара. Тем самым мы приведем оба кубита в состояние суперпозиции перед тем, как они попадут на вход функции $U_{f}$ . Верхний кубит будет находиться в такой суперпозиции:

| x ⟩ = \frac{1}{\sqrt{2}} | 0 ⟩ + \frac{1}{\sqrt{2}} | 1 ⟩,

а нижний - в такой:

| y ⟩ = \frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩ .

Если рассмотреть это как систему $| ψ ⟩$ , состоящую из двух кубитов, то она будет выглядеть так:

| ψ ⟩ = \frac{1}{2} (| 0 ⟩ + | 1 ⟩) (| 0 ⟩ - | 1 ⟩)

Сразу после $U_{f}$ система будет находиться в состоянии:

| ψ ⟩ = \frac{1}{2} (| 0 ⟩ + | 1 ⟩) (| 0 \oplus f (x) ⟩ - | 1 \oplus f (x) ⟩)

После того, как $U_{f}$ отрабатывает, нижний кубит, как это ни странно, уже нас не интересует, так что к нему операции больше не применяются, и его измерение также не производится.

Дело в том, что ответ на вопрос о том, сбалансирована функция $f (x)$ или нет, будет нами получен из верхнего кубита после того, как на него подействует оператор Адамара и будет произведено измерение. В том случае, если функция сбалансирована, результат измерения верхнего кубита будет равен $1$ , а если несбалансированна – $0$ .

Разберемся подробнее, почему это происходит. Рассмотрим все возможные $f (x)$ , которые могут находиться в черном ящике:

$f (x) = f_{1}$

В этом случае $f (x)$ всегда принимает значение $0$ , и система кубитов будет выглядеть так:

| ψ ⟩ = \frac{1}{2} (| 0 ⟩ + | 1 ⟩) (| 0 ⟩ - | 1 ⟩) = \frac{1}{2} (| 00 ⟩ - | 01 ⟩ + | 10 ⟩ - | 11 ⟩)

$f (x) = f_{2}$

$f (x)$ будет равно $1$ независимо от аргумента. Используя таблицу истинности XOR, легко убедиться, что во второй скобке $| 0 ⟩$ и $| 1 ⟩$ поменяются местами, но если вынести минус за скобку, то мы можем его не учитывать, так общий фазовый множитель (-1 в данном случае) для системы не имеет значения:

| ψ ⟩ = \frac{1}{2} (| 0 ⟩ + | 1 ⟩) (| 1 ⟩ - | 0 ⟩) = - \frac{1}{2} (| 0 ⟩ + | 1 ⟩) (| 0 ⟩ - | 1 ⟩) = - \frac{1}{2} (| 00 ⟩ - | 01 ⟩ + | 10 ⟩ - | 11 ⟩)

Видно, что при применении функций $f_{1}$ и $f_{2}$ , являющихся несбалансированными, мы получаем фактически одно и тоже состояние. Если после этого применить к первому кубиту оператор Адамара, то после измерения мы получим значение $0$ .

Рассмотрим теперь сбалансированные функции $f_{3}$ и $f_{4}$ .

$f (x) = f_{3}$

Здесь ситуация сложнее, так как $f (x)$ будет зависеть от состояния первого кубита. Поэтому мы раскроем скобки, а значения функции подставим позже:

$| ψ ⟩ = \frac{1}{2} (| 0 ⟩ + | 1 ⟩) (| 0 \oplus f (x) ⟩ - | 1 \oplus f (x) ⟩) = \frac{1}{2} (| 0 ⟩ | 0 \oplus f (x) ⟩ - | 0 ⟩ | 1 \oplus f (x) ⟩ + | 1 ⟩ | 0 \oplus f (x) ⟩ - | 1 ⟩ | 1 \oplus f (x) ⟩) =$

$= \frac{1}{2} (| 0 ⟩ | 0 \oplus 0 ⟩ - | 0 ⟩ | 1 \oplus 0 ⟩ + | 1 ⟩ | 0 \oplus 1 ⟩ - | 1 ⟩ | 1 \oplus 1 ⟩) = \frac{1}{2} (| 00 ⟩ - | 01 ⟩ + | 11 ⟩ - | 10 ⟩) =$

$= \frac{1}{2} (| 00 ⟩ - | 01 ⟩ - | 10 ⟩ + | 11 ⟩) = \frac{1}{2} (| 0 ⟩ - | 1 ⟩) (| 0 ⟩ - | 1 ⟩)$

Видно, что первый кубит поменял свое состояние - теперь он в суперпозиции $\frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩)$ , так что далее к нему можно применить оператор Адамара, после которого он перейдет в состояние $| 1 ⟩$ .

$f (x) = f_{4}$

Здесь будет похожая ситуация:

$= \frac{1}{2} (| 0 ⟩ | 0 \oplus 1 ⟩ - | 0 ⟩ | 1 \oplus 1 ⟩ + | 1 ⟩ | 0 \oplus 0 ⟩ - | 1 ⟩ | 1 \oplus 0 ⟩) = \frac{1}{2} (| 01 ⟩ - | 00 ⟩ + | 10 ⟩ - | 11 ⟩) =$

$= - \frac{1}{2} (| 00 ⟩ - | 01 ⟩ + | 11 ⟩ - | 10 ⟩) = - \frac{1}{2} (| 0 ⟩ - | 1 ⟩) (| 0 ⟩ - | 1 ⟩)$

Получили то же состояние $| ψ ⟩$ , что и для $f_{3}$ , с точностью до фазового множителя. Соответственно, здесь первый кубит после применения оператора Адамара также будет измерен с результатом $1$ .

Теперь можно получить более компактную формулу, которая подходит для всех четырех функций:

| ψ ⟩ = \frac{1}{2} ((- 1)^{f (0)} | 0 ⟩ + (- 1)^{f (1)} | 1 ⟩) (| 0 ⟩ - | 1 ⟩)

Задание

С помощью квантовых операторов попробуйте создать $U_{f}$ для всех четырех $f (x)$ .

Задание рекомендуется сделать до прочтения программистской части по алгоритму Дойча, так как там содержится ответ.

Алгоритм Дойча в коде#

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

Импортируем все необходимые библиотеки и модули, а также создадим квантовое устройство-симулятор, рассчитанное на схему из двух кубитов:

import pennylane as qml
from pennylane import numpy as np

dev = qml.device("default.qubit", shots=1, wires=2)

/home/runner/work/qmlcourse/qmlcourse/.venv/lib/python3.8/site-packages/_distutils_hack/__init__.py:33: UserWarning: Setuptools is replacing distutils.
  warnings.warn("Setuptools is replacing distutils.")

Теперь создадим функции для черного ящика. Обратите внимание, что здесь уже учтено сложение по модулю $2$ результата функции с состоянием второго кубита:

def f1():
    pass

def f2():
    qml.PauliX(wires=[1])

def f3():
    qml.CNOT(wires=[0, 1])

def f4():
    qml.PauliX(wires=0)
    qml.CNOT(wires=[0, 1])
    qml.PauliX(wires=0)

Создадим словарь с функциями и их названиями:

black_boxes_dict = {"f1": f1, "f2": f2, "f3": f3, "f4": f4}

А вот таким образом мы будем случайно выбирать название функции для черного ящика:

def random_black_box(black_boxes_dict):
    black_boxes_dict_list_keys = list(black_boxes_dict.keys())
    n = np.random.randint(0, len(black_boxes_dict_list_keys))

    return black_boxes_dict_list_keys[n]

А теперь самое важное – сам алгоритм Дойча:

@qml.qnode(dev, interface=None)
def circuit(black_box_name):
    qml.Hadamard(wires=0)
    qml.PauliX(wires=1)
    qml.Hadamard(wires=1)

    black_boxes_dict[black_box_name]()
    qml.Hadamard(wires=0)

    return qml.sample(qml.PauliZ([0]))

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

Выберем случайным образом функцию:

black_box_name = random_black_box(black_boxes_dict)

А затем запустим алгоритм Дойча и выведем результат его работы. Собственное значение $1$ оператора $Z$ будет соответствовать состоянию $| 0 ⟩$ (функция несбалансированная), а собственное значение $- 1$ – состоянию $| 1 ⟩$ (функция сбалансирована):

result = circuit(black_box_name)
print(result)

Проверим, насколько правильно сработал алгоритм. Для этого посмотрим на функцию из черного ящика:

print(black_box_name)

f2

Также посмотрим, как выглядит квантовая схема:

qml.drawer.use_style("default")
fig, ax = qml.draw_mpl(circuit)(black_box_name)
fig.show()

../../../_images/deutschs_algorithm_17_0.png

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

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

QMLCourse

Алгоритм Дойча

Contents

Алгоритм Дойча#

Алгоритм Дойча в коде#