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

В Алгоритм Бернштейна – Вазирани, который решает Проблема Бернштейна – Вазирани. это квантовый алгоритм изобретен Итан Бернштейн и Умеш Вазирани в 1992 г.^[1] Это ограниченная версия Алгоритм Дойча – Йожи где вместо того, чтобы различать два разных класса функций, он пытается изучить строку, закодированную в функции.^[2] Алгоритм Бернштейна – Вазирани был разработан для доказательства разделение оракула между классы сложности BQP и BPP.^[1]

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Итан Бернштейн и Умеш Вазирани (1997). «Квантовая теория сложности». SIAM Журнал по вычислениям. 26 (5): 1411–1473. Дои:10.1137 / S0097539796300921.
2. С. Д. Фаллек, С. Д. Херольд, Б. Дж. МакМахон, К. М. Маллер, К. Р. Браун и Дж. М. Амини (2016). «Транспортная реализация алгоритма Бернштейна – Вазирани с ионными кубитами». Новый журнал физики. 18. Дои:10.1088 / 1367-2630 / aab341.