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

Алгоритм предложен профессором Калифорнийского университета в Беркли Умешем Вазирани^[en] и его студентом Итаном Бернштейном. При описании алгоритма современные источники, как правило, ссылаются на выступление Бернштейна и Вазирани^[2] на симпозиуме по теории вычислений в 1993 году^[3]. Алгоритм Бернштейна — Вазирани является расширенной версией алгоритма Дойча — Йожи, поскольку вместо определения принадлежности функции к определённому классу — сбалансированная или постоянная (то есть принимает либо значение 0, либо 1 при любых аргументах) — алгоритм находит «спрятанный» вектор, позволяющий однозначно определить значение функции в любой точке^[4].

Алгоритм Бернштейна — Вазирани демонстрирует в решаемой им задаче зазор между классическими и квантовыми алгоритмами по наименьшему требуемому количеству запросов к оракулу (чёрному ящику). Даже если разрешить использование вероятностных алгоритмов (с заранее ограниченной вероятностью ошибки), решение классической задачи потребует ${\displaystyle O(n)}$ обращений к оракулу, в то время как в квантовом алгоритме достаточно ${\displaystyle O(1)}$ обращений к нему^[5].

Рассмотрим оракул, преобразующий ${\displaystyle n}$-битное число в один бит, то есть ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$.

Причём ${\displaystyle f(x)=a\cdot x}$, где ${\displaystyle \cdot }$ — скалярное произведение вида: ${\displaystyle x\cdot y=x_{1}y_{1}\oplus x_{2}y_{2}\oplus ...\oplus x_{n}y_{n}}$. Считаем, что один вызов функции ${\displaystyle f}$ осуществляется за константное время.

Требуется найти ${\displaystyle a}$^[1].

Постановка задачи в квантовой модели похожая, но доступ к оракулу в ней осуществляется не напрямую через функцию ${\displaystyle f}$, а через линейный оператор ${\displaystyle U_{f}}$, действующий на систему из ${\displaystyle n+1}$ кубита:

${\displaystyle U_{f}=\sum _{x\in \{0,1\}^{n},y\in \{0,1\}}|x\rangle \langle x|\otimes |y\oplus f(x)\rangle \langle y|}$,

где ${\displaystyle |x\rangle }$ — кет-вектор, соответствующий квантовому состоянию ${\displaystyle x}$, ${\displaystyle \langle x|}$ — бра-вектор, соответствующий квантовому состоянию ${\displaystyle x}$, ${\displaystyle \otimes }$ — произведение Кронекера, ${\displaystyle \oplus }$ — сложение по модулю 2.

Квантовым состояниям ${\displaystyle 0}$ и ${\displaystyle 1}$ соответствуют векторы ${\textstyle |0\rangle ={\binom {1}{0}}}$ и ${\textstyle |1\rangle ={\binom {0}{1}}}$. Вектор для совместного состояния ${\displaystyle x_{1}x_{2}\dots x_{n}}$ может быть представлен как произведение ${\displaystyle |x_{1}x_{2}\dots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \dots \otimes |x_{n}\rangle }$^[6].

Аналогично классическому случаю, предполагается, что обращение к оракулу, вычисляющему результат применения оператора ${\displaystyle U_{f}}$ к входящей системе из ${\displaystyle n+1}$ кубита, выполняется за константное время.

В квантовом случае, как и в классическом, предполагается, что ${\displaystyle f(x)=a\cdot x}$, и требуется найти ${\displaystyle a}$^[1].

В классическом случае при каждом вызове оракула возвращается один бит числа ${\displaystyle a}$, поэтому чтобы найти ${\displaystyle n}$-битное число ${\displaystyle a}$, нужно вызвать оракул ${\displaystyle n}$ раз. Ниже приведён вариант ${\displaystyle n}$ обращений к оракулу, позволяющих целиком восстановить ${\displaystyle a}$^[1]:

${\displaystyle f(1000...0_{n})=a_{1}}$

${\displaystyle f(0100...0_{n})=a_{2}}$

${\displaystyle \vdots }$

${\displaystyle f(0000...1_{n})=a_{n}}$

Количество обращений к оракулу в классическом случае равно ${\displaystyle O(n)}$, где ${\displaystyle n}$ — количество бит числа ${\displaystyle a}$. Несложными теоретико-информационными рассуждениями можно показать, что эта оценка не улучшаема даже в рамках класса BPP^[1].

