Simonsův problém - Simons problem - Wikipedia

V teorie výpočetní složitosti a kvantové výpočty, Simonův problém je výpočetní problém které lze vyřešit exponenciálně rychleji na a kvantový počítač než na klasickém (nebo tradičním) počítači. Simonův problém zahrnuje použití černé skříňky. Problémy černé skříňky poskytují kvantovým algoritmům výhodu oproti klasickým algoritmům.

Samotný problém má malou praktickou hodnotu, protože existuje jen málo představitelných realistických nastavení, která by vyžadovala řešení Simonova problému. Problém je však stále důležitý, protože je lze prokázat že a kvantový algoritmus může tento problém vyřešit exponenciálně rychleji než jakýkoli známý klasický algoritmus. Toto je první příklad kvantového výpočetního problému, který lze vyřešit v polynomiálním čase na kvantovém počítači.

Problém je nastaven v modelu složitost rozhodovacího stromu nebo složitost dotazu a byla vytvořena Daniel Simon v roce 1994. Simon vystavoval a kvantový algoritmus, obvykle volal Simonův algoritmus, který řeší problém exponenciálně rychleji než jakýkoli deterministický nebo pravděpodobnostní klasický algoritmus, vyžadující exponenciálně kratší výpočetní čas (nebo přesněji dotazy) než nejlepší klasický pravděpodobnostní algoritmus. V Simonově algoritmu je pro kvantový algoritmus zapotřebí spíše lineární počet dotazů než exponenciální počet dotazů, které jsou potřebné pro klasický pravděpodobnostní algoritmus. Tento problém přináší věštecké oddělení mezi třídami složitosti BPP a BQP, na rozdíl od oddělení poskytovaného Algoritmus Deutsch – Jozsa, který odděluje P a EQP. Separace je exponenciální (vzhledem k věštci) mezi kvantovou a omezenou chybou složitosti klasického dotazu. Simonův problém se neprokazuje, spíše ukazuje, že existuje věštec, ve vztahu ke kterému. Věštec použitý v Simonově problému je černá skříňka, kterou bereme v úvahu při výpočtu.

Inspirací byl také Simonův algoritmus Shorův algoritmus. Oba problémy jsou zvláštními případy Abelianů skrytý problém s podskupinou, o kterém je nyní známo, že má efektivní kvantové algoritmy.

Popis problému

Vzhledem k funkci (implementované a Černá skříňka nebo věštce) ${ displaystyle f: {0,1 } ^ {n} pravá šipka {0,1 } ^ {n}}$, slíbil uspokojit vlastnost, že pro některé nenulové ${ displaystyle s in {0,1 } ^ {n}}$ a všechno ${ displaystyle x, y in {0,1 } ^ {n}}$,

${ displaystyle f (x) = f (y)}$ kdyby a jen kdyby ${ displaystyle x oplus y in {0 ^ {n}, s }}$ nebo ${ displaystyle { displaystyle x = y otimes s}}$

Cílem je identifikovat sa a zjistit, zda ${ displaystyle s = 0 ^ {n}}$ nebo ${ displaystyle s neq 0 ^ {n}}$ dotazem f (x).

Tady, ${ displaystyle s = 0 ^ {n}}$ klasifikuje funkci jedna k jedné.

Li ${ displaystyle s neq 0 ^ {n}}$ , funkce je funkce dvou ku jedné taková ${ displaystyle { displaystyle x oplus y in {0 ^ {n}, s }}}$

Jinými slovy, ${ displaystyle f}$ je funkce dvou na jednoho taková ${ displaystyle f (x) = f (x oplus s)}$, pro všechny ${ displaystyle x in {0,1 } ^ {n}}$ kde ${ displaystyle s in {0,1 } ^ {n}}$ není známo.

Fotbalová branka

Je důležité si uvědomit, že cílem Simonova problému je snížit počet dotazů na černou skříňku, abychom mohli určit s exponenciálně rychle.

Příklad

Například pokud ${ displaystyle n = 3}$, pak je následující funkce příkladem funkce, která splňuje požadovanou a právě zmíněnou vlastnost:

${ displaystyle x}$	${ displaystyle f (x)}$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

