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

Алгоритм Deutsch-Jozsa является детерминированным квантовый алгоритм , предложенный Дэвидом Дойч и Ричард Джозза в 1992 году с улучшениями по Ричард Клив , Артур Экерт , Кьяра Macchiavello и Мишель Моска в 1998 году ^{[1] [2]} Хотя мало практического использования тока, это один из первых примеров квантового алгоритма, который экспоненциально быстрее любого возможного детерминированного классического алгоритма. ^[3]

Описание проблемы [ править ]

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

Мотивация [ править ]

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

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

Классическое решение [ править ]

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

История [ править ]

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

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

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

Алгоритм [ править ]

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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]={\frac {1}{2^{n}}}\sum _{y=0}^{2^{n}-1}\left[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle }$

где - сумма побитового произведения.${\displaystyle x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}}$

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

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

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

Алгоритм Дойча [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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