Groverio algoritmas

Groverio algoritmas (Šablonas:En) yra kvantinis algoritmas skirtas ieškojimui nestrukturizuotoje (nesutvarkytoje) duomenų bazėje su N kintamųjų per O($\sqrt{N}$) laiką ir užimantis $O({\log }_{2}N)=O(n)$ saugojimo vietos. Algoritmas buvo sugalvotas L. Groverio (Lov Grover) 1996 m.

Klasiškai, ieškant nesutvarkytoje duomenų bazėje reikia linijinio ieškojimo per O(N/2) laiką. Groverio algoritmas kuris užima O(N^1/2) laiko, yra greičiausias įmanomas algoritmas skirtas ieškojimui nesutvarkytoje duomenų bazėje. Jis suteikia tik kvadratinį pagreitėjimą, skirtingai nuo kitų kvantinių algoritmų, kurie gali suteikti eksponentinį paspartėjimą, nei jų klasikiniai atitikmenys. Tikimybė, kad atsakymas bus klaidingas yra 1/N, kur N yra duomenų bazę sudarančių elementų sveikas skaičius. N=2ⁿ, kur n kubitų skaičius.

Groverio Iteracija

$|O⟩=|0⟩|0⟩...|0⟩=|00...0⟩.$

$|\psi ⟩=H|0⟩H|0⟩H|0⟩H|0⟩...H|0⟩H|0⟩=H^n|O⟩.$

Vartai M, kurie naudojami po Hadamardo vartų:

$M=1-2|t⟩⟨t|;$

$M|\psi ⟩=(1-2|t⟩⟨t|)|\psi ⟩=|\psi ⟩-\frac{2}{\sqrt{2^n}}|t⟩=|\psi ⟩-\frac{2}{\sqrt{N}}|t⟩,$

$⟨t|\psi ⟩=\frac{1}{\sqrt{2^n}}$

kur t yra ieškomas elementas, o n yra kubitų skaičius.

Per vartus B pereina visi kubitai išskyrus paskutinį.

$B=2|\psi ⟩⟨\psi |-1$,

$B(|\psi ⟩-\frac{2}{\sqrt{N}}|t⟩)=(2|\psi ⟩⟨\psi |-1)(|\psi ⟩-\frac{2}{\sqrt{N}}|t⟩)=2|\psi ⟩⟨\psi |\psi ⟩-|\psi ⟩-\frac{4}{\sqrt{N}}|\psi ⟩⟨\psi |t⟩+\frac{2}{\sqrt{N}}|t⟩=$.

$=2|\psi ⟩-|\psi ⟩-\frac{4}{\sqrt{N}}\cdot \frac{1}{\sqrt{N}}|\psi ⟩+\frac{2}{\sqrt{N}}|t⟩=|\psi ⟩-\frac{4}{N}|\psi ⟩+\frac{2}{\sqrt{N}}|t⟩=\frac{N-4}{N}|\psi ⟩+\frac{2}{\sqrt{N}}|t⟩$,

kur $⟨\psi |\psi ⟩=1,$

$⟨\psi |t⟩=\frac{1}{\sqrt{2^n}}.$

Pavyzdžiui, t=|1001>:

$⟨1001|\psi ⟩=\frac{1}{\sqrt{2^4}}.$

$⟨t|t⟩=⟨1001|1001⟩=1.$

$⟨t|x⟩=⟨1001|1000⟩=0.$

$B=H(2|O⟩⟨O|-1)H=(2H|O⟩⟨O|-H)H=2H|O⟩⟨O|H-HH=2|\psi ⟩⟨\psi |-1.$

Groverio iteracija G:

$G=BM=(2|\psi ⟩⟨\psi |-1)(1-2|t⟩⟨t|).$

Operatorius M ir B reikia kartoti tiek kartų kiek reikia Groverio iteracijų, kol bus gautas teisingas atsakymas.

HH=1; MM=1; BB=1;

$(2|O⟩⟨O|-1)(2|O⟩⟨O|-1)=4|O⟩⟨O|O⟩⟨O|-2|O⟩⟨O|-2|O⟩⟨O|+1=4|O⟩⟨O|-4|O⟩⟨O|+1=1.$

Groverio Iteracija su 5 kubitais (N=16)

