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

Квантовый алгоритм

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

Постановка проблемы

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

Алгоритм

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

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

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

Применим преобразование Адамара к состоянию кубита, чтобы получить ${\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}$

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

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

• Задача на скрытую линейную функцию

Ссылки

1. Ethan Bernstein и Umesh Vazirani (1997). «Квантовая теория сложности». SIAM Journal on Computing . 26 (5): 1411–1473. doi :10.1137/S0097539796300921.
2. SD Fallek, CD Herold, BJ McMahon, KM Maller, KR Brown и JM Amini (2016). «Транспортная реализация алгоритма Бернштейна–Вазирани с ионными кубитами». New Journal of Physics . 18 . arXiv : 1710.01378 . doi : 10.1088/1367-2630/aab341 .{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. Алок Шукла и Пракаш Ведула (2023). «Обобщение алгоритма Бернштейна--Вазирани с несколькими секретными ключами и вероятностным оракулом». Квантовая обработка информации . 22:244 (6): 1–18. arXiv : 2301.10014 . doi :10.1007/s11128-023-03978-3.