Алгоритм Deutsch – Jozsa

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

• 1 Постановка проблемы
• 2 Мотивация
• 3 Классическое решение
• 4 История
• 5 Алгоритм
• 6 Алгоритм Дойча
• 7 См. Также
• 8 Ссылки
• 9 Внешние ссылки

В задаче Дойча – Йозса нам дается квантовый компьютер черного ящика, известный как оракул, который реализует некоторую функцию $f:\; \{\; 0,\; 1\}\; n\; \to \; \{0,\; 1\}\; \{\backslash \; displaystyle\; f\; \backslash \; двоеточие\; \backslash \; \{0,1\; \backslash \}\; ^\; \{n\}\; \backslash \; rightarrow\; \backslash \; \{0,1\; \backslash \}\}$. Функция принимает на вход n-значные двоичные значения и выдает на выходе 0 или 1 для каждого такого значения. Нам обещали, что функция будет либо константой (0 на всех выходах или 1 на всех выходах), либо сбалансированной (возвращает 1 для половины входного домена и 0 для второй половины). Затем задача состоит в том, чтобы определить, является ли $f\; \{\backslash \; displaystyle\; f\}$постоянным или сбалансированным, с помощью оракула.

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

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

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

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

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

Дальнейшие усовершенствования алгоритма Дойча – Йозса были сделаны Кливом и др., В результате чего был получен детерминированный алгоритм, требующий только одного запроса $f\; \{\backslash \; displaystyle\; f\}$. Этот алгоритм до сих пор называют алгоритмом Дойча – Йозса в честь новаторских методов, которые они использовали.

Для работы алгоритма Дойча – Йозса оракульные вычисления $f\; (\; x)\; \{\backslash \; displaystyle\; f\; (x)\}$from $x\; \{\backslash \; displaystyle\; x\}$должен быть квантовым оракулом, который не декогерируется $х\; \{\backslash \; displaystyle\; x\}$. Он также не должен оставлять копии $x\; \{\backslash \; displaystyle\; x\}$в конце вызова оракула.

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

$1\; 2\; n\; +\; 1\; \sum \; x\; =\; 0\; 2\; n\; -\; 1\; |\; Икс⟩\; (|\; 0⟩\; -\; |\; 1⟩)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{2\; ^\; \{n\; +\; 1\}\}\}\}\; \backslash \; sum\; \_\; \{x\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -\; 1\}\; |\; x\; \backslash \; rangle\; (|\; 0\; \backslash \; rangle\; -\; |\; 1\; \backslash \; rangle)\}$.

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

$1\; 2\; n\; +\; 1\; \sum \; x\; =\; 0\; 2\; n\; -\; 1\; |\; Икс⟩\; (|\; е\; (х)⟩\; -\; |\; 1\; \oplus \; е\; (х)⟩)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{2\; ^\; \{n\; +\; 1\}\}\}\}\; \backslash \; sum\; \_\; \{x\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -1\}\; |\; x\; \backslash \; rangle\; (|\; f\; (x)\; \backslash \; rangle\; -\; |\; 1\; \backslash \; oplus\; f\; (x)\; \backslash \; rangle)\}$.

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

$1\; 2\; n\; +\; 1\; \sum \; x\; =\; 0\; 2\; n\; -\; 1\; (-\; 1)\; f\; (x)\; |\; Икс⟩\; (|\; 0⟩\; -\; |\; 1⟩)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{2\; ^\; \{n\; +\; 1\}\}\}\}\; \backslash \; sum\; \_\; \{x\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -\; 1\}\; (-\; 1)\; ^\; \{f\; (x)\}\; |\; x\; \backslash \; rangle\; (|\; 0\; \backslash \; rangle\; -\; |\; 1\; \backslash \; rangle)\}$.

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

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

Мы применяем преобразование Адамара к каждому кубиту, чтобы получить

$1\; 2\; n\; \sum \; x\; =\; 0\; 2\; n\; -\; 1\; (-\; 1)\; f\; (x)\; [1\; 2\; n\; \sum \; y\; знак\; равно\; 0\; 2\; n\; -\; 1\; (-\; 1)\; x\; \cdot \; y\; |\; y⟩]\; =\; 1\; 2\; n\; \sum \; y\; =\; 0\; 2\; n\; -\; 1\; [\sum \; x\; =\; 0\; 2\; n\; -\; 1\; (-\; 1)\; f\; (x)\; (-\; 1)\; x\; \cdot \; y]\; |\; y⟩\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{2\; ^\; \{n\}\}\}\}\; \backslash \; sum\; \_\; \{x\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -1\}\; (-\; 1)\; ^\; \{f\; (x)\}\; \backslash \; left\; [\{\backslash \; frac\; \{1\}\; \{\backslash \; sqrt\; \{2\; ^\; \{n\}\}\}\}\; \backslash \; sum\; \_\; \{y\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -1\}\; (-\; 1)\; ^\; \{x\; \backslash \; cdot\; y\}\; |\; y\; \backslash \; rangle\; \backslash \; right]\; =\; \{\backslash \; frac\; \{1\}\; \{2\; ^\; \{n\}\}\}\; \backslash \; sum\; \_\; \{y\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -1\}\; \backslash \; left\; [\backslash \; sum\; \_\; \{x\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -1\}\; (-\; 1)\; ^\; \{f\; (x)\}\; (-\; 1)\; ^\; \{x\; \backslash \; cdot\; y\}\; \backslash \; right]\; |\; y\; \backslash \; rangle\}$