V tomto případě, ${ displaystyle s = 110}$ (tj. řešení). Lze snadno ověřit, že každý výstup z ${ displaystyle f}$ se vyskytuje dvakrát a dva vstupní řetězce odpovídající libovolnému danému výstupu mají bitový XOR rovný ${ displaystyle s = 110}$.

Například vstupní řetězce ${ displaystyle 010}$ a ${ displaystyle 100}$ jsou oba mapovány (uživatelem ${ displaystyle f}$) na stejný výstupní řetězec ${ displaystyle 000}$. ${ displaystyle { displaystyle f (010) = 000}}$ a ${ displaystyle { displaystyle f (100) = 000}}$. Pokud použijeme XOR na 010 a 100, získáme 110, to znamená ${ displaystyle { displaystyle 010 oplus 100 = 110 = s}.}$${ displaystyle s = 110}$ lze také ověřit pomocí vstupních řetězců 001 a 111, které jsou oba mapovány (pomocí f) na stejný výstupní řetězec 010. Pokud použijeme XOR na 001 a 111, získáme 110, tj. ${ displaystyle 001 oplus 111 = 110 = s}$. To dává stejné řešení ${ displaystyle s = 110}$ jsme vyřešili dříve.

V tomto příkladu je funkce f skutečně funkcí dvou ku jedné, kde ${ displaystyle { displaystyle s neq 0 ^ {n}}}$.

U funkce 1: 1 ${ displaystyle f (x) = f (y)}$ takhle ${ displaystyle f (1) = 1, f (2) = 2, f (3) = 3 atd.}$

Problémová tvrdost

Intuitivně se jedná o velmi těžký problém vyřešit „klasickým“ způsobem, i když člověk používá náhodnost a přijímá malou pravděpodobnost chyby. Intuice za tvrdostí je rozumně jednoduchá: pokud chcete problém vyřešit klasicky, musíte najít dva různé vstupy ${ displaystyle x}$ a ${ displaystyle y}$ pro který ${ displaystyle f (x) = f (y)}$. Ve funkci nemusí být nutně žádná struktura ${ displaystyle f}$ to by nám pomohlo najít dva takové vstupy: konkrétněji můžeme něco objevit ${ displaystyle f}$ (nebo co dělá) pouze tehdy, když pro dva různé vstupy získáme stejný výstup. V každém případě bychom museli hádat ${ displaystyle { displaystyle Omega ({ sqrt {2 ^ {n}}})}}$ různé vstupy, než je pravděpodobné, že najdete pár, na kterém ${ displaystyle f}$ bere stejný výstup podle narozeninový problém. Vzhledem k tomu, klasicky najít s se 100% jistotou by to vyžadovalo kontrolu až ${ displaystyle 2 ^ {n-1} +1}$ vstupů, Simonův problém se snaží najít s použitím méně dotazů než tato klasická metoda.

Přehled Simonova algoritmu

Idea

Myšlenkou na vysoké úrovni za Simonovým algoritmem je „dostatečně dlouho“ zkoumat (nebo „zkoumat“) kvantový obvod (viz obrázek níže) ${ displaystyle n-1}$ (lineárně nezávislé ) n-bitové řetězce, to je

${ displaystyle y_ {1}, y_ {2}, tečky, y_ {n-1} in {0,1 } ^ {n},}$

tak, aby byly splněny následující rovnice

