Algoritmus Bernstein – Vazirani - Bernstein–Vazirani algorithm

The Algoritmus Bernstein – Vazirani, který řeší Bernstein – Vazirani problém je kvantový algoritmus vynalezl Ethan Bernstein a Umesh Vazirani v roce 1992.^[1] Je to omezená verze Algoritmus Deutsch – Jozsa kde se místo rozlišení mezi dvěma různými třídami funkcí pokusí naučit řetězec zakódovaný ve funkci.^[2] Algoritmus Bernstein – Vazirani byl navržen tak, aby dokázal věštecké oddělení mezi třídy složitosti BQP a BPP.^[1]

Problémové prohlášení

Vzhledem k věštec který implementuje funkci ${ displaystyle f colon {0,1 } ^ {n} rightarrow {0,1 }}$ ve kterém ${ displaystyle f (x)}$ je slíbil být Tečkovaný produkt mezi ${ displaystyle x}$ a tajný řetězec ${ displaystyle s in {0,1 } ^ {n}}$ modulo 2, ${ displaystyle f (x) = x cdot s = x_ {1} s_ {1} + x_ {2} s_ {2} + cdots + x_ {n} s_ {n}}$, najít ${ displaystyle s}$.

Algoritmus

Nejúčinnější metodou k nalezení tajného řetězce je klasicky vyhodnocení funkce ${ displaystyle n}$ časy kde ${ displaystyle x = 2 ^ {i}}$, ${ displaystyle i in {0,1, ..., n-1 }}$^[2]

${ displaystyle { begin {zarovnáno} 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} konec {zarovnáno}}}$

Na rozdíl od klasického řešení, které potřebuje minimálně ${ displaystyle n}$ dotazy na funkci k vyhledání ${ displaystyle s}$, pomocí kvantového výpočtu je potřeba pouze jeden dotaz. Kvantový algoritmus je následující: ^[2]

Použijte a Hadamardova transformace do ${ displaystyle n}$ stav qubit ${ displaystyle | 0 rangle ^ { mnohokrát n}}$ dostat

${ displaystyle { frac {1} { sqrt {2 ^ {n}}}} sum _ {x = 0} ^ {2 ^ {n} -1} | x rangle.}$

Dále použijte věštec ${ displaystyle U_ {f}}$ který se transformuje ${ displaystyle | x rangle to (-1) ^ {f (x)} | x rangle}$. To lze simulovat pomocí standardního věštce, který se transformuje ${ displaystyle | b rangle | x rangle to | b oplus f (x) rangle | x rangle}$ aplikací tohoto věštce na ${ displaystyle { frac {| 0 rangle - | 1 rangle} { sqrt {2}}} | x rangle}$. (${ displaystyle oplus}$ označuje přidání mod dva.) Tím se superpozice transformuje do

${ displaystyle { frac {1} { sqrt {2 ^ {n}}}} součet _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} | x rangle.}$

Na každý qubit se aplikuje další Hadamardova transformace, což je tak pro qubits kde ${ displaystyle s_ {i} = 1}$, jeho stav je převeden z ${ displaystyle | - rangle}$ na ${ displaystyle | 1 rangle}$ a pro qubits kde ${ displaystyle s_ {i} = 0}$, jeho stav je převeden z ${ displaystyle | + rangle}$ na ${ displaystyle | 0 rangle}$. Získat ${ displaystyle s}$, měření v standardní základ (${ displaystyle {| 0 rangle, | 1 rangle }}$) se provádí na qubits.

Graficky může být algoritmus znázorněn následujícím diagramem, kde ${ displaystyle H ^ { další krát}}$ označuje Hadamardovu transformaci ${ displaystyle n}$ qubits:

${ 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}}} součet _ {x, y in {0,1 } ^ {n}} (- 1) ^ {f (x) + x cdot y} | y rangle = | s rangle}$

Důvodem je poslední stav ${ displaystyle | s rangle}$ je to proto, že konkrétně ${ displaystyle y}$,

${ displaystyle { frac {1} {2 ^ {n}}} součet _ {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 {jinak}}.}$

Od té doby ${ displaystyle s oplus y = { vec {0}}}$ je pravda pouze tehdy, když ${ displaystyle s = y}$, to znamená, že je zapnuta pouze nenulová amplituda ${ displaystyle | s rangle}$. Takže měření výstupu obvodu ve výpočetní bázi poskytuje tajný řetězec ${ displaystyle s}$.

Viz také

• Problém se skrytou lineární funkcí

Reference