WikiSort.ru - Не сортированное

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

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

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

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

Алгоритм Дойча — Йожи основан на разработанном Давидом Дойчем в 1985 году схожем алгоритме, являющемся частным случаем первого. В этом алгоритме функция ${\displaystyle f(x_{1})}$ являлась функцией одной переменной, в отличие от функции многих переменных ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})}$ , используемой в более позднем алгоритме.

Алгоритм

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

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

${\displaystyle O_{f}}$  — фазовый запрос, который инвертирует фазу для состояний регистра, соответствующих единицам функции ${\displaystyle f}$ и не изменяет состояния, соответствующие нулям функции: ${\displaystyle \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]

Работа алгоритма на примере задачи Дойча

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

№	f(0)	f(1)
1	0	0	${\displaystyle f(x)\equiv 0}$
2	1	1	${\displaystyle f(x)\equiv 1}$
3	0	1	${\displaystyle f(x)=x}$
4	1	0	${\displaystyle f(x)=NOT(x)}$

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

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

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

Применяя фазовый запрос ${\displaystyle O_{f}}$ к нашей функции ${\displaystyle f}$ , получаем следующее состояние: ${\displaystyle \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 }$

Второе преобразование Адамара приводит к следующему состоянию: ${\displaystyle \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)	Состояние кубита ${\displaystyle \vert \varphi \rangle }$	Вероятность получения 0	Вероятность получения 1
1	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle ((-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 }$	${\displaystyle 1^{2}=1}$	${\displaystyle 0}$
2	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle ((-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 }$	${\displaystyle (-1)^{2}=1}$	${\displaystyle 0}$
3	${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle ((-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 }$	${\displaystyle 0}$	${\displaystyle 1^{2}=1}$
4	${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle ((-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 }$	${\displaystyle 0}$	${\displaystyle (-1)^{2}=1}$

Примечания