Алгоритм Германа – Йожи

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

Задача Дойча-Йожсы специально разработана так, чтобы быть простой для квантового алгоритма и сложной для любого детерминированного классического алгоритма. Это проблема черного ящика , которую квантовый компьютер может эффективно решить без ошибок, тогда как детерминированному классическому компьютеру для решения проблемы потребуется экспоненциальное количество запросов к черному ящику. Более формально, это дает оракул, относительно которого EQP (класс проблем, которые могут быть решены точно за полиномиальное время на квантовом компьютере) и P различны.

Поскольку проблему легко решить на вероятностном классическом компьютере, она не дает разделения оракула с BPP , классом задач, которые можно решить с ограниченной ошибкой за полиномиальное время на вероятностном классическом компьютере. Проблема Саймона является примером проблемы, которая приводит к разделению оракула между BQP и BPP .

Постановка задачи

В задаче Дойча-Йожсы нам дан квантовый компьютер «черный ящик», известный как оракул , который реализует некоторую функцию:

$f\colon \{0,1\}^{n}\rightarrow \{0,1\}$

Функция принимает на вход n-битные двоичные значения и выдает на выходе либо 0, либо 1 для каждого такого значения. Нам обещают , что функция либо постоянна (0 на всех входах или 1 на всех входах), либо сбалансирована (1 ровно для половины входной области и 0 для другой половины). Тогда задача состоит в том, чтобы определить, является ли $f$ является постоянным или сбалансированным с помощью оракула.

Классическое решение

Для обычного детерминированного алгоритма, где $n$ это количество битов, $2^{n-1}+1$ оценки $f$ потребуется в худшем случае. Чтобы доказать это $f$ является константой, необходимо оценить чуть более половины набора входных данных и обнаружить, что их выходные данные идентичны (поскольку функция гарантированно будет либо сбалансированной, либо постоянной, а не где-то посередине). В лучшем случае функция сбалансирована и первые два выходных значения различны. Для обычного рандомизированного алгоритма константа $k$ оценки функции достаточно для получения правильного ответа с высокой вероятностью (неудача с вероятностью $\epsilon \leq 1/2^{k}$ с $k\geq 1$). Однако, $k=2^{n-1}+1$ оценки по-прежнему необходимы, если мы хотим получить ответ, не допускающий ошибки. Квантовый алгоритм Дойча-Йожы дает ответ, который всегда верен при единственной оценке $f$.

История

Алгоритм Дойча-Йожсы обобщает более раннюю (1985 г.) работу Дэвида Дойча, которая предоставила решение для простого случая, когда $n=1$.
В частности, для булевой функции , входной сигнал которой равен одному биту, $f:\{0,1\}\rightarrow \{0,1\}$, оно постоянно?

Алгоритм, как первоначально предложил Дойч, не был детерминированным. Алгоритм сработал с вероятностью в половину. В 1992 году Дойч и Йожа разработали детерминированный алгоритм, который был обобщен до функции, принимающей $n$ бит для его ввода. В отличие от алгоритма Дойча, этот алгоритм требовал двух вычислений функции вместо одной.

Дальнейшие улучшения алгоритма Дойча-Йожы были внесены Кливом и др., в результате получается алгоритм, который одновременно является детерминированным и требует только одного запроса $f$. Этот алгоритм до сих пор называют алгоритмом Дойча – Йожи в честь использованных им новаторских методов.

Алгоритм

Чтобы алгоритм Дойча-Йожы работал, вычисления оракула $f(x)$ от $x$ должен быть квантовый оракул, который не декогерирует $x$. Он также не должен делать копию $x$, потому что это нарушит теорему о запрете клонирования .

Алгоритм Дойча-Йожы представляет собой квантовую схему.

Алгоритм начинается с $n+1$ битовое состояние $|0\rangle ^{\otimes n}|1\rangle$. То есть каждый из первых n битов находится в состоянии $|0\rangle$ и последний бит $|1\rangle$. К каждому биту применяется вентиль Адамара для получения состояния

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )$,

где $x$ пробегает по всем $n$-битовые строки. У нас есть функция $f$ реализован как квантовый оракул. Оракул отображает свое входное состояние $|x\rangle |y\rangle$ к $|x\rangle |y\oplus f(x)\rangle$, где $\oplus$ обозначает сложение по модулю 2. Применение квантового оракула дает;

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle )$.

Для каждого $x,f(x)$ равно либо 0, либо 1. Проверяя эти две возможности, мы видим, что приведенное выше состояние равно

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )$.

В этот момент последний кубит ${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}$ можно игнорировать и остается следующее:

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle$.

Далее кубит пройдет через ворота Адамара.

$H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle$

( $j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}$ представляет собой сумму побитового произведения, где $\oplus$ сложение по модулю 2) по первому регистру для получения

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle$

Отсюда мы видим, что вероятность состояния $k$ быть измеренным является

$\left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot k}\right|^{2}$

Вероятность измерения $k=0$, соответствующий $|0\rangle ^{\otimes n}$, является

${\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}$

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

Алгоритм Германа

Алгоритм Дойча является частным случаем общего алгоритма Дойча – Йожи, где n = 1 в $f\colon \{0,1\}^{n}\rightarrow \{0,1\}$. Нам нужно проверить состояние $f(0)=f(1)$. Это эквивалентно проверке $f(0)\oplus f(1)$ (где $\oplus$ — это сложение по модулю 2, которое также можно рассматривать как квантовый вентиль XOR, реализованный как вентиль Controlled NOT ), если ноль, то $f$ является постоянным, в противном случае $f$ не является постоянным.

Начнем с двухкубитного состояния $|0\rangle |1\rangle$ и применить вентиль Адамара к каждому кубиту. Это дает

${\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).$

Нам дана квантовая реализация функции $f$ это отображает $|x\rangle |y\rangle$ к $|x\rangle |f(x)\oplus y\rangle$. Применяя эту функцию к нашему текущему состоянию, мы получаем

${\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))$

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

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

Мы игнорируем последний бит и глобальную фазу и поэтому имеем состояние

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

Применяя вентиль Адамара к этому состоянию, мы имеем

${\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )$

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

$f(0)\oplus f(1)=0$ тогда и только тогда, когда мы измеряем $|0\rangle$ и $f(0)\oplus f(1)=1$ тогда и только тогда, когда мы измеряем $|1\rangle$. Итак, мы с уверенностью знаем, $f(x)$ является постоянным или сбалансированным.

См. также

• Алгоритм Бернштейна – Вазирани

Внешние ссылки

• Лекция Дойча об алгоритме Дойча-Йожы