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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Алгоритм Дойча — Йожи для функции f от n переменных. H — преобразование Адамара. U_f — фазовый запрос. Нижний кубит — вспомогательный, используемый для осуществления фазового запроса.

Алгоритм Дойча — Йожи (упоминается также как алгоритм Дойча — Джозы) — квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Йожей[en] в 1992 году, и ставший одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Эти алгоритмы благодаря использованию явления квантовой запутанности и принципа суперпозиции обладают значительным приростом скорости выполнения по сравнению с соответствующими классическими алгоритмами.

Задача Дойча — Йожи заключается в определении является ли функция двоичной переменной f(n) постоянной (принимает либо значение 0, либо 1 при любых аргументах) или сбалансированной (для половины области определения принимает значение 0, для другой половины 1). При этом считается априорно известным, что функция либо является константой, либо сбалансирована.

Для решения этой задачи классическому детерминированному алгоритму необходимо произвести 2^{n-1}+1 вычислений функции f в худшем случае. Классическому вероятностному алгоритму потребуется меньше времени, чтобы дать верный ответ с высокой вероятностью. Но в любом случае для получения верного ответа с единичной вероятностью потребуется 2^{n-1}+1 вычислений. Алгоритм даёт верный ответ, один раз применив фазовый запрос, соответствующий заданной функции f.

Если функция f несбалансирована, то алгоритм может выдать ответ «константа» с некоторой вероятностью, причём чем больше разница между количеством «0» и «1», тем больше будет эта вероятность[1].

Алгоритм Дойча — Йожи основан на разработанном Давидом Дойчем в 1985 году схожем алгоритме, являющемся частным случаем первого. В этом алгоритме функция f(x_1) являлась функцией одной переменной, в отличие от функции многих переменных f(x_1, x_2, \dots , x_n), используемой в более позднем алгоритме.

Алгоритм[править | править вики-текст]

На входе алгоритма есть булева функция f(x_1, x_2, \dots ,x_n) от n булевых переменных. Алгоритм представляет собой применение к нулевому вектору \vert 0\rangle оператора H^{\otimes n} O_{f} H^{\otimes n} и измерение состояния регистра. Если все биты регистра равны 0, значит значение функции f(x) не зависит от x, в противном случае функция является сбалансированной.

Здесь H — преобразование Адамара: H = \frac{1}{ \sqrt{2} } \begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}

O_{f} — фазовый запрос, который инвертирует фазу для состояний регистра, соответствующих единицам функции f и не изменяет состояния, соответствующие нулям функции: \lambda_{0} \cdot \vert 0\rangle + \lambda_{1} \cdot \vert 1\rangle \xrightarrow{O_{f}} (-1)^{f(0)} \cdot \lambda_{0} \cdot \vert 0\rangle + (-1)^{f(1)} \cdot \lambda_{1} \cdot \vert 1\rangle [2]

Работа алгоритма на примере задачи Дойча[править | править вики-текст]

На вход алгоритму подаётся булева функция одной переменной f(x). Всего существуют 4 такие функции[2]:

f(0) f(1)
1 0 0 f(x) \equiv 0
2 1 1 f(x) \equiv 1
3 0 1 f(x) = x
4 1 0 f(x) = NOT(x)

Функции 1 и 2 назовём константными, а функции 3 и 4 — сбалансированными.

На первом шаге задаём кубиту нулевое состояние: \vert \varphi \rangle = 1 \cdot \vert 0 \rangle + 0 \cdot \vert 1 \rangle

Применяя преобразование Адамара получаем \vert \varphi \rangle = \frac{1}{ \sqrt{2} } \cdot \vert 0 \rangle + \frac{1}{ \sqrt{2} } \cdot \vert 1 \rangle. В принципе, можно было бы сразу назначить кубиту такое состояние, но технически проще сначала задать нулевое состояние, а потом преобразовать его с помощью унитарных преобразований к нужному виду.

Применяя фазовый запрос O_{f} к нашей функции f, получаем следующее состояние: \vert \varphi \rangle = (-1) ^ {f(0)} \cdot \frac{1}{ \sqrt{2} } \cdot \vert 0 \rangle + (-1) ^ {f(1)} \cdot \frac{1}{ \sqrt{2} } \cdot \vert 1 \rangle

Второе преобразование Адамара приводит к следующему состоянию: \vert \varphi \rangle = (-1) ^ {f(0)} \cdot \frac{1}{2} \cdot (\vert 0 \rangle + \vert 1 \rangle) + (-1) ^ {f(1)} \cdot \frac{1}{2} \cdot (\vert 0 \rangle - \vert 1 \rangle) = ((-1) ^ {f(0)} + (-1) ^ {f(1)}) \cdot \frac{1}{2} \cdot \vert 0 \rangle + ((-1) ^ {f(0)} - (-1) ^ {f(1)}) \cdot \frac{1}{2} \cdot \vert 1 \rangle

При измерении состояния кубита получим 0 для константных функций и 1 для сбалансированных. Это можно увидеть, если подставить всевозможные функции f(x) в выражение для состояния кубита:

f(0) f(1) Состояние кубита \vert \varphi \rangle Вероятность получения 0 Вероятность получения 1
1 0 0 ((-1) ^ 0 + (-1) ^ 0) \cdot \frac{1}{2} \cdot \vert 0 \rangle + ((-1) ^ 0 - (-1) ^ 0) \cdot \frac{1}{2} \cdot \vert 1 \rangle = 1 \cdot \vert 0 \rangle + 0 \cdot \vert 1 \rangle 1^{2} = 1 0
2 1 1 ((-1) ^ 1 + (-1) ^ 1) \cdot \frac{1}{2} \cdot \vert 0 \rangle + ((-1) ^ 1 - (-1) ^ 1) \cdot \frac{1}{2} \cdot \vert 1 \rangle = -1 \cdot \vert 0 \rangle + 0 \cdot \vert 1 \rangle (-1)^{2} = 1 0
3 0 1 ((-1) ^ 0 + (-1) ^ 1) \cdot \frac{1}{2} \cdot \vert 0 \rangle + ((-1) ^ 0 - (-1) ^ 1) \cdot \frac{1}{2} \cdot \vert 1 \rangle = 0 \cdot \vert 0 \rangle + 1 \cdot \vert 1 \rangle 0 1^{2} = 1
4 1 0 ((-1) ^ 1 + (-1) ^ 0) \cdot \frac{1}{2} \cdot \vert 0 \rangle + ((-1) ^ 1 - (-1) ^ 0) \cdot \frac{1}{2} \cdot \vert 1 \rangle = 0 \cdot \vert 0 \rangle - 1 \cdot \vert 1 \rangle 0 (-1)^{2} = 1

Примечания[править | править вики-текст]