где $Икс\; \cdot \; Y\; знак\; равно\; Икс\; 0\; Y\; 0\; \oplus \; Икс\; 1\; Y\; 1\; \oplus \; \cdots \; \oplus \; Xn\; -\; 1\; Yn\; -\; 1\; \{\backslash \; Displaystyle\; x\; \backslash \; cdot\; y\; =\; x\_\; \{0\}\; y\_\; \{0\}\; \backslash \; oplus\; x\_\; \{1\}\; y\_\; \{1\}\; \backslash \; oplus\; \backslash \; cdots\; \backslash \; oplus\; x\_\; \{n-1\}\; y\_\; \{n-1\}\}$- сумма побитового произведения.

Наконец, мы исследуем вероятность измерения $|\; 0⟩\; \otimes \; N\; \{\backslash \; Displaystyle\; |\; 0\; \backslash \; rangle\; ^\; \{\backslash \; otimes\; n\}\}$,

$|\; 1\; 2\; n\; \sum \; x\; знак\; равно\; 0\; 2\; n\; -\; 1\; (-\; 1)\; f\; (x)\; |\; 2\; \{\backslash \; displaystyle\; \{\backslash \; bigg\; |\}\; \{\backslash \; frac\; \{1\}\; \{2\; ^\; \{n\}\}\}\; \backslash \; sum\; \_\; \{x\; =\; 0\}\; ^\; \{2\; ^\; \{n\}\; -1\}\; (-\; 1)\; ^\; \{f\; (x)\}\; \{\backslash \; bigg\; |\}\; ^\; \{2\}\}$

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

Алгоритм Дойча является частным случаем общего алгоритма Дойча – Йоже. Нам нужно проверить условие $f\; (0)\; =\; f\; (1)\; \{\backslash \; displaystyle\; f\; (0)\; =\; f\; (1)\}$. Это эквивалентно проверке $f\; (0)\; \oplus \; f\; (1)\; \{\backslash \; displaystyle\; f\; (0)\; \backslash \; oplus\; f\; (1)\}$(где $\oplus \; \{\backslash \; displaystyle\; \backslash \; oplus\}$- сложение по модулю 2, которое также можно рассматривать как квантовый элемент XOR, реализованный как элемент Управляемое НЕ ), если ноль, то $f\; \{\backslash \; displaystyle\; f\}$является постоянным, в противном случае $f\; \{\backslash \; displaystyle\; f\}$не является постоянным.

Начнем с двухкубитного состояния $|\; 0⟩\; |\; 1⟩\; \{\backslash \; displaystyle\; |\; 0\; \backslash \; rangle\; |\; 1\; \backslash \; rangle\}$и применить преобразование Адамара к каждому кубиту. Это дает

$1\; 2\; (|\; 0⟩\; +\; |\; 1⟩)\; (|\; 0⟩\; -\; |\; 1⟩).\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; (|\; 0\; \backslash \; rangle\; +\; |\; 1\; \backslash \; rangle)\; (|\; 0\; \backslash \; rangle\; -\; |\; 1\; \backslash \; rangle).\}$

Нам дана квантовая реализация функции $f\; \{\backslash \; displaystyle\; f\}$, который отображает $|\; x⟩\; |\; y⟩\; \{\backslash \; displaystyle\; |\; x\; \backslash \; rangle\; |\; y\; \backslash \; rangle\}$до $|\; x⟩\; |\; е\; (Икс)\; \oplus \; Y⟩\; \{\backslash \; Displaystyle\; |\; х\; \backslash \; rangle\; |\; е\; (х)\; \backslash \; oplus\; y\; \backslash \; rangle\}$. Применяя эту функцию к нашему текущему состоянию, мы получаем

$1\; 2\; (|\; 0⟩\; (|\; f\; (0)\; \oplus \; 0⟩\; -\; |\; f\; (0)\; \oplus \; 1⟩)\; +\; |\; 1⟩\; (|\; f\; (1)\; \oplus \; 0⟩\; -\; |\; е\; (1)\; \oplus \; 1⟩))\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; (|\; 0\; \backslash \; rangle\; (|\; f\; (0)\; \backslash \; oplus\; 0\; \backslash \; rangle\; -\; |\; f\; (0)\; \backslash \; oplus\; 1\; \backslash \; rangle)\; +\; |\; 1\; \backslash \; rangle\; (|\; f\; (1)\; \backslash \; oplus\; 0\; \backslash \; rangle\; -\; |\; f\; (1)\; \backslash \; oplus\; 1\; \backslash \; rangle))\}$

$=\; 1\; 2\; ((-\; 1)\; f\; (0)\; |\; 0⟩\; (|\; 0⟩\; -\; |\; 1⟩)\; +\; (-\; 1)\; е\; (1)\; |\; 1⟩\; (|\; 0⟩\; -\; |\; 1⟩))\; \{\backslash \; displaystyle\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; ((-\; 1)\; ^\; \{f\; (0)\}\; |\; 0\; \backslash \; rangle\; (|\; 0\; \backslash \; rangle\; -\; |\; 1\; \backslash \; rangle)\; +\; (-\; 1)\; ^\; \{f\; (1)\}\; |\; 1\; \backslash \; rangle\; (|\; 0\; \backslash \; rangle\; -\; |\; 1\; \backslash \; rangle))\; \}$

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

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

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

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

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

$=\; 1\; 2\; ((1\; +\; (-\; 1)\; f\; (0)\; \oplus \; f\; (1))\; |\; 0⟩\; +\; (1\; -\; (-\; 1)\; f\; (0)\; \oplus \; f\; (1))\; |\; 1⟩).\; \{\backslash \; displaystyle\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; ((1\; +\; (-\; 1)\; ^\; \{f\; (0)\; \backslash \; oplus\; f\; (1)\})\; |\; 0\; \backslash \; rangle\; +\; (1\; -\; (-\; 1)\; ^\; \{\; е\; (0)\; \backslash \; oplus\; f\; (1)\})\; |\; 1\; \backslash \; rangle).\}$

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

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

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