${ displaystyle left {{ begin {zarovnáno} y_ {1} cdot s & = 0 y_ {2} cdot s & = 0 & , , , vdots y_ {n- 1} cdot s & = 0 end {zarovnáno}} vpravo.}$

kde ${ displaystyle y_ {i} cdot s}$ je modulo-2 Tečkovaný produkt; to je ${ displaystyle y_ {i} cdot s = y_ {i1} s_ {1} oplus y_ {i2} s_ {2} oplus dots oplus y_ {in} s_ {n}}$, a ${ displaystyle y_ {ij}, s_ {j} v {0,1 }}$, pro ${ displaystyle i = 1, tečky, n-1}$ a pro ${ displaystyle j = 1, tečky, n}$.

Tento lineární systém tedy obsahuje ${ displaystyle n-1}$ lineární rovnice v ${ displaystyle n}$ neznámé (tj. kousky ${ displaystyle s in {0,1 } ^ {n}}$), a cílem je jej vyřešit za účelem získání ${ displaystyle s}$, a ${ displaystyle s}$ je pevná pro danou funkci ${ displaystyle f}$. Ne vždy existuje (jedinečné) řešení.

Simonův kvantový obvod

Kvantový obvod představující / implementující Simonův algoritmus

Kvantový obvod (viz obrázek) je implementací (a vizualizací) kvantové části Simonova algoritmu.

Nejprve je připraven kvantový stav všech nul (to lze snadno provést). Stát ${ displaystyle | 0 rangle}$ představuje ${ displaystyle | 0 ^ {n} rangle}$ kde ${ displaystyle n}$ je počet qubitů. Polovina tohoto stavu se poté transformuje pomocí Hadamardovy transformace. Výsledek se poté přenese do věštce (neboli „černé skříňky“), který umí počítat ${ displaystyle f}$. Kde ${ displaystyle U_ {f}}$ působí na dva registry jako ${ displaystyle | x rangle | 0 ^ {n} rangle rightarrow | x rangle | f (x) rangle}$. Poté se část výstupu produkovaného věšteckem transformuje pomocí další Hadamardovy transformace. Nakonec je provedeno měření celkového výsledného kvantového stavu. Během tohoto měření získáme n-bitové řetězce, ${ displaystyle y_ {1}, y_ {2}, tečky, y_ {n-1} in {0,1 } ^ {n}}$, zmíněno v předchozím pododdíle.

Simonův algoritmus lze považovat za iterativní algoritmus (který využívá kvantový obvod) následovaný (případně) klasickým algoritmem k nalezení řešení lineárního systému rovnic.

Simonův algoritmus

V této části je podrobně vysvětlena každá část Simonova algoritmu. Může být užitečné podívat se na obrázek Simonova kvantového obvodu výše při čtení každé z následujících podsekcí.

Vstup

Simonův algoritmus začíná vstupem ${ displaystyle | 0 ^ {n} rangle otimes | 0 ^ {n} rangle = | 0 ^ {n} rangle | 0 ^ {n} rangle}$, kde ${ displaystyle | 0 ^ {n} rangle}$ je kvantový stav s ${ displaystyle n}$ nuly.

(Symbol ${ displaystyle otimes}$ je typický symbol používaný k označení tenzorový produkt. Aby nedošlo k přeplnění notace, symbolu ${ displaystyle otimes}$ je někdy vynechán: například v předchozí větě ${ displaystyle | 0 ^ {n} rangle otimes | 0 ^ {n} rangle}$ je ekvivalentní k ${ displaystyle | 0 ^ {n} rangle | 0 ^ {n} rangle}$. V tomto článku se (často) používá k odstranění nejednoznačnosti nebo k předcházení nejasnostem.)

Příklad

Například, pokud ${ displaystyle n = 2}$, pak je počáteční vstup

${ displaystyle | 0 ^ {2} rangle otimes | 0 ^ {2} rangle = | 00 rangle otimes | 00 rangle = (| 0 rangle otimes | 0 rangle) otimes (| 0 rangle otimes | 0 rangle) = | 0 rangle otimes | 0 rangle otimes | 0 rangle otimes | 0 rangle = | 0000 rangle = | 0 ^ {4} rangle = | 0 ^ {2n} rangle}$.

První Hadamardova transformace

Poté se vstup (jak je popsán v předchozí podkapitole) transformuje pomocí a Hadamardova transformace. Konkrétně Hadamardova transformace ${ displaystyle H ^ { další krát}}$ (dále jen tenzorový produkt lze použít i na matice) se použije na první ${ displaystyle n}$ qubits, tedy do „částečného“ stavu ${ displaystyle | 0 ^ {n} rangle}$, takže složený stav po této operaci je

${ displaystyle | Psi rangle = left (H ^ { otimes n} | 0 ^ {n} rangle right) otimes | 0 ^ {n} rangle = left ( sum _ {x v {0,1 } ^ {n}} { frac {1} { sqrt {2 ^ {n}}}} left | x right rangle right) otimes left | 0 ^ { n} right rangle = left ({ frac {1} { sqrt {2 ^ {n}}}} sum _ {x in {0,1 } ^ {n}} left | x right rangle right) otimes left | 0 ^ {n} right rangle = { frac {1} {2 ^ { frac {n} {2}}}} sum _ {x v {0,1 } ^ {n}} left ( left | x right rangle otimes left | 0 ^ {n} right rangle right)}$

kde ${ displaystyle x in {0,1 } ^ {n}}$ označuje libovolný n-bitový řetězec (tj. součet je přes jakýkoli n-bitový řetězec). Termín ${ displaystyle { frac {1} { sqrt {2 ^ {n}}}}}$ lze ze součtu započítat, protože na tom nezávisí ${ displaystyle x}$ (tj. je to konstanta vzhledem k ${ displaystyle x}$), a ${ displaystyle { frac {1} { sqrt {2 ^ {n}}}} = { frac {1} {2 ^ { frac {n} {2}}}}}$.

Příklad

Předpokládejme (znovu) ${ displaystyle n = 2}$, pak je vstup ${ displaystyle | 0000 rangle}$ a Hadamardova transformace ${ displaystyle H ^ { otimes 2}}$ je

${ displaystyle H ^ { otimes 2} = { frac {1} { sqrt {2}}} { begin {bmatrix} 1 & 1 1 & -1 end {bmatrix}} otimes { frac {1 } { sqrt {2}}} { begin {bmatrix} 1 & 1 1 & -1 end {bmatrix}} = { frac {1} { sqrt {2}}} { begin {bmatrix} { frac {1} { sqrt {2}}} { begin {bmatrix} 1 & 1 1 & -1 end {bmatrix}} & { frac {1} { sqrt {2}}} { begin {bmatrix } 1 & 1 1 & -1 end {bmatrix}} { frac {1} { sqrt {2}}} { begin {bmatrix} 1 & 1 1 & -1 end {bmatrix}} & - left ({ frac {1} { sqrt {2}}} { begin {bmatrix} 1 & 1 1 & -1 end {bmatrix}} right) end {bmatrix}} = { frac {1} {2}} { begin {bmatrix} 1 & 1 & 1 & 1 1 & -1 & 1 & -1 1 & 1 & -1 & -1 1 & -1 & -1 & 1 end {bmatrix}}}$

Pokud nyní použijeme ${ displaystyle H ^ { otimes 2}}$ na první ${ displaystyle | 00 rangle}$, tj. státu

${ displaystyle | 00 rangle = { začátek {bmatrix} 1 0 0 0 konec {bmatrix}}}$

získáváme

${ displaystyle { begin {aligned} H ^ { otimes 2} | 00 rangle & = { frac {1} {2}} { begin {bmatrix} 1 & 1 & 1 & 1 1 & -1 & 1 & -1 1 & 1 & - 1 & -1 1 & -1 & -1 & 1 end {bmatrix}} { begin {bmatrix} 1 0 0 0 end {bmatrix}} = { frac {1} {2}} { begin {bmatrix} 1 1 1 1 end {bmatrix}} [6pt] & = { frac {1} {2}} left ({ begin {bmatrix} 1 0 0 0 end {bmatrix}} + { begin {bmatrix} 0 1 0 0 end {bmatrix}} + { begin {bmatrix} 0 0 1 0 end {bmatrix}} + { begin {bmatrix} 0 0 0 1 end {bmatrix}} right) = { frac {1} {2}} left (| 00 rangle + | 01 rangle + | 10 rangle + | 11 rangle right) = { frac {1} {2 ^ {2/2}}} sum _ {x in {0,1 } ^ {2}} vlevo | x vpravo rangle end {zarovnáno}}}$

Abychom získali konečný složený kvantový stav, můžeme nyní tenzorovat součin ${ displaystyle H ^ { otimes 2} | 00 rangle}$ s ${ displaystyle | 00 rangle}$, to je

${ displaystyle { begin {aligned} left (H ^ { otimes 2} | 00 rangle right) otimes | 00 rangle & = left ({ frac {1} {2}} sum _ {x in {0,1 } ^ {2}} left | x right rangle right) otimes | 00 rangle = { frac {1} {2}} left (| 00 rangle + | 01 rangle + | 10 rangle + | 11 rangle right) otimes | 00 rangle [6pt] & = { frac {1} {2}} left (| 00 rangle otimes | 00 rangle + | 01 rangle otimes | 00 rangle + | 10 rangle otimes | 00 rangle + | 11 rangle otimes | 00 rangle right) = { frac {1} {2 }} sum _ {x in {0,1 } ^ {2}} left ( left | x right rangle otimes | 00 rangle right). end {zarovnáno}}}$

Věštec

Potom zavoláme věštbu nebo černou skříňku (${ displaystyle U_ {f}}$ na obrázku výše) pro výpočet funkce ${ displaystyle f}$ na transformovaném vstupu ${ displaystyle | Psi rangle = { frac {1} {2 ^ {n / 2}}} součet _ {x in {0,1 } ^ {n}} left ( left | x right rangle otimes left | 0 ^ {n} right rangle right)}$, získat stát

${ displaystyle | Psi rangle '= { frac {1} {2 ^ {n / 2}}} součet _ {x in {0,1 } ^ {n}} left ( left | x right rangle otimes left | f (x) right rangle right)}$

Druhá Hadamardova transformace

Poté použijeme Hadamardovu transformaci ${ displaystyle H ^ { další krát}}$ do států prvního ${ displaystyle n}$ qubits státu ${ displaystyle | Psi rangle '}$, získat

${ displaystyle { begin {aligned} | Psi rangle '' & = { frac {1} {2 ^ {n / 2}}} sum _ {x in {0,1 } ^ { n}} left ( left (H ^ { otimes n} left | x right rangle right) otimes left | f (x) right rangle right) [4pt] & = { frac {1} {2 ^ {n / 2}}} sum _ {x in {0,1 } ^ {n}} left ( left ({ frac {1} {2 ^ {n / 2}}} sum _ {y in {0,1 } ^ {n}} (- 1) ^ {x cdot y} left | y right rangle right) otimes left | f (x) right rangle right) = { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} left ( sum _ {y in {0,1 } ^ {n}} left ((- 1) ^ {x cdot y} left | y right rangle otimes left | f (x ) right rangle right) right) end {aligned}}}$

kde ${ displaystyle (-1) ^ {x cdot y}}$ může být ${ displaystyle -1}$ nebo ${ displaystyle 1}$, záleží na ${ displaystyle x cdot y = x_ {1} y_ {1} + tečky + x_ {n} y_ {n}}$, kde ${ displaystyle x_ {i}, y_ {i} v {0,1 }}$, pro ${ displaystyle i = 1, tečky, n}$. Například, pokud ${ displaystyle x = 101}$ a ${ displaystyle y = 111}$, pak ${ displaystyle x cdot y = 1 * 1 + 0 * 1 + 1 * 1 = 2}$, což je sudé číslo. V tomto případě tedy ${ displaystyle (-1) ^ {x cdot y} = (- 1) ^ {1 * 1 + 0 * 1 + 1 * 1} = (- 1) ^ {2} = 1}$, a ${ displaystyle {x cdot y}}$ je vždy nezáporné číslo.

Intuici za touto inverzní Hadamardovou transformací, která se zde používá, lze nalézt na Učební poznámky CMU

Pojďme nyní přepsat

${ displaystyle | Psi rangle '' = { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} left ( sum _ {y in {0,1 } ^ {n}} left ((- 1) ^ {x cdot y} left | y right rangle otimes left | f (x) right rangle right) right)}$

jak následuje

${ displaystyle | Psi rangle '' = součet _ {y in {0,1 } ^ {n}} left ( left | y right rangle otimes left ({ frac { 1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} left ((- 1) ^ {x cdot y} left | f (x) right rangle right) right) right)}$

Tato manipulace bude vhodná k pochopení vysvětlení v následujících částech. Pořadí součtů bylo obráceno.

Měření

Po provedení všech dříve popsaných operací se na konci obvodu a měření se provádí.

Nyní existují dva možné případy, které musíme zvážit samostatně

• ${ displaystyle x oplus y = 0 ^ {n}}$ nebo
• ${ displaystyle x oplus y = s}$, kde ${ displaystyle s neq 0 ^ {n}}$.

První případ

Nejprve analyzujme (speciální) případ ${ displaystyle x oplus y = 0 ^ {n}}$, což znamená, že ${ displaystyle f}$ je (podle požadavku) a jedna ku jedné funkce (jak je vysvětleno výše v „popisu problému“).

Mějte na paměti, že kvantový stav před měřením je

${ displaystyle sum _ {y v {0,1 } ^ {n}} vlevo | y vpravo rangle otimes vlevo ({ frac {1} {2 ^ {n}}} součet _ {x in {0,1 } ^ {n}} left ((- 1) ^ {x cdot y} left | f (x) right rangle right) right)}$

Nyní pravděpodobnost, že výsledky měření budou v každém řetězci ${ displaystyle y in {0,1 } ^ {n}}$ je

${ displaystyle p_ {y} = {{ Bigg |} { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} vlevo ((-1) ^ {x cdot y} left | f (x) right rangle right) { Bigg |}} ^ {2} = { frac {1} {2 ^ {n} }}}$

To vyplývá z

${ displaystyle {{ Bigg |} { frac {1} {2 ^ {n}}} součet _ {x v {0,1 } ^ {n}} vlevo ((- 1) ^ {x cdot y} left | f (x) right rangle right) { Bigg |}} ^ {2} = {{ Bigg |} { frac {1} {2 ^ { n}}} sum _ {x in {0,1 } ^ {n}} left ((- 1) ^ {x cdot y} left | x right rangle right) { Bigg |}} ^ {2}}$

protože dva vektory se liší pouze v pořadí jejich záznamů, vzhledem k tomu ${ displaystyle f}$ je jedna ku jedné.

Hodnota pravé strany, to znamená

${ displaystyle {{ Bigg |} { frac {1} {2 ^ {n}}} součet _ {x v {0,1 } ^ {n}} vlevo ((- 1) ^ {x cdot y} vlevo | x vpravo rangle vpravo) { Bigg |}} ^ {2}}$

je snáze vidět ${ displaystyle { frac {1} {2 ^ {n}}}}$.

Takže kdy ${ displaystyle x oplus y = 0 ^ {n}}$, výsledek je prostě a rovnoměrně rozloženo ${ displaystyle n}$-bitový řetězec.

Druhý případ

Pojďme nyní analyzovat případ ${ displaystyle x oplus y = s}$, kde ${ displaystyle s neq 0 ^ {n}}$. V tomto případě, ${ displaystyle f}$ je funkce dvou na jednoho, to znamená, že existují dva vstupy, které se mapují na stejný výstup ${ displaystyle f}$.

Analýza provedená v prvním případě je stále platná pro tento druhý případ, tj. Pravděpodobnost měření daného řetězce ${ displaystyle y in {0,1 } ^ {n}}$ stále lze reprezentovat jako

${ displaystyle p_ {y} = {{ Bigg |} { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} vlevo ((-1) ^ {x cdot y} left | f (x) right rangle right) { Bigg |}} ^ {2}}$

V tomto druhém případě však stále musíme zjistit, o jakou hodnotu jde ${ displaystyle p_ {y}}$ je. Podívejme se proč v následujících vysvětleních.

Nechat ${ displaystyle A = f ( {0,1 } ^ {n})}$, obraz uživatele ${ displaystyle f}$. Nechat ${ displaystyle z v A}$ (tj. ${ displaystyle z}$ je nějaký výstup funkce ${ displaystyle f}$), pak pro každého ${ displaystyle x_ {1} v {0,1 } ^ {n}}$, existuje jeden (a pouze jeden) ${ displaystyle x_ {2} in {0,1 } ^ {n}}$, takový, že ${ displaystyle f (x_ {1}) = f (x_ {2}) = z}$; navíc máme také ${ displaystyle x_ {1} oplus x_ {2} = s}$, což odpovídá ${ displaystyle x_ {2} = s oplus x_ {1}}$ (přehled tohoto konceptu naleznete výše v části „popis problému“).

Proto máme

${ displaystyle p_ {y} = {{ Bigg |} { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} vlevo ((-1) ^ {x cdot y} left | f (x) right rangle right) { Bigg |}} ^ {2} = {{ Bigg |} { frac {1 } {2 ^ {n}}} součet _ {z v A} vlevo (((- 1) ^ {x_ {1} cdot y} + (- 1) ^ {x_ {2} cdot y }) left | z right rangle right) { Bigg |}} ^ {2}}$

Vzhledem k tomu ${ displaystyle x_ {2} = s oplus x_ {1}}$, pak můžeme přepsat koeficient ${ displaystyle (-1) ^ {x_ {1} cdot y} + (- 1) ^ {x_ {2} cdot y}}$ jak následuje

${ displaystyle (-1) ^ {x_ {1} cdot y} + (- 1) ^ {x_ {2} cdot y} = (- 1) ^ {x_ {1} cdot y} + (- 1) ^ {(x_ {1} oplus s) cdot y}}$

Vzhledem k tomu ${ displaystyle (x_ {1} oplus s) cdot y = (x_ {1} cdot y) oplus (s cdot y)}$, pak můžeme dále napsat výše uvedený výraz jako

${ displaystyle (-1) ^ {x_ {1} cdot y} (1 + (- 1) ^ {y cdot s})}$

Tak, ${ displaystyle p_ {y}}$ lze dále psát jako

${ displaystyle p_ {y} = {{ Bigg |} { frac {1} {2 ^ {n}}} součet _ {z v A} vlevo ((- 1) ^ {x_ {1 } cdot y} (1 + (- 1) ^ {y cdot s}) left | z right rangle right) { Bigg |}} ^ {2}}$

Liché číslo

Teď když ${ displaystyle y cdot s = y_ {1} s_ {1} + tečky + y_ {n} s_ {n}}$ je tedy liché číslo ${ displaystyle (-1) ^ {y cdot s} = - 1}$. V tom případě,

${ displaystyle (-1) ^ {x_ {1} cdot y} (1 + (- 1) ^ {y cdot s}) = (- 1) ^ {x_ {1} cdot y} (1- 1) = 0}$

V důsledku toho máme

${ displaystyle p_ {y} = {{ Bigg |} { frac {1} {2 ^ {n}}} součet _ {z v A} vlevo ((- 1) ^ {x_ {1 } cdot y} (1 + (- 1) ^ {y cdot s}) left | z right rangle right) { Bigg |}} ^ {2} = 0}$

Vzhledem k tomu ${ displaystyle p_ {y} = 0}$, pak nikdy nemáme tento případ, tedy žádný řetězec ${ displaystyle y in {0,1 } ^ {n}}$ je v tomto případě vidět (po měření).

(To je případ, kdy máme ničivé rušení.)

Sudé číslo

Pokud místo toho ${ displaystyle y cdot s}$ je sudé číslo (např. nula) ${ displaystyle (-1) ^ {y cdot s} = 1}$. V tom případě,

${ displaystyle (-1) ^ {x_ {1} cdot y} (1 + (- 1) ^ {y cdot s}) = (- 1) ^ {x_ {1} cdot y} 2}$

Takže máme

${ displaystyle p_ {y} = {{ Bigg |} { frac {1} {2 ^ {n}}} součet _ {z v A} vlevo ((- 1) ^ {x_ {1 } cdot y} (2) left | z right rangle right) { Bigg |}} ^ {2} = {{ Bigg |} { frac {2} {2 ^ {n} }} sum _ {z v A} left ((- 1) ^ {x_ {1} cdot y} left | z right rangle right) { Bigg |}} ^ {2} = {{ Bigg |} { frac {1} {2 ^ {n-1}}} sum _ {z in A} left ((- 1) ^ {x_ {1} cdot y} left | z right rangle right) { Bigg |}} ^ {2}}$

Je případ konstruktivní interference,

${ displaystyle { frac {2} {2 ^ {n}}} = 2 * 2 ^ {- n} = 2 ^ {1} * 2 ^ {- n} = 2 ^ {- n + 1} = 2 ^ {- (n-1)} = { frac {1} {2 ^ {n-1}}}}$Stručně řečeno, pro tento druhý případ máme následující pravděpodobnosti

${ displaystyle p_ {y} = {{ Bigg |} { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} vlevo ((-1) ^ {x cdot y} left | f (x) right rangle right) { Bigg |}} ^ {2} = { begin {cases} { frac {1} {2 ^ {n-1}}} & quad { text {if}} y cdot s { text {je sudý}} 0 & quad { text {if}} y cdot s { text {is odd}} end {cases}}}$

Klasické následné zpracování

Když spustíme obvod (operace) výše, existují dva případy:

• v (zvláštním) případě, kdy ${ displaystyle x oplus y = 0 ^ {n}}$, výsledky měření v každém řetězci ${ displaystyle y in {0,1 } ^ {n}}$ s pravděpodobností ${ displaystyle p_ {y} = { frac {1} {2 ^ {n}}}}$

• v případě ${ displaystyle x oplus y = s}$ (kde ${ displaystyle s neq 0 ^ {n}}$), pravděpodobnost získání každého řetězce ${ displaystyle y in {0,1 } ^ {n}}$ darováno

${ displaystyle p_ {y} = { begin {cases} { frac {1} {2 ^ {n-1}}} & quad { text {if}} y cdot s { text {je sudý }} 0 & quad { text {if}} y cdot s { text {je liché}} end {případy}}}$

V obou případech tedy měření vyústí v nějaký řetězec ${ displaystyle y in {0,1 } ^ {n}}$ to uspokojuje ${ displaystyle s cdot y = 0}$a distribuce je jednotný přes všechny řetězce, které splňují toto omezení.

Je to dostatek informací k určení ${ displaystyle s}$? Odpověď je „ano“ za předpokladu, že se postup (výše) několikrát opakuje (a je přijata malá pravděpodobnost selhání). Konkrétně, pokud je spuštěn výše uvedený proces ${ displaystyle n-1}$ krát dostáváme ${ displaystyle n-1}$ struny ${ displaystyle y_ {1}, y_ {2}, tečky, y_ {n-1} in {0,1 } ^ {n}}$, takový, že

${ displaystyle { begin {cases} y_ {1} cdot s & = 0 y_ {2} cdot s & = 0 & vdots y_ {n-1} cdot s & = 0 end { případy}}}$

Toto je systém ${ displaystyle n-1}$ lineární rovnice v ${ displaystyle n}$ neznámé (tj. kousky ${ displaystyle s}$) a cílem je jeho dosažení k dosažení ${ displaystyle s}$. Všimněte si, že každý z ${ displaystyle y_ {1}, y_ {2}, tečky, y_ {n-1} in {0,1 } ^ {n}}$ které získáme po každém měření (pro každé „kolo“ procesu) je samozřejmě výsledkem měření, takže je známo (na konci každého „kola“).

Dostaneme pouze jedinečné nenulové řešení ${ displaystyle s}$ pokud máme "štěstí" a ${ displaystyle y_ {1}, y_ {2}, tečky, y_ {n-1} in {0,1 } ^ {n}}$ jsou lineárně nezávislé. Pravděpodobnost, že ${ displaystyle y_ {1}, y_ {2}, tečky, y_ {n-1}}$ jsou lineárně nezávislé alespoň

${ displaystyle prod _ {k = 1} ^ { infty} left (1 - { frac {1} {2 ^ {k}}} right) = 0,288788 dots> { frac {1} { 4}}}$

Pokud máme lineární nezávislost, můžeme vyřešit systém a získat kandidátní řešení ${ displaystyle s ' neq 0 ^ {n}}$ a otestujte to ${ displaystyle f (0 ^ {n}) = f (s ')}$. Li ${ displaystyle f (0 ^ {n}) = f (s ')}$, víme, že ${ displaystyle s = s '}$a problém byl vyřešen. Li ${ displaystyle f (0 ^ {n}) neq f (s ')}$, to musí být ono ${ displaystyle s = 0 ^ {n}}$ (protože kdyby tomu tak nebylo, jedinečné nenulové řešení lineárních rovnic by bylo ${ displaystyle s}$). Ať tak či onak, jakmile budeme mít lineární nezávislost, můžeme problém vyřešit.

Složitost

Simonův algoritmus vyžaduje ${ displaystyle O (n)}$ dotazy na černou skříňku, zatímco klasický algoritmus by potřeboval alespoň ${ displaystyle Omega (2 ^ {n / 2})}$ dotazy. Je také známo, že Simonův algoritmus je optimální v tom smyslu žádný Kvantový algoritmus k řešení tohoto problému vyžaduje ${ displaystyle Omega (n)}$ dotazy.^[1][2]

Viz také

• Algoritmus Deutsch – Jozsa

Reference