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

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

История

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

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

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

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

Рассмотрим оракул, преобразующий $n$-битное число в один бит, то есть $f:\{0,1{\}}^n\to \{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⟩⟨x|\otimes |y\oplus f(x)⟩⟨y|$,

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

Квантовым состояниям $0$ и $1$ соответствуют векторы $|0⟩=(\genfrac{}{}{0ex}{}{1}{0})$ и $|1⟩=(\genfrac{}{}{0ex}{}{0}{1})$. Вектор для совместного состояния $x_1{x}_2\dots x_n$ может быть представлен как произведение $|x_1{x}_2\dots x_n⟩=|x_1⟩\otimes |x_2⟩\otimes \dots \otimes |x_n⟩$Шаблон:Sfn.

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

$⋮$

$f(0000...1_n)=a_n$

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

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

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

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

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

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

1. На первом шаге оператор Адамара $H^{\otimes (n+1)}$ применяется к $(n+1)$-кубитному состоянию $|0{⟩}^n|1⟩$, состоящего из основного состояния $|0{⟩}^n$ и Шаблон:Не переведено $|1⟩$: Шаблон:Pb $|0{⟩}^n|1⟩\stackrel{H^{\otimes (n+1)}}{\to }\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}|x⟩|-⟩$;
2. Затем к результату предыдущего шага применяется оператор $U_f$: Шаблон:Pb $\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}|x⟩|-⟩\stackrel{U_f}{\to }\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}{(-1)}^{f(x)}|x⟩|-⟩$;
3. После чего к первым $n$ кубитам результата применяется $H^{\otimes (n)}$, что, с учётом того, что $f(x)=a\cdot x$, даёт: Шаблон:Pb $\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}{(-1)}^{a\cdot x}|x⟩|-⟩\stackrel{H^{\otimes (n)}}{\to }\frac{1}{2^n}\sum _{x,y\in \{0,1{\}}^n}{(-1)}^{(a\cdot x)\oplus (x\cdot y)}|y⟩|-⟩\sim |a⟩|-⟩$.

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

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

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

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

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

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

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

Ссылки

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга