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

Алгоритм Бернштейна — Вазирани — квантовый алгоритм, решающий задачу нахождения числа, скрытого в черном ящике. Рассматриваемый алгоритм позволяет ускорить решение классической задачи. Кроме того, он показывает, что $BPP\subseteq BQP$ , где BPP и BQP - классы сложности. Также алгоритм находит своё применение в базах данных, атаке на блочный шифр, тесте производительности для квантовых компьютеров. Существует реализация алгоритма на компьютерах IBM.

История

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

Одной из предпосылок создания алгоритма было установление существования эффективной универсальной квантовой машины Тьюринга. Эта машина существенно сложнее, чем классическая машина Тьюринга. Вообще говоря, квантовые компьютеры были впервые упомянуты Ричардом Фейнманом в 1982 году. В 1985 году, идеи Фейнмана были рассмотрены и формализованы Дойчем , где он описал квантовую машину Тьюринга. Кроме того, Дойч сделал предположение о том, что квантовые компьютеры могут выполнять некоторые вычисления гораздо быстрее, чем классические компьютеры. Сильное продвижение в этом направлении совершил Питер Шор в своей работе в 1994 году, в которой он разработал алгоритм полиномиального времени на квантовом компьютере для простых множителей .

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

Классический случай

Рассмотрим чёрный ящик (который также называется оракулом), преобразующий $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. Кет-вектор $|x\rangle$ равен — $|x\rangle =\alpha |0\rangle +\beta |1\rangle$, где $|0\rangle ={\binom {1}{0}}$ и $|1\rangle ={\binom {0}{1}}$ , $\alpha$ и $\beta$ — такие комплексные числа, что $\alpha ^{2}+\beta ^{2}=1$. Для такого вектора верно, например, следующее выражение — $|x_{1}x_{2}x_{3}\rangle =|x_{1}\rangle |x_{2}\rangle |x_{3}\rangle$.

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

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

Для решения задачи в квантовом случае нужно $O(1)$ обращений к оракулу вместо $O(n)$ в классическом случае, где $n-$ количество бит числа $a$. Вообще говоря, построение и использование оракула требует $O(4^{n})$ логических элемента, но это не учитывается, потому что оракул используется как чёрный ящик и важно только количество обращений к нему.

Алгоритм

Классический случай

Так как в классическом случае при каждом вызове оракула мы находим один бит числа $a$, то для нахождения $n$-битного числа $a$ нужно вызвать оракул $n$ раз.

Ниже приведены вызовы оракула для нахождения каждого бита числа $a$.

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

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

$\vdots$

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

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

Описание алгоритма Бернштейна — Вазирани. Графически схема его работы может быть описана следующей диаграммой:

Схема работы алгоритма

Одной из основных формул математического описания алгоритма является определение 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|}}$

Рассмотрим действие алгоритма:

1. На первом шаге применен оператор Адамара $H^{\otimes {(n+1)}}$ к $n$-кубитному состоянию $|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 \otimes |-\rangle }$.

2. Далее результат первого шага попадает в чёрный ящик.

У оператора $U_{f}$ есть важное свойство — когда на вход оператору подается некоторое состояние, то на выходе оператора появляется функция $f(x)$:

$U_{f}(|x\rangle |-\rangle )=(-1)^{f(x)}|x\rangle |-\rangle$, где $|-\rangle ={\frac {\vert 0\rangle -\vert 1\rangle }{\sqrt {2}}}$

Далее применяем описанное свойство к результату, полученному на первом шаге, и получаем.

${\textstyle {\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x\in \{0,1\}^{n}}{(-1)}^{f(x)}|x\rangle \otimes |-\rangle }$.

3. С учётом того, что $f(x)=a\cdot x$ получаем

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

4. Заключительное преобразование Адамара $H^{\otimes {(n)}}$ применяется к каждому кубиту, в результате чего получаем состояние

${\textstyle {\frac {1}{\sqrt {2^{n}}}}\sum \limits _{x,y\in \{0,1\}^{n}}{(-1)}^{(a\cdot x)\oplus (x\cdot y)}|y\rangle \otimes |-\rangle \equiv |a\rangle \otimes |-\rangle }$.

В результате получаем, что измерение входного регистра даст значение $|a\rangle$

Существует несколько реализаций алгоритма Бернштейна — Вазирани. Например, можно сделать оптическую cистему, реализующую алгоритм Бернштейна — Вазирани. Кроме того, есть реализация алгоритма на 5 и 16 кубитных компьютерах IBM. О сложностях реализации алгоритма на компьютерах IBM написано в следующем подразделе .

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

В любой практической реализации алгоритма Бернштейна — Вазирани основную сложность составляет создание оракула. Как было отмечено в квантовой постановке задачи построение и использование оракула требует $O(4^{n})$ логических элемента. Задача сразу становится достаточно сложной. Для решения проблемы был написан квантовый компилятор списка соединений (Quantum Netlist Compiler). В QNC реализованы специальные функции, дающие дополнительные возможности (например, создание кода Грея для уменьшения количества логических элементов. Это свойство упрощает создание оракула).

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

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

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

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

Существует реализация алгоритма Бернштейна-Вазирани в открытом доступе, выполненная на языке JavaScript.

Ссылки

• Strengths and Weaknesses of Quantum Computing // arXiv:quant-ph/9701001. — 1997-01-01.
• John Preskill. Lecture Notes for Physics 219: Quantum Computation. — 1999-01-01.
• 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-07-08. — Т. 400, вып. 1818. — С. 97–117. — doi:10.1098/rspa.1985.0070.
• Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Strengths and Weaknesses of Quantum Computing // arXiv:quant-ph/9701001. — 1997-01-01.