Tarkime turime ant įėjimo 5 kubitus. Pirmi 4 kubitai yra 0 būsenoje, o penktas kubitas yra 1 busenoje. Pirmi keturi kubitai yra skaičius n, kuris praėjes pro H tampa 2ⁿ. Visus 5 kubitus praleidžiame pro Hadamardo vartus.

t=1, $|\psi ⟩H|1⟩=H|0⟩H|0⟩H|0⟩H|0⟩H|1⟩=\frac{1}{4}(|0⟩+|1⟩)(|0⟩+|1⟩)(|0⟩+|1⟩)(|0⟩+|1⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=$

$=\frac{1}{4}(|0000⟩+|0010⟩+|0001⟩+|0011⟩+|1000⟩+|1010⟩+|1001⟩+|1011⟩+$

$+|0100⟩+|0110⟩+|0101⟩+|0111⟩+|1100⟩+|1110⟩+|1101⟩+|1111⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=|\psi ⟩\frac{1}{\sqrt{2}}(|0⟩-|1⟩).$ Orakulas M:

$M=1-2|t⟩⟨t|=1-2|1001⟩⟨1001|.$

$M|\psi ⟩=|\psi ⟩-\frac{2}{\sqrt{2^n}}|t⟩=|\psi ⟩-\frac{2}{\sqrt{2^4}}|1001⟩,$

kur t yra ieškoma būsena. Tarkime, mes ieškome |1001> busenos. Tada perėjus per orakulą M |1001> busena bus pažymėta ženklu minus, jos amplitudė pasidarys neigiama:

t=2,

$M|\psi ⟩\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=(1-2|1001⟩⟨1001|)|\psi ⟩\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=(|\psi ⟩-2|1001⟩⟨1001|\psi ⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=$

$=(|\psi ⟩-\frac{2}{\sqrt{2^4}}|1001⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=(|\psi ⟩-\frac{1}{2}|1001⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=$

$=(\frac{1}{4}(|0000⟩+|0010⟩+|0001⟩+|0011⟩+|1000⟩+|1010⟩+|1001⟩+|1011⟩+$

$+|0100⟩+|0110⟩+|0101⟩+|0111⟩+|1100⟩+|1110⟩+|1101⟩+|1111⟩))-\frac{1}{2}|1001⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=$

$=\frac{1}{4}(|0000⟩+|0010⟩+|0001⟩+|0011⟩+|1000⟩+|1010⟩-|1001⟩+|1011⟩+$

$+|0100⟩+|0110⟩+|0101⟩+|0111⟩+|1100⟩+|1110⟩+|1101⟩+|1111⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩).$

Toliau Praleidžiame tik pirmus 4 kubitus pro B vartus:

t=3, $B(|\psi ⟩-\frac{1}{2}|1001⟩)=(2|\psi ⟩⟨\psi |-1)(|\psi ⟩-\frac{1}{2}|1001⟩)=2|\psi ⟩⟨\psi |\psi ⟩-|\psi ⟩-\frac{2}{2}|\psi ⟩⟨\psi |1001⟩+\frac{1}{2}|1001⟩=$

$=2|\psi ⟩-|\psi ⟩-|\psi ⟩\frac{1}{\sqrt{2^4}}+\frac{1}{2}|1001⟩=|\psi ⟩-\frac{1}{4}|\psi ⟩+\frac{1}{2}|1001⟩=\frac{3}{4}|\psi ⟩+\frac{1}{2}|1001⟩=$

$=\frac{1}{16}(3|0000⟩+3|0010⟩+3|0001⟩+3|0011⟩+3|1000⟩+3|1010⟩+3|1001⟩+3|1011⟩+$

$+3|0100⟩+3|0110⟩+3|0101⟩+3|0111⟩+3|1100⟩+3|1110⟩+3|1101⟩+3|1111⟩)+\frac{1}{2}|1001⟩=$

$=\frac{1}{16}(3|0000⟩+3|0010⟩+3|0001⟩+3|0011⟩+3|1000⟩+3|1010⟩+11|1001⟩+3|1011⟩+$

$+3|0100⟩+3|0110⟩+3|0101⟩+3|0111⟩+3|1100⟩+3|1110⟩+3|1101⟩+3|1111⟩).$

Kaip matome po perėjimo per B vartus, ieškomo elemento amplitudė pakilo ir sudaro $\frac{11}{16}$, o visų kitų elementų amplitudės yra $\frac{3}{16}$.

$15(\frac{3}{16}{)}^2+(\frac{11}{16}{)}^2=1.$

Tai reiškia, kad tikimybė išmatuoti |1001> yra (11/16)²=0.47265625 arba ~47 %.

Toliau vėl praleidžiame visus 5 kubitus pro orakulą M (penktas kubitas neparodytas, nes skaičiavimuose jis nieko nekeičia):

t=4, $M(\frac{3}{4}|\psi ⟩+\frac{1}{2}|1001⟩)=(1-2|1001⟩⟨1001|)(\frac{3}{4}|\psi ⟩+\frac{1}{2}|1001⟩)=$

$=\frac{3}{4}|\psi ⟩-\frac{6}{4}|1001⟩⟨1001|\psi ⟩+\frac{1}{2}|1001⟩-\frac{2}{2}|1001⟩⟨1001|1001⟩=$

$=\frac{3}{4}|\psi ⟩-\frac{3}{2}|1001⟩\frac{1}{\sqrt{2^4}}+\frac{1}{2}|1001⟩-|1001⟩=\frac{3}{4}|\psi ⟩-\frac{3}{2}|1001⟩\frac{1}{4}-\frac{1}{2}|1001⟩=$

$=\frac{3}{4}|\psi ⟩-\frac{3}{8}|1001⟩-\frac{1}{2}|1001⟩=\frac{3}{4}|\psi ⟩-\frac{7}{8}|1001⟩=$

$=\frac{1}{16}(3|0000⟩+3|0010⟩+3|0001⟩+3|0011⟩+3|1000⟩+3|1010⟩-11|1001⟩+3|1011⟩+$

$+3|0100⟩+3|0110⟩+3|0101⟩+3|0111⟩+3|1100⟩+3|1110⟩+3|1101⟩+3|1111⟩).$

$15(\frac{3}{4}\frac{1}{4}{)}^2+(\frac{3}{16}-\frac{7}{8}{)}^2=1.$

Toliau pirmus 4 kubitus praleidžiame pro B vartus:

t=5,

$B(\frac{3}{4}|\psi ⟩-\frac{7}{8}|1001⟩)=(2|\psi ⟩⟨\psi |-1)(\frac{3}{4}|\psi ⟩-\frac{7}{8}|1001⟩)=\frac{3}{2}|\psi ⟩⟨\psi |\psi ⟩-\frac{3}{4}|\psi ⟩-\frac{7}{4}|\psi ⟩⟨\psi |1001⟩+\frac{7}{8}|1001⟩=$

$=\frac{3}{2}|\psi ⟩-\frac{3}{4}|\psi ⟩-\frac{7}{4}|\psi ⟩\frac{1}{\sqrt{2^4}}+\frac{7}{8}|1001⟩=\frac{3}{4}|\psi ⟩-\frac{7}{4}|\psi ⟩\frac{1}{4}+\frac{7}{8}|1001⟩=\frac{3}{4}|\psi ⟩-\frac{7}{16}|\psi ⟩+\frac{7}{8}|1001⟩=$

$=\frac{5}{16}|\psi ⟩+\frac{7}{8}|1001⟩$

Tikimybė dabar išmatuoti |1001> yra $(\frac{5}{16}\cdot \frac{1}{4}+\frac{7}{8}{)}^2=(\frac{5}{64}+\frac{7}{8}{)}^2=(\frac{5+7\cdot 8}{64}{)}^2=(\frac{61}{64}{)}^2\approx 0.91$ arba ~91 %.

$15(\frac{5}{16}\cdot \frac{1}{4}{)}^2+(\frac{61}{64}{)}^2=1.$

Kadangi n=4, o N=2ⁿ=2⁴=16, tai pagal idėja reikia padaryti $\sqrt{16}=4$ Groverio Iteracijas G. O dabar kol kas padarytos tik dvi groverio iteracijos. Taigi, toliau praleidžiame visus kubitus pro M vartus:

t=6, $M(\frac{5}{16}|\psi ⟩+\frac{7}{8}|1001⟩)=(1-2|1001⟩⟨1001|)(\frac{5}{16}|\psi ⟩+\frac{7}{8}|1001⟩)=$

$=\frac{5}{16}|\psi ⟩-\frac{5}{8}|1001⟩⟨1001|\psi ⟩+\frac{7}{8}|1001⟩-\frac{7}{4}|1001⟩⟨1001|1001⟩=$

$=\frac{5}{16}|\psi ⟩-\frac{5}{8}|1001⟩\frac{1}{4}+\frac{7}{8}|1001⟩-\frac{7}{4}|1001⟩=\frac{5}{16}|\psi ⟩-\frac{5}{32}|1001⟩-\frac{7}{8}|1001⟩=$

$=\frac{5}{16}|\psi ⟩+\frac{-5-7\cdot 4}{32}|1001⟩=\frac{5}{16}|\psi ⟩-\frac{33}{32}|1001⟩.$

Toliau praleidžiame pirmus keturis kubitus pro B vartus:

t=7, $B(\frac{5}{16}|\psi ⟩-\frac{33}{32}|1001⟩)=(2|\psi ⟩⟨\psi |-1)(\frac{5}{16}|\psi ⟩-\frac{33}{32}|1001⟩)=$

$=\frac{5}{8}|\psi ⟩⟨\psi |\psi ⟩-\frac{5}{16}|\psi ⟩-\frac{33}{16}|\psi ⟩⟨\psi |1001⟩+\frac{33}{32}|1001⟩=\frac{5}{8}|\psi ⟩-\frac{5}{16}|\psi ⟩-\frac{33}{16}|\psi ⟩\frac{1}{4}+\frac{33}{32}|1001⟩=$

$=\frac{5}{16}|\psi ⟩-\frac{33}{64}|\psi ⟩+\frac{33}{32}|1001⟩=\frac{5\cdot 4-33}{64}|\psi ⟩+\frac{33}{32}|1001⟩=-\frac{13}{64}|\psi ⟩+\frac{33}{32}|1001⟩.$

Tikimybė išmatuoti |1001> yra $(-\frac{13}{64}\cdot \frac{1}{4}+\frac{33}{32}{)}^2=(-\frac{13}{256}+\frac{33}{32}{)}^2=(\frac{-13+33\cdot 8}{256}{)}^2=(\frac{251}{256}{)}^2=\frac{63001}{65536}\approx 0.961$ arba ~96.1 %.

Toliau praleidžiame visus kubitus pro M vartus:

t=8, $M(-\frac{13}{64}|\psi ⟩+\frac{33}{32}|1001⟩)=(1-2|1001⟩⟨1001|)(-\frac{13}{64}|\psi ⟩+\frac{33}{32}|1001⟩)=$

$=-\frac{13}{64}|\psi ⟩+\frac{13}{32}|1001⟩⟨1001|\psi ⟩+\frac{33}{32}|1001⟩-\frac{33}{16}|1001⟩⟨1001|1001⟩=$

$=-\frac{13}{64}|\psi ⟩+\frac{13}{32}|1001⟩\frac{1}{4}+\frac{33}{32}|1001⟩-\frac{33}{16}|1001⟩=-\frac{13}{64}|\psi ⟩+\frac{13}{128}|1001⟩-\frac{33}{32}|1001⟩=$

$=-\frac{13}{64}|\psi ⟩+\frac{13-33\cdot 4}{128}|1001⟩=-\frac{13}{64}|\psi ⟩-\frac{119}{128}|1001⟩.$

Toliau praleidžiame pirmus keturis kubitus pro B vartus:

t=9, $B(-\frac{13}{64}|\psi ⟩-\frac{119}{128}|1001⟩)=(2|\psi ⟩⟨\psi |-1)(-\frac{13}{64}|\psi ⟩-\frac{119}{128}|1001⟩)=$

$=-\frac{13}{32}|\psi ⟩⟨\psi |\psi ⟩+\frac{13}{64}|\psi ⟩-\frac{119}{64}|\psi ⟩⟨\psi |1001⟩+\frac{119}{128}|1001⟩=-\frac{13}{32}|\psi ⟩+\frac{13}{64}|\psi ⟩-\frac{119}{64}|\psi ⟩\frac{1}{4}+\frac{119}{128}|1001⟩=$

$=-\frac{13}{64}|\psi ⟩-\frac{119}{256}|\psi ⟩+\frac{119}{128}|1001⟩=\frac{-13\cdot 4-119}{256}|\psi ⟩+\frac{119}{128}|1001⟩=-\frac{171}{256}|\psi ⟩+\frac{119}{128}|1001⟩.$

Tikimybė išmatuoti |1001> yra $(-\frac{171}{256}\cdot \frac{1}{4}+\frac{119}{128}{)}^2=(-\frac{171}{1024}+\frac{119}{128}{)}^2=(\frac{-171+119\cdot 8}{1024}{)}^2=(\frac{781}{1024}{)}^2=\frac{609961}{1048576}\approx 0.582$ arba ~58.2 %. Kaip matome po ketvirtos groverio iteracijos G=MB, ieškomo elemento (|1001>) aplitudė sumažėjo. Išvada, kad groverio iteracijas reikia nustoti daryti kada visos elementų amplitudės pasidaro neigiamos (-). Na ir bendra amplitude kaip visada lygi 1: $15(\frac{-171}{1024}{)}^2+(\frac{781}{1024}{)}^2=1.$

Groverio algoritmas kai N=8

Turime 4 kubitus, tris pirmi kubitai yra nuliai, o ketvirtas vienetas. Praleidžiame juos visus pro Hadamardo vartus:

t=1, $|\psi ⟩H|1⟩=H|0⟩H|0⟩H|0⟩H|1⟩=\frac{1}{\sqrt{2^3}}(|0⟩+|1⟩)(|0⟩+|1⟩)(|0⟩+|1⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=$

$=\frac{1}{2\sqrt{2}}(|000⟩+|001⟩+|011⟩+|111⟩+|100⟩+|110⟩+|101⟩+|010⟩)\frac{1}{\sqrt{2}}(|0⟩-|1⟩).$

Toliau visus 4 kubitus praleidžiame pro M vartus. Ketvirto kubito nerašome nes jis lieka nepakitęs. Tarkime mes ieškome |110>.

t=2,

$M|\psi ⟩=M\frac{1}{2\sqrt{2}}(|000⟩+|001⟩+|011⟩+|111⟩+|100⟩+|110⟩+|101⟩+|010⟩)=(1-2|110⟩⟨110|)|\psi ⟩=$

$=|\psi ⟩-2|110⟩⟨110|\psi ⟩=|\psi ⟩-2|110⟩\frac{1}{\sqrt{2^3}}=|\psi ⟩-2|110⟩\frac{1}{2\sqrt{2}}=|\psi ⟩-\frac{1}{\sqrt{2}}|110⟩=$

$=\frac{1}{2\sqrt{2}}(|000⟩+|001⟩+|011⟩+|111⟩+|100⟩-|110⟩+|101⟩+|010⟩).$

Toliau praleidžiame tik pirmus 3 kubitus pro B vartus:

t=3, $B(|\psi ⟩-\frac{1}{\sqrt{2}}|110⟩)=(2|\psi ⟩⟨\psi |-1)(|\psi ⟩-\frac{1}{\sqrt{2}}|110⟩)=$

$=2|\psi ⟩⟨\psi |\psi ⟩-|\psi ⟩-\frac{2}{\sqrt{2}}|\psi ⟩⟨\psi |110⟩+\frac{1}{\sqrt{2}}|110⟩=$

$=2|\psi ⟩-|\psi ⟩-\frac{2}{\sqrt{2}}|\psi ⟩\frac{1}{2\sqrt{2}}+\frac{1}{\sqrt{2}}|110⟩=$

$=|\psi ⟩-\frac{2}{4}|\psi ⟩+\frac{1}{\sqrt{2}}|110⟩=$

$=\frac{1}{2}|\psi ⟩+\frac{1}{\sqrt{2}}|110⟩.$

$=\frac{1}{2}\cdot \frac{1}{2\sqrt{2}}(|000⟩+|001⟩+|011⟩+|111⟩+|100⟩+|110⟩+|101⟩+|010⟩)+\frac{1}{\sqrt{2}}|110⟩.$

$=\frac{1}{4\sqrt{2}}(|000⟩+|001⟩+|011⟩+|111⟩+|100⟩+5|110⟩+|101⟩+|010⟩).$

Tikimybė išmatuoti |110> yra $(\frac{5}{4\sqrt{2}}{)}^2=\frac{25}{32}=0.78125$ arba apytiksliai 78 %.

$7(\frac{1}{4\sqrt{2}}{)}^2+\frac{25}{32}=7(\frac{1}{32})+\frac{25}{32}=1.$

Po dar vienos groverio iteracijos G=MB, tikimybė išmatuoti |110> bus ~0.945 arba 94.5 %.

Toliau vėl praleisime visus kubitus pro M vartus:

t=4, $M(\frac{1}{2}|\psi ⟩+\frac{1}{\sqrt{2}}|110⟩)=(1-2|110⟩⟨110|)(\frac{1}{2}|\psi ⟩+\frac{1}{\sqrt{2}}|110⟩)=$

$=\frac{1}{2}|\psi ⟩-\frac{2}{2}|110⟩⟨110|\psi ⟩+\frac{1}{\sqrt{2}}|110⟩-\frac{2}{\sqrt{2}}|110⟩⟨110|110⟩=\frac{1}{2}|\psi ⟩-\frac{1}{2\sqrt{2}}|110⟩+\frac{1}{\sqrt{2}}|110⟩-\frac{2}{\sqrt{2}}|110⟩=$

$=\frac{1}{2}|\psi ⟩+\frac{-|110⟩+2|110⟩-4|110⟩}{2\sqrt{2}}=\frac{1}{2}|\psi ⟩-\frac{3|110⟩}{2\sqrt{2}}.$

Toliau praleisime tris pirmus kubitus pro B vartus:

t=5, $B(\frac{1}{2}|\psi ⟩-\frac{3|110⟩}{2\sqrt{2}})=(2|\psi ⟩⟨\psi |-1)(\frac{1}{2}|\psi ⟩-\frac{3|110⟩}{2\sqrt{2}})=$

$=|\psi ⟩⟨\psi |\psi ⟩-\frac{1}{2}|\psi ⟩-\frac{3}{\sqrt{2}}|\psi ⟩⟨\psi |110⟩+\frac{3}{2\sqrt{2}}|110⟩=|\psi ⟩-\frac{1}{2}|\psi ⟩-\frac{3}{\sqrt{2}}\cdot \frac{1}{2\sqrt{2}}|\psi ⟩+\frac{3}{2\sqrt{2}}|110⟩=$

$=\frac{4|\psi ⟩-2|\psi ⟩-3|\psi ⟩}{4}+\frac{3}{2\sqrt{2}}|110⟩=-\frac{1}{4}|\psi ⟩+\frac{3}{2\sqrt{2}}|110⟩.$

Tikimybė išmatuoti ieškomą buseną (|110>) yra:

$(-\frac{1}{4}\cdot \frac{1}{2\sqrt{2}}+\frac{3}{2\sqrt{2}}{)}^2=(-\frac{1}{8\sqrt{2}}+\frac{3}{2\sqrt{2}}{)}^2=(\frac{-1+3\cdot 4}{8\sqrt{2}}{)}^2=(\frac{11}{8\sqrt{2}}{)}^2=0.9453125$ arba ~94.5 %.

$7(\frac{-1}{8\sqrt{2}}{)}^2+(\frac{11}{8\sqrt{2}}{)}^2=\frac{7}{64\cdot 2}+\frac{121}{128}=\frac{7+121}{128}=1.$

Jeigu padarysime dar viena groverio iteracija G=MB, tai tikimybė išmatuoti |110> elementą bus $(\frac{13}{16\sqrt{2}}{)}^2\approx 0.330$ arba ~33.0 %. Po M vartų visų elementų amplitudės pasidaro neigiamos (-), kas ir parodo, kad jau viršytas iteracijų G limitas.

Kiek Groverio iteracijų reikia?

Groverio algoritmui groverio iteracijų r reikia:

$r\to \frac{\pi \sqrt{2^n}}{4}\approx \sqrt{2^n}$

$r\to \frac{\pi \sqrt{2^3}}{4}\approx 2.221441469$

$r\to \frac{\pi \sqrt{2^4}}{4}=\pi \approx 3.141592654$

Bet iteracijos gali būti tik sveiki skaičiai. Bet kai kubitų labai daug, tai ieškomo elemento gavimo tikimybė yra labai aukšta ir pakanka to, kad iteracijos atliekamos sveikais skaičiais.

Skaičiuojant groverio iteracijas pagal formule:

$r\to \frac{\pi \sqrt{2^n}}{4}$

Rodyklė užsisuka už 90 laipsnių reikšmės, bet už tai gaunamas truputi tikslesnis atsakymas (visada?). O jeigu norima, kad rodyklė neužsisuktų už 90 laipsnių stataus kampo, tai tada reikės viena groverio iteracija r mažiau, bet atsakymas bus truputi mažiau tikslus:

$r=\arccos \frac{1}{\sqrt{N}}:(2\arccos \sqrt{\frac{N-1}{N}})=\pi :(4\arcsin \frac{1}{\sqrt{N}})-0.5$

Laikoma, kad tokiu budu gautas iteracijų skaičius yra tikslus, nors gaunamas mažesnis teisigno atsakymo tikslumas. N=2ⁿ, kur n kubitų skaičius.

Teisingo atsakymo gavimo tikimybė

Reikia žinoti kampą:

$\theta =2\arccos (\sqrt{1-\frac{1}{2^n}})=2\arcsin \frac{1}{\sqrt{2^n}},$

kur n yra kubitų skaičius. Tada galima surasti ieškomo elemento |t> amplitudę:

$\sin (\frac{2r+1}{2}\theta )|t⟩$,

kur t yra ieškomas elementas, r yra groverio iteracijų skaičius. O tikimybė išmatuoti ieškomą elementą yra:

$p={\sin }^2(\frac{2r+1}{2}\theta ).$

Visų likusių elementų amplitudė kartu sudėjus yra:

$\cos (\frac{2r+1}{2}\theta )(|\psi ⟩-\frac{1}{2^n}|t⟩)$.

O tikimybė išmatuoti klaidingą atsakymą (būseną) yra:

$p={\cos }^2(\frac{2r+1}{2}\theta ).$

Pavyzdžiui, kai n=3:

$\theta =2\arccos (\sqrt{1-\frac{1}{2^3}})=2\arccos \sqrt{0.875}\approx 0.722734247.$

Tikimybė išmatuoti ieškomą elementą yra:

$p={\sin }^2(\frac{2\cdot 2+1}{2}0.722734247)={\sin }^2(2.5\cdot 0.722734247)\approx 0.972271824^2=0.9453125.$

Pavyzdys, kai n=4:

$\theta =2\arcsin \frac{1}{\sqrt{2^4}}\approx 0.50536051.$

Tikimybė išmatuoti ieškomą elementą yra:

$p={\sin }^2(\frac{2\cdot 3+1}{2}\cdot 0.50536051)={\sin }^2(3.5\cdot 0.50536051)\approx 0.98046875^2\approx 0.961318969.$

Groverio Iteracija

Vaizdas:Groveriteration.PNG

Groverio Iteracija: iš pradžių ieškomas elementas pažymimas neigiama amplitude, o paskui jo amplitudė apsukama apie vidurkį.

Norint paprastai ir greitai suskaičiuoti teisingo atsakymo gavimo tikimybę po vienos groverio iteracijos G, galima naudotis šia formule:

$p=(\frac{3N-4}{N\sqrt{N}}{)}^2$,

Kur $N=2^n$, o n kubitų skaičius. Pavyzdžiui, kai N=8:

$p=(\frac{3\cdot 8-4}{8\sqrt{8}}{)}^2=0.78125$.

Kai N=16:

$p=(\frac{3\cdot 16-4}{16\sqrt{16}}{)}^2=0.47265625$.

Kai N=1024:

$p=(\frac{3\cdot 1024-4}{1024\sqrt{1024}}{)}^2\approx 0.008766189$.

Apytiksliai sužinoti teisingo atsakymo tikimybę po betkiek Groverio iteracijų galima pagal formulę: $p=\frac{r^2}{2^n}$, kur n yra kubitų skaičius, o r yra iteracijų skaičius. Bet ši formulė takityna tik kai kubitų ir iteracijų skaičius yra didelis (daugiau nei 100).

Jeigu kubitų yra daugiau negu užduoties, kurią reikia išspresti, kintamųjų arba tiek pat (m≤n), tada Groverio iteracijų skaičių r galima apytiksliai apskaičiuoti pagal formulę:

$r\approx \sqrt{M}=\sqrt{2^m}=2^{\frac{m}{2}}$,

o tikimybę p, pagal formulę:

$p\approx \frac{r^2}{2^m},r^2<2^m,$

kur m yra užduoties kintamųjų skaičius, o n yra kubitų skaičius.

Jeigu kubitų n yra mažiau negu kintamųjų m (elementų doumenų bazėje yra $2^m$), $m>n$, tai teisingo atsakymo tikimybė p gaunama pagal formulę:

$p=\frac{\sqrt{2^n}}{2^m}=2^{\frac{n}{2}-m}=\frac{r^2}{2^m},$

kur r yra Groverio iteracijų skaičius, $r^2<2^n.$

Groverio algoritmas su 2 kubitais (N=4)

Atsakymas gaunamas su 100 % tikimybe, nes:

$r\to \frac{\pi \sqrt{2^n}}{4}=\frac{\pi \sqrt{2^2}}{4}=\frac{\pi }{2}\approx 1.570796327$

$\theta =2\arcsin \frac{1}{\sqrt{2^n}}=2\arcsin \frac{1}{\sqrt{2^2}}\approx 1.047197551$

Tikimybė išmatuoti ieškomą elementą yra:

$p={\sin }^2(\frac{2\cdot r+1}{2}\cdot \theta )={\sin }^2(\frac{2\cdot 1+1}{2}\cdot 1.047197551)={\sin }^2(1.5\cdot 1.047197551)=1^2=1.$

Pagal šią formulę, iteracijų skaičius yra sveikas skaičius (kaip beje ir teisingo atsakymo tikimybė):

$r=\pi :(4\arcsin \frac{1}{\sqrt{2^2}})-0.5=\frac{3.141592654}{4\cdot 0.523598775}-0.5=1.5-0.5=1$

Pavyzdžiui, surasime |01>: $|00⟩\to \frac{1}{\sqrt{2^2}}(|0⟩+|1⟩)(|0⟩+|1⟩)=|\psi ⟩=\frac{1}{2}(|00⟩+|01⟩+|10⟩+|11⟩)\to (1-2|01⟩⟨01|)|\psi ⟩=$ $=|\psi ⟩-\frac{2}{\sqrt{2^2}}|01⟩=|\psi ⟩-|01⟩=\frac{1}{2}(|00⟩-|01⟩+|10⟩+|11⟩)\to (2|\psi ⟩⟨\psi |-1)(|\psi ⟩-|01⟩)=$ $=2|\psi ⟩⟨\psi |\psi ⟩-2|\psi ⟩⟨\psi |01⟩-|\psi ⟩+|01⟩=2|\psi ⟩-\frac{2}{\sqrt{2^2}}|\psi ⟩-|\psi ⟩+|01⟩=|01⟩.$

Groverio algoritmas bendru atveju

Turime $|0{⟩}^{\oplus n}|1⟩$ įėjimą, kurį praleidžiame pro $n+1$ Hadamardo vartų:

$\frac{1}{\sqrt{2^{n+1}}}\sum _{x_1}^{2^n}|x⟩(|0⟩-|1⟩)=|\psi ⟩\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=|\psi ⟩|-⟩.$

Toliau praleidžiame per funkciją $|x⟩|y⟩\to |x⟩|y\oplus f(x)⟩:$

$\frac{1}{\sqrt{2^{n+1}}}\sum _{x_1}^{2^n}|x⟩(|0\oplus f(x)⟩-|1\oplus f(x)⟩)=\frac{1}{\sqrt{2^{n+1}}}\sum _{x_1}^{2^n}(-1{)}^{f(x)}|x⟩(|0⟩-|1⟩),$

taigi, jeigu $f(x)=1,$ tai ir yra ieškomas elementas ir jis pažimimas minuso ženklu "$-$".

Nuorodos

• Davido Deutsch'o pamoka apie Groverio algortimą. Video.
• http://arxiv.org/pdf/quant-ph/0301079 Groverio algoritmas (ang.). PDF.
• http://iontrap.physics.lsa.umich.edu/publications/archive/PRA_72_050306_brickman_grover.pdf Šablonas:Webarchive Groverio algoritmas su jonų gaudykle. PDF.
• http://www.cit.gu.edu.au/~s55086/qucomp/sim.html Šablonas:Webarchive http://www.cit.gu.edu.au/~s55086/qucomp/qucompApplet.html Groverio algoritmas su fotonais (reikia firefox, kad normaliai rodytų).
• http://arxiv.org/pdf/quant-ph/9807053.pdf
• http://www.cs.washington.edu/education/courses/cse599d/06wi/lecturenotes12.pdf
• http://www.physast.uga.edu/~mgeller/Nat434p169.pdfŠablonas:Neveikianti nuoroda
• http://www.znaturforsch.com/aa/v57a/s57a0701.pdf