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

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

Алгоритм Дойча — первый вариант алгоритма, разработанный Дойчем в 1985 году; в нём рассматривается функция ${\displaystyle f(x_{1})}$ от одной переменной.

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

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

В квантовой постановке вычисление функции происходит в форме обращения к квантовому оракулу, производящего унитарное преобразование ${\displaystyle U_{f}}$, которое действует на наборе ${\displaystyle |x_{1}x_{2}\dots x_{n}\rangle |y\rangle =|x\rangle |y\rangle }$ из ${\displaystyle n}$ кубитов ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$, выступающих аргументами функции, а также целевого кубита ${\displaystyle y}$, на котором отразятся вычисления. Результатом такого преобразования для любого собственного состояния ${\displaystyle |x\rangle }$ является набор ${\displaystyle |x\rangle |y\oplus f(x)\rangle }$, где ${\displaystyle \oplus }$ — обозначение исключающего «или», соответствующего результату операции контролируемого отрицания кубита ${\displaystyle |y\rangle }$ с помощью кубита ${\displaystyle |f(x)\rangle }$. Так как унитарные преобразования являются линейными, результат данного преобразования для суперпозиции собственных состояний ${\displaystyle |x\rangle =\alpha _{0}|0\rangle +\ldots +\alpha _{2^{n}-1}|2^{n}-1\rangle }$ определяется как ${\displaystyle U_{f}(|x\rangle |y\rangle )=\alpha _{0}|0\rangle |y\oplus f(0)\rangle +\ldots +\alpha _{2^{n}-1}|{2^{n}-1}\rangle |y\oplus f(2^{n}-1)\rangle .}$

Алгоритму Дойча — Йожи достаточно однократного обращения к квантовому оракулу для достоверного решения задачи.

В основе алгоритма лежит преобразование Адамара^[англ.] ${\textstyle H}$, результатом применения которого к собственным состояниям кубита являются суперпозиции

${\displaystyle |+\rangle =H|0\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle +|1\rangle {\big )},}$

${\displaystyle |-\rangle =H|1\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}.}$

Если при обращении к оракулу целевой кубит находится в состоянии ${\displaystyle |-\rangle }$, то оракул реализует так называемый фазовый запрос, результатом которого для собственных состояний является умножение всего состояния на ${\displaystyle (-1)^{f(x)}}$^[1]:

${\displaystyle U_{f}{\big (}|x\rangle |-\rangle {\big )}={\frac {1}{\sqrt {2}}}|x\rangle {\big (}|f(x)\rangle -|1\oplus f(x)\rangle {\big )}=(-1)^{f(x)}|x\rangle |-\rangle .}$

Таким образом, в случае суперпозиции состояний фазовый запрос инвертирует фазу у всех состояний ${\displaystyle x}$, соответствующих ${\displaystyle f(x)=1}$, и оставит без изменений состояния, соответствующие ${\displaystyle f(x)=0}$. В качестве аргумента фазового запроса алгоритм Дойча — Йожи использует состояние

${\displaystyle H^{\otimes n}|0\rangle ^{\otimes n}=|+\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x\in \{0,1\}^{n}}|x\rangle ,}$

являющееся равномерной суперпозицией всех собственных состояний набора из ${\displaystyle n}$ кубитов. Здесь ${\displaystyle \otimes n}$ обозначает возведение в степень ${\displaystyle n}$ через тензорное (кронекерово) произведение. Результат применения фазового запроса к такому состоянию равен

