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

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

Алгоритм Дойча — Йожи для функции $f$ от $n$ переменных. $H$ — преобразование Адамара. $U_{f}$ — фазовый запрос. Нижний кубит — вспомогательный, используемый для осуществления фазового запроса.

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

Задача

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

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

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

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

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

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

$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 .$

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

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

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

$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 .$

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

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

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

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

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

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

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

№	$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)=\neg x$

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

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

$|\varphi \rangle =1\cdot |0\rangle +0\cdot |1\rangle .$

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

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

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

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

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

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

$|\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 )}=$

$=\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 для сбалансированных:

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

Литература

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