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

Алгоритм Бернштейна — Вазирани (англ. Bernstein–Vazirani algorithm) — квантовый алгоритм, решающий задачу нахождения $n$-битного числа (в иностранной литературе также употребляется термин скрытая строка), скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году. Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке. Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров, был реализован на 5- и 16-кубитных квантовых компьютерах IBM.

История

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

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

Постановка задачи Бернштейна — Вазирани

Классическая задача

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

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

Требуется найти $a$.

Квантовая задача

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

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

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

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

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

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

Алгоритм

Классическая задача

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

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

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

$\vdots$

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

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

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

В основу алгоритма положен 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. На первом шаге оператор Адамара $H^{\otimes {(n+1)}}$ применяется к $(n+1)$-кубитному состоянию $|0\rangle ^{n}|1\rangle$, состоящего из основного состояния $|0\rangle ^{n}$ и вспомогательного бита $|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. Затем к результату предыдущего шага применяется оператор $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. После чего к первым $n$ кубитам результата применяется $H^{\otimes (n)}$, что, с учётом того, что $f(x)=a\cdot x$, даёт:
   ${\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 }$.

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

Реализация алгоритма на компьютерах IBM

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

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

Практическое применение

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

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

Ссылки

• Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, Adetokunbo Adedoyin, John Ambrosiano. Quantum Algorithm Implementations for Beginners // arXiv:1804.03719 [quant-ph]. — 2018.
• David Deutsch, Roger Penrose. Quantum theory, the Church–Turing principle and the universal quantum computer (англ.) // Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences. — 1985. — 8 July (vol. 400, iss. 1818). — P. 97–117. — doi:10.1098/rspa.1985.0070.
• Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Strengths and Weaknesses of Quantum Computing (англ.) // SIAM J. Comput.. — 1997. — Vol. 26. — P. 1510–1523. — doi:10.1137/S0097539796300933. — arXiv:quant-ph/9701001.
• Jack D. Hidary. Quantum Computing: An Applied Approach. — Springer International Publishing, 2019. — С. 104—107. — ISBN 978-3030239213. — doi:10.1007/978-3-030-23922-0.