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

Алгоритм Бернштейна-Вазирани , который решает проблему Бернштейна-Вазирани , представляет собой квантовый алгоритм, изобретенный Итаном Бернштейном и Умешом Вазирани в 1997 году. Это ограниченная версия алгоритма Дойча-Йожсы , в которой вместо того, чтобы различать два разных класса функций, он пытается изучить строку, закодированную в функции. Алгоритм Бернштейна-Вазирани был разработан для доказательства разделения оракула между классами сложности BQP и BPP .

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

Дан оракул , реализующий функцию $f\colon \{0,1\}^{n}\rightarrow \{0,1\}$ в котором $f(x)$ обещает быть скалярным произведением между $x$ и секретная строка $s\in \{0,1\}^{n}$ модуль 2, $f(x)=x\cdot s=x_{1}s_{1}\oplus x_{2}s_{2}\oplus \cdots \oplus x_{n}s_{n}$, находить $s$.

Алгоритм

Классически наиболее эффективный метод поиска секретной строки — вычисление функции $n$ раз с входными значениями $x=2^{i}$ для всех $i\in \{0,1,...,n-1\}$:

${\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1_{n})&=s_{n}\\\end{aligned}}$

В отличие от классического решения, которое требует как минимум $n$ запросы функции, чтобы найти $s$, требуется только один запрос с использованием квантовых вычислений. Квантовый алгоритм выглядит следующим образом:

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

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

Далее примените оракул $U_{f}$ который преобразует $|x\rangle \to (-1)^{f(x)}|x\rangle$. Это можно смоделировать с помощью стандартного оракула, который преобразует $|b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle$ применив этот оракул к ${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle$. ( $\oplus$ обозначает сложение по модулю два.) Это преобразует суперпозицию в

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

К каждому кубиту применяется другое преобразование Адамара, в результате чего для кубитов, где $s_{i}=1$, его состояние преобразуется из $|-\rangle$ к $|1\rangle$ и для кубитов, где $s_{i}=0$, его состояние преобразуется из $|+\rangle$ к $|0\rangle$. Чтобы получить $s$, измерение в стандартном базисе ( $\{|0\rangle ,|1\rangle \}$) выполняется на кубитах.

Графически алгоритм можно представить следующей схемой, где $H^{\otimes n}$ обозначает преобразование Адамара на $n$ кубиты:

$|0\rangle ^{n}\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}|x\rangle \xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{2^{n}}}\sum _{x,y\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}|y\rangle =|s\rangle$

Причина того, что последнее состояние $|s\rangle$ потому что для конкретного $y$,

${\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot s+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot (s\oplus y)}=1{\text{ if }}s\oplus y={\vec {0}},\,0{\text{ otherwise}}.$

С $s\oplus y={\vec {0}}$ верно только тогда, когда $s=y$, это означает, что единственная ненулевая амплитуда находится на $|s\rangle$. Таким образом, измерение выходного сигнала схемы в вычислительной базе дает секретную строку $s$.

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

См. также

• Проблема со скрытой линейной функцией