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

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

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

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

Алгоритм

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

${ displaystyle { begin {align} 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} конец {выровнено}}}$

В отличие от классического решения, которое требует как минимум ${ 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 | х rangle to (-1) ^ {f (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 {else}}.}$

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

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

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

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