${\displaystyle U_{f}{\big (}|+\rangle ^{\otimes n}|-\rangle {\big )}={\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle |-\rangle .}$

После повторного применения преобразования ${\displaystyle H^{\otimes n}}$ к первым ${\displaystyle n}$ кубитам амплитуда состояния ${\displaystyle |0\rangle ^{\otimes n}}$ будет равна

${\displaystyle {\frac {1}{2^{n}}}\sum \limits _{x\in \{0,1\}^{n}}(-1)^{f(x)},}$

то есть ${\displaystyle 1}$ при ${\displaystyle f(x)=0}$ или ${\displaystyle -1}$ при ${\displaystyle f(x)=1}$, либо ${\displaystyle 0}$, если функция сбалансирована. Таким образом, проверка сбалансированности функции равносильна проверке того, что все кубиты находятся в состоянии ${\displaystyle |0\rangle }$ по окончании алгоритма.

Другими словами, алгоритм представляет собой применение к нулевому вектору ${\displaystyle |0\rangle ^{\otimes n}}$ оператора ${\displaystyle H^{\otimes n}U_{f}H^{\otimes n}}$ и измерение состояния регистра. Если все биты регистра равны ${\displaystyle 0}$, значит значение функции ${\displaystyle f(x)}$ не зависит от ${\displaystyle x}$, в противном случае функция является сбалансированной.

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

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

№	${\displaystyle f(0)}$	${\displaystyle 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)=\neg x}$

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

На первом шаге кубиту задаётся нулевое состояние:

${\displaystyle |\varphi \rangle =1\cdot |0\rangle +0\cdot |1\rangle .}$

Применение преобразования Адамара даёт

${\displaystyle |\varphi \rangle ={\frac {1}{\sqrt {2}}}\cdot |0\rangle +{\frac {1}{\sqrt {2}}}\cdot |1\rangle .}$

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

Фазовый запрос ${\displaystyle O_{f}}$ к функции ${\displaystyle f}$ даёт следующее состояние:

${\displaystyle |\varphi \rangle =(-1)^{f(0)}\cdot {\frac {1}{\sqrt {2}}}\cdot |0\rangle +(-1)^{f(1)}\cdot {\frac {1}{\sqrt {2}}}\cdot |1\rangle .}$

Второе преобразование Адамара приводит к следующему состоянию:

${\displaystyle |\varphi \rangle =(-1)^{f(0)}\cdot {\frac {1}{2}}\cdot {\big (}|0\rangle +|1\rangle {\big )}+(-1)^{f(1)}\cdot {\frac {1}{2}}\cdot {\big (}|0\rangle -|1\rangle {\big )}=}$

${\displaystyle =\left((-1)^{f(0)}+(-1)^{f(1)}\right)\cdot {\frac {1}{2}}\cdot |0\rangle +\left((-1)^{f(0)}-(-1)^{f(1)}\right)\cdot {\frac {1}{2}}\cdot |1\rangle .}$

При измерении состояния кубита получается 0 для константных функций и 1 для сбалансированных:

№	${\displaystyle f(0)}$	${\displaystyle f(1)}$	Состояние кубита ${\displaystyle |\varphi \rangle }$	Вероятность получения 0	Вероятность получения 1
1	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle {\big (}(-1)^{0}+(-1)^{0}{\big )}\cdot {\frac {1}{2}}\cdot |0\rangle +{\big (}(-1)^{0}-(-1)^{0}{\big )}\cdot {\frac {1}{2}}\cdot |1\rangle =1\cdot |0\rangle +0\cdot |1\rangle }$	${\displaystyle 1^{2}=1}$	${\displaystyle 0}$
2	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle {\big (}(-1)^{1}+(-1)^{1}{\big )}\cdot {\frac {1}{2}}\cdot |0\rangle +{\big (}(-1)^{1}-(-1)^{1}{\big )}\cdot {\frac {1}{2}}\cdot |1\rangle =-1\cdot |0\rangle +0\cdot |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 {\big (}(-1)^{1}+(-1)^{0}{\big )}\cdot {\frac {1}{2}}\cdot |0\rangle +{\big (}(-1)^{1}-(-1)^{0}{\big )}\cdot {\frac {1}{2}}\cdot |1\rangle =0\cdot |0\rangle -1\cdot |1\rangle }$	${\displaystyle 0}$	${\displaystyle (-1)^{2}=1}$

• Wolf R. d. Quantum Computing (англ.): Lecture Notes — 2019. — 176 p. — arXiv:1907.09415