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

Алгори́тм До́йча, квантовый алгоритм, предложенный Д. Дойчем в 1985 г., для решения следующей задачи. Пусть дана функция ${\displaystyle f}$, которая в качестве аргумента принимает ${\displaystyle 0}$ или ${\displaystyle 1}$ и в качестве значения тоже выдаёт ${\displaystyle 0}$ или ${\displaystyle 1}$. Функция задана в виде чёрного ящика, т. е. имеется возможность подавать на вход одно из двух значений и считывать выход (значение функции). Требуется за наименьшее число обращений к функции понять, совпадают или отличаются значения ${\displaystyle f(0)}$ и ${\displaystyle f(1)}$.

В классической парадигме вычислений на этот вопрос можно ответить, обратившись к функции два раза: вычислив значения функции по отдельности для обоих значений аргумента и затем сравнив эти значения. На квантовом компьютере можно ответить на этот вопрос, обратившись к аналогичному квантовому чёрному ящику лишь единожды. Сначала происходит вычисление функции в обеих точках сразу (точнее – строится когерентная суперпозиция из обоих значений функции), а затем нужным образом производится интерференция этих двух альтернатив, с тем чтобы не узнавать значения функции в точках по отдельности, а сразу ответить непосредственно на требуемый вопрос.

Квантовая схема алгоритма Дойча приведена на рисунке.

Алгоритм Дойча использует два кубита. Начальные состояния кубитов записаны слева. То есть алгоритм предписывает создать вначале два кубита в соответствующих состояниях (задаваемых векторами комплексного линейного пространства). Линия на схеме означает в данном случае один кубит. Путь вдоль черты слева направо предписывает последовательность применяемых вычислительных (унитарных) операций (вентилей). На рисунке однокубитный вентиль ${\displaystyle H}$ (преобразование Адамара) преобразует базисный вектор ${\displaystyle \left|0\right\rangle }$ (соответствующий значению бита 0) в вектор ${\displaystyle \psi _{+}=(\left|0\right\rangle +\left|1\right\rangle )/{\sqrt {2}}}$, а базисный вектор ${\displaystyle \left|1\right\rangle }$ (соответствующий значению бита ${\displaystyle 1}$) – в вектор ${\displaystyle \psi _{-}=(\left|0\right\rangle -\left|1\right\rangle )/{\sqrt {2}}}$. Поскольку рассматриваются линейные операторы, то достаточно задать их действие на базисные векторы. Двухкубитный вентиль ${\displaystyle U_{f}}$ преобразует ${\displaystyle \left|x,0\right\rangle }$ в ${\displaystyle \left|x,f(x)\right\rangle }$ и ${\displaystyle \left|x,1\right\rangle }$ – в ${\displaystyle \left|x,1-f(x)\right\rangle }$, где ${\displaystyle x}$ есть ${\displaystyle 0}$ или ${\displaystyle 1}$. То есть этот вентиль осуществляет вычисление функции ${\displaystyle f}$. На его первый вход подаётся ${\displaystyle \psi _{+}=(\left|0\right\rangle +\left|1\right\rangle )/{\sqrt {2}}}$, т. е. суперпозиция обоих значений аргументов. Соответственно, функция вычисляется как бы одновременно в двух точках. После чего вентиль ${\displaystyle H}$ создаёт интерференцию между этими двумя альтернативами. Последний прямоугольник в верхней строке схемы означает проведение измерения над данным кубитом. Несложный алгебраический расчёт показывает, что результат измерения, равный ${\displaystyle 0}$, означает, что значения функции в двух точках совпадают, результат, равный ${\displaystyle 1}$, – что отличаются. Таким образом, мы отвечаем на требуемый вопрос за одно обращение к функции.

Далее приведён расчёт для алгоритма Дойча. Начальное состояние первого кубита – ${\displaystyle \psi _{+}=(\left|0\right\rangle +\left|1\right\rangle )/{\sqrt {2}}}$, начальное состояние второго кубита – ${\displaystyle \psi _{-}=(\left|0\right\rangle -\left|1\right\rangle )/{\sqrt {2}}}$. Отметим, что обычно алгоритм рассматривается, начиная с начальных базисных векторов ${\displaystyle \left|0\right\rangle }$ и ${\displaystyle \left|1\right\rangle }$, которые при помощи преобразования Адамара преобразуются в векторы ${\displaystyle \psi _{+}}$ и ${\displaystyle \psi _{-}}$.