В основу алгоритма положен n-кубитный оператор Адамара:

${\textstyle H^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x,y\in \{0,1\}^{n}}{{(-1)}^{x\cdot y}|y\rangle \langle x|}}$

А также тот факт, что применение оператора ${\textstyle U_{f}}$ к состоянию вида ${\textstyle |x\rangle |-\rangle =|x\rangle \otimes |-\rangle }$, где ${\textstyle |-\rangle ={\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$ даёт в результате величину ${\textstyle U_{f}(|x\rangle |-\rangle )=(-1)^{f(x)}|x\rangle |-\rangle }$^[1].

По шагам работа алгоритма может быть представлена следующим образом^[1]:

1. На первом шаге оператор Адамара ${\displaystyle H^{\otimes {(n+1)}}}$ применяется к ${\displaystyle (n+1)}$-кубитному состоянию ${\displaystyle |0\rangle ^{n}|1\rangle }$, состоящего из основного состояния ${\displaystyle |0\rangle ^{n}}$ и вспомогательного бита^[en] ${\displaystyle |1\rangle }$:
   ${\textstyle |0\rangle ^{n}|1\rangle {\xrightarrow {H^{\otimes {(n+1)}}}}{\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x\in \{0,1\}^{n}}|x\rangle |-\rangle }$;
2. Затем к результату предыдущего шага применяется оператор ${\displaystyle U_{f}}$:
   ${\textstyle {\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x\in \{0,1\}^{n}}|x\rangle |-\rangle {\xrightarrow {~U_{f}~}}{\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x\in \{0,1\}^{n}}{(-1)}^{f(x)}|x\rangle |-\rangle }$;
3. После чего к первым ${\displaystyle n}$ кубитам результата применяется ${\displaystyle H^{\otimes (n)}}$, что, с учётом того, что ${\displaystyle f(x)=a\cdot x}$, даёт^[4]:
   ${\textstyle {\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x\in \{0,1\}^{n}}{(-1)}^{a\cdot x}|x\rangle |-\rangle {\xrightarrow {~H^{\otimes (n)}~}}{\frac {1}{2^{n}}}\sum \limits _{x,y\in \{0,1\}^{n}}{(-1)}^{(a\cdot x)\oplus (x\cdot y)}|y\rangle |-\rangle \sim |a\rangle |-\rangle }$.

В результате измерение входного регистра даст значение ${\displaystyle |a\rangle }$^[1]. Таким образом, в квантовой постановке задачи достаточно ${\displaystyle O(1)}$ обращений к оракулу. В общем случае построение и использование оракула требует ${\displaystyle O(4^{n})}$ логических элементов, но это не учитывается при анализе алгоритма в данной модели, так как значимым для неё является только число обращений к оракулу^[1]. Алгоритм в таком виде был реализован на 5- и 16-кубитных компьютерах IBM^[1], также возможно собрать оптическую cистему, реализующую алгоритм^[7].

В любой практической реализации алгоритма Бернштейна — Вазирани основную сложность составляет создание оракула, так как построение и использование оракула требует ${\displaystyle O(4^{n})}$ логических элемента.^[1]

Кроме сложности построения оракула, практической реализации сопутствуют проблемы с точностью. Тестирование системы проводилось на 1-, 2- и 3-битных строках, на которых симулятор IBM-Qiskit^[en] выдавал правильный ответ со 100 % точностью. Затем было проведено тестирование 1- и 2-битных строк на 5-кубитной машине ibmqx4 и 16-кубитной ibmqx5, где были зафиксированы ошибки вычислений и сильное отклонение от ожидаемого результата^[1].

Алгоритм Бернштейна — Вазирани может применяться:

1. В базах данных^[8]. С помощью алгоритма доступ к нужным данным теоретически можно получить значительно быстрее, чем в классическом случае.
2. В атаке на блочный шифр^[9]. Алгоритм Бернштейна — Вазирани предоставляет несколько новых, более совершенных, чем в классическом случае, способов атаки на блочный шифр.
3. В тесте производительности для квантовых компьютеров^[10]. Алгоритм используется в качестве теста производительности для 11-кубитного квантового компьютера.