Совместное состояние двух кубитов записывается в виде
${\displaystyle \psi _{+}\otimes \psi _{-}}$, где ${\displaystyle \otimes }$ – тензорное произведение векторов. Совместное состояние можно переписать в виде

${\displaystyle {\begin{aligned}\psi _{+}\otimes \psi _{-}={\frac {1}{2}}(\left|0\right\rangle +\left|1\right\rangle )\otimes (\left|0\right\rangle -\left|1\right\rangle )=\\={\frac {1}{2}}(\left|0\right\rangle \otimes \left|0\right\rangle -\left|0\right\rangle \otimes \left|1\right\rangle +\left|1\right\rangle \otimes \left|0\right\rangle -\left|1\right\rangle \otimes \left|1\right\rangle )\end{aligned}}}$.

В предыдущих обозначениях можно записать Невозможно разобрать выражение (неизвестная функция «\ket»): {\displaystyle \left|0\right\rangle\otimes\left|0\right\rangle=\ket{00}} , Невозможно разобрать выражение (неизвестная функция «\ket»): {\displaystyle \left|0\right\rangle\otimes\left|1\right\rangle=\ket{01}} и т. д. Вентиль ${\displaystyle U_{f}}$ преобразует это состояние в

Это составное состояние двух кубитов является сцепленным (запутанным). Появление сцепленных состояний есть необходимое условие «квантового ускорения», т. е. более высокой эффективности квантового алгоритма по сравнению с классическими.

Заметим, что если ${\displaystyle f(x)=0}$, то Невозможно разобрать выражение (неизвестная функция «\ket»): {\displaystyle \ket{f(x)}-\ket{1-f(x)}=\left|0\right\rangle-\left|1\right\rangle} , а если ${\displaystyle f(x)=1}$, то Невозможно разобрать выражение (неизвестная функция «\ket»): {\displaystyle \ket{f(x)}-\ket{1-f(x)}=\left|1\right\rangle-\left|0\right\rangle} . Таким образом, если ${\displaystyle f(0)=f(1)}$, то последнее выражение переписывается в виде (с точностью до знака перед всем выражением)

${\displaystyle {\frac {1}{2}}(\left|0\right\rangle +\left|1\right\rangle )\otimes (\left|0\right\rangle -\left|1\right\rangle )=\psi _{+}\otimes \psi _{-}}$,

а если ${\displaystyle f(0)\neq f(1)}$, то оно переписывается в виде (также с точностью до знака перед всем выражением)

${\displaystyle {\frac {1}{2}}(\left|0\right\rangle -\left|1\right\rangle )\otimes (\left|0\right\rangle -\left|1\right\rangle )=\psi _{-}\otimes \psi _{-}}$.

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

Теперь применим к первому кубиту, который находится либо в состоянии ${\displaystyle \psi _{+}}$, если ${\displaystyle f(0)=f(1)}$, либо в состоянии ${\displaystyle \psi _{-}}$, если ${\displaystyle f(0)\neq f(1)}$, преобразование Адамара ${\displaystyle H:}$

${\displaystyle H\psi _{+}={\frac {1}{\sqrt {2}}}(H\left|0\right\rangle +H\left|1\right\rangle )={\frac {1}{\sqrt {2}}}(\psi _{+}+\psi _{-})=\left|0\right\rangle }$,

${\displaystyle H\psi _{-}={\frac {1}{\sqrt {2}}}(H\left|0\right\rangle -H\left|1\right\rangle )={\frac {1}{\sqrt {2}}}(\psi _{+}-\psi _{-})=\left|1\right\rangle }$.

Конечное состояние первого кубита есть ${\displaystyle \left|0\right\rangle }$, если значения функции в двух точках совпадают, и ${\displaystyle \left|1\right\rangle }$, если они не совпадают. В первом случае в результате измерения с вероятностью единица получается ${\displaystyle 0}$, во втором – ${\displaystyle 1}$.

Таким образом, за одно обращение к функции ${\displaystyle f}$ удаётся ответить на вопрос о том, совпадают или отличаются значения этой функции в двух точках.