Groverio algoritmas (ang. Grover's algorithm ) yra kvantinis algoritmas skirtas ieškojimui nestrukturizuotoje (nesutvarkytoje) duomenų bazėje su N kintamųjų per O(
N
{\displaystyle {\sqrt {N}}}
Lov Grover ) 1996 m.
Klasiškai, ieškant nesutvarkytoje duomenų bazėje reikia linijinio ieškojimo per O(N) laiką. Groverio algoritmas kuris užima O(N1/2 ) laiko, yra greičiausias įmanomas kvantinis 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. Bet netgi kvadratinis paspartėjimas žymus, kai N yra didelis. Pavyzdžiui, su tam tikru N , tokios pat spartos kvantiniam kompiuteriui kaip klasikinis prireiktų, 4 mėnesių. Tuo tarpu klasikiniam kompiuteriui prireiktų 1013 metų (toks yra Visatos amžius). Tikimybė, kad atsakymas bus klaidingas yra 1/N, kur N yra duomenų bazę sudarančių elementų sveikas skaičius. N =2n , kur n kubitų skaičius.
Groverio Iteracija
|
ψ
⟩
=
H
|
0
⟩
H
|
0
⟩
H
|
0
⟩
H
|
0
⟩
.
.
.
H
|
0
⟩
H
|
0
⟩
=
H
n
|
O
⟩
.
{\displaystyle |\psi \rangle =H|0\rangle H|0\rangle H|0\rangle H|0\rangle ...H|0\rangle H|0\rangle =H^{n}|O\rangle .}
Vartai M , kurie naudojami po Hadamardo vartų:
M
=
1
−
2
|
t
⟩
⟨
t
|
;
{\displaystyle M=1-2|t\rangle \langle t|;}
M
|
ψ
⟩
=
|
ψ
⟩
−
2
2
n
|
t
⟩
,
{\displaystyle M|\psi \rangle =|\psi \rangle -{\frac {2}{\sqrt {2^{n}}}}|t\rangle ,}
kur t yra ieškomas elementas.
Per vartus B pereina visi kubitai išskyrus paskutinį.
B
=
2
|
ψ
⟩
⟨
ψ
|
−
1
{\displaystyle B=2|\psi \rangle \langle \psi |-1}
kur n yra kubitų skaičius.
B
=
H
(
2
|
O
⟩
⟨
O
|
−
1
)
H
=
(
2
H
|
O
⟩
⟨
O
|
−
H
)
H
=
2
H
|
O
⟩
⟨
O
|
H
−
H
H
=
2
|
ψ
⟩
⟨
ψ
|
−
1.
{\displaystyle B=H(2|O\rangle \langle O|-1)H=(2H|O\rangle \langle O|-H)H=2H|O\rangle \langle O|H-HH=2|\psi \rangle \langle \psi |-1.}
|
O
⟩
=
|
0
⟩
|
0
⟩
.
.
.
|
0
⟩
=
|
00...0
⟩
.
{\displaystyle |O\rangle =|0\rangle |0\rangle ...|0\rangle =|00...0\rangle .}
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.
{\displaystyle (2|O\rangle \langle O|-1)(2|O\rangle \langle O|-1)=4|O\rangle \langle O|O\rangle \langle O|-2|O\rangle \langle O|-2|O\rangle \langle O|+1=4|O\rangle \langle O|-4|O\rangle \langle O|+1=1.}
Groverio iteracija G :
G
=
B
M
=
(
2
|
ψ
⟩
⟨
ψ
|
−
1
)
(
1
−
2
|
t
⟩
⟨
t
|
)
.
{\displaystyle G=BM=(2|\psi \rangle \langle \psi |-1)(1-2|t\rangle \langle t|).}
⟨
ψ
|
x
⟩
=
1
2
n
.
{\displaystyle \langle \psi |x\rangle ={\frac {1}{\sqrt {2^{n}}}}.}
Pavyzdžiui, x=|1001>:
⟨
1001
|
ψ
⟩
=
1
2
4
.
{\displaystyle \langle 1001|\psi \rangle ={\frac {1}{\sqrt {2^{4}}}}.}
⟨
ψ
|
ψ
⟩
=
1.
{\displaystyle \langle \psi |\psi \rangle =1.}
⟨
x
|
x
⟩
=
⟨
1001
|
1001
⟩
=
1.
{\displaystyle \langle x|x\rangle =\langle 1001|1001\rangle =1.}
⟨
x
|
y
⟩
=
⟨
1001
|
1000
⟩
=
0.
{\displaystyle \langle x|y\rangle =\langle 1001|1000\rangle =0.}
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 2n . Visus 5 kubitus praleidžiame pro Hadamardo vartus .
t=1,
|
ψ
⟩
H
|
1
⟩
=
H
|
0
⟩
H
|
0
⟩
H
|
0
⟩
H
|
0
⟩
H
|
1
⟩
=
1
4
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle |\psi \rangle H|1\rangle =H|0\rangle H|0\rangle H|0\rangle H|0\rangle H|1\rangle ={\frac {1}{4}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle +|1\rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=}
=
1
4
(
|
0000
⟩
+
|
0010
⟩
+
|
0001
⟩
+
|
0011
⟩
+
|
1000
⟩
+
|
1010
⟩
+
|
1001
⟩
+
|
1011
⟩
+
{\displaystyle ={\frac {1}{4}}(|0000\rangle +|0010\rangle +|0001\rangle +|0011\rangle +|1000\rangle +|1010\rangle +|1001\rangle +|1011\rangle +}
+
|
0100
⟩
+
|
0110
⟩
+
|
0101
⟩
+
|
0111
⟩
+
|
1100
⟩
+
|
1110
⟩
+
|
1101
⟩
+
|
1111
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
|
ψ
⟩
1
2
(
|
0
⟩
−
|
1
⟩
)
.
{\displaystyle +|0100\rangle +|0110\rangle +|0101\rangle +|0111\rangle +|1100\rangle +|1110\rangle +|1101\rangle +|1111\rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=|\psi \rangle {\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle ).}
Orakulas M :
M
=
1
−
2
|
t
⟩
⟨
t
|
=
1
−
2
|
1001
⟩
⟨
1001
|
.
{\displaystyle M=1-2|t\rangle \langle t|=1-2|1001\rangle \langle 1001|.}
M
|
ψ
⟩
=
|
ψ
⟩
−
2
2
n
|
t
⟩
=
|
ψ
⟩
−
2
2
4
|
1001
⟩
,
{\displaystyle M|\psi \rangle =|\psi \rangle -{\frac {2}{\sqrt {2^{n}}}}|t\rangle =|\psi \rangle -{\frac {2}{\sqrt {2^{4}}}}|1001\rangle ,}
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
|
ψ
⟩
1
2
(
|
0
⟩
−
|
1
⟩
)
=
(
1
−
2
|
1001
⟩
⟨
1001
|
)
|
ψ
⟩
1
2
(
|
0
⟩
−
|
1
⟩
)
=
(
|
ψ
⟩
−
2
|
1001
⟩
⟨
1001
|
ψ
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle M|\psi \rangle {\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=(1-2|1001\rangle \langle 1001|)|\psi \rangle {\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=(|\psi \rangle -2|1001\rangle \langle 1001|\psi \rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=}
=
(
|
ψ
⟩
−
2
2
4
|
1001
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
(
|
ψ
⟩
−
1
2
|
1001
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle =(|\psi \rangle -{\frac {2}{\sqrt {2^{4}}}}|1001\rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=(|\psi \rangle -{\frac {1}{2}}|1001\rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=}
=
(
1
4
(
|
0000
⟩
+
|
0010
⟩
+
|
0001
⟩
+
|
0011
⟩
+
|
1000
⟩
+
|
1010
⟩
+
|
1001
⟩
+
|
1011
⟩
+
{\displaystyle =({\frac {1}{4}}(|0000\rangle +|0010\rangle +|0001\rangle +|0011\rangle +|1000\rangle +|1010\rangle +|1001\rangle +|1011\rangle +}
+
|
0100
⟩
+
|
0110
⟩
+
|
0101
⟩
+
|
0111
⟩
+
|
1100
⟩
+
|
1110
⟩
+
|
1101
⟩
+
|
1111
⟩
)
)
−
1
2
|
1001
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle +|0100\rangle +|0110\rangle +|0101\rangle +|0111\rangle +|1100\rangle +|1110\rangle +|1101\rangle +|1111\rangle ))-{\frac {1}{2}}|1001\rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=}
=
1
4
(
|
0000
⟩
+
|
0010
⟩
+
|
0001
⟩
+
|
0011
⟩
+
|
1000
⟩
+
|
1010
⟩
−
|
1001
⟩
+
|
1011
⟩
+
{\displaystyle ={\frac {1}{4}}(|0000\rangle +|0010\rangle +|0001\rangle +|0011\rangle +|1000\rangle +|1010\rangle -|1001\rangle +|1011\rangle +}
+
|
0100
⟩
+
|
0110
⟩
+
|
0101
⟩
+
|
0111
⟩
+
|
1100
⟩
+
|
1110
⟩
+
|
1101
⟩
+
|
1111
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
.
{\displaystyle +|0100\rangle +|0110\rangle +|0101\rangle +|0111\rangle +|1100\rangle +|1110\rangle +|1101\rangle +|1111\rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle ).}
Toliau Praleidžiame tik pirmus 4 kubitus pro B vartus:
t=3,
B
(
|
ψ
⟩
−
1
2
|
1001
⟩
)
=
(
2
|
ψ
⟩
⟨
ψ
|
−
1
)
(
|
ψ
⟩
−
1
2
|
1001
⟩
)
=
2
|
ψ
⟩
⟨
ψ
|
ψ
⟩
−
|
ψ
⟩
−
2
2
|
ψ
⟩
⟨
ψ
|
1001
⟩
+
1
2
|
1001
⟩
=
{\displaystyle B(|\psi \rangle -{\frac {1}{2}}|1001\rangle )=(2|\psi \rangle \langle \psi |-1)(|\psi \rangle -{\frac {1}{2}}|1001\rangle )=2|\psi \rangle \langle \psi |\psi \rangle -|\psi \rangle -{\frac {2}{2}}|\psi \rangle \langle \psi |1001\rangle +{\frac {1}{2}}|1001\rangle =}
=
2
|
ψ
⟩
−
|
ψ
⟩
−
|
ψ
⟩
1
2
4
+
1
2
|
1001
⟩
=
|
ψ
⟩
−
1
4
|
ψ
⟩
+
1
2
|
1001
⟩
=
3
4
|
ψ
⟩
+
1
2
|
1001
⟩
=
{\displaystyle =2|\psi \rangle -|\psi \rangle -|\psi \rangle {\frac {1}{\sqrt {2^{4}}}}+{\frac {1}{2}}|1001\rangle =|\psi \rangle -{\frac {1}{4}}|\psi \rangle +{\frac {1}{2}}|1001\rangle ={\frac {3}{4}}|\psi \rangle +{\frac {1}{2}}|1001\rangle =}
=
1
16
(
3
|
0000
⟩
+
3
|
0010
⟩
+
3
|
0001
⟩
+
3
|
0011
⟩
+
3
|
1000
⟩
+
3
|
1010
⟩
+
3
|
1001
⟩
+
3
|
1011
⟩
+
{\displaystyle ={\frac {1}{16}}(3|0000\rangle +3|0010\rangle +3|0001\rangle +3|0011\rangle +3|1000\rangle +3|1010\rangle +3|1001\rangle +3|1011\rangle +}
+
3
|
0100
⟩
+
3
|
0110
⟩
+
3
|
0101
⟩
+
3
|
0111
⟩
+
3
|
1100
⟩
+
3
|
1110
⟩
+
3
|
1101
⟩
+
3
|
1111
⟩
)
+
1
2
|
1001
⟩
=
{\displaystyle +3|0100\rangle +3|0110\rangle +3|0101\rangle +3|0111\rangle +3|1100\rangle +3|1110\rangle +3|1101\rangle +3|1111\rangle )+{\frac {1}{2}}|1001\rangle =}
=
1
16
(
3
|
0000
⟩
+
3
|
0010
⟩
+
3
|
0001
⟩
+
3
|
0011
⟩
+
3
|
1000
⟩
+
3
|
1010
⟩
+
11
|
1001
⟩
+
3
|
1011
⟩
+
{\displaystyle ={\frac {1}{16}}(3|0000\rangle +3|0010\rangle +3|0001\rangle +3|0011\rangle +3|1000\rangle +3|1010\rangle +11|1001\rangle +3|1011\rangle +}
+
3
|
0100
⟩
+
3
|
0110
⟩
+
3
|
0101
⟩
+
3
|
0111
⟩
+
3
|
1100
⟩
+
3
|
1110
⟩
+
3
|
1101
⟩
+
3
|
1111
⟩
)
.
{\displaystyle +3|0100\rangle +3|0110\rangle +3|0101\rangle +3|0111\rangle +3|1100\rangle +3|1110\rangle +3|1101\rangle +3|1111\rangle ).}
Kaip matome po perėjimo per B vartus, ieškomo elemento amplitudė pakilo ir sudaro
11
16
{\displaystyle {\frac {11}{16}}}
3
16
{\displaystyle {\frac {3}{16}}}
15
(
3
16
)
2
+
(
11
16
)
2
=
1.
{\displaystyle 15({\frac {3}{16}})^{2}+({\frac {11}{16}})^{2}=1.}
Tai reiškia, kad tikimybė išmatuoti |1001> yra (11/16)2 =~0.47 arba ~47 %.
Toliau vėl praleidžiame visus 5 kubitus pro orakulą M (penktas kubitas neparodytas, nes matematiniuose skaičiavimuose jis nieko nekeičia arba kitaip tariant penktas kubitas ir padaro, kad būtų M ):
t=4,
M
(
3
4
|
ψ
⟩
+
1
2
|
1001
⟩
)
=
(
1
−
2
|
1001
⟩
⟨
1001
|
)
(
3
4
|
ψ
⟩
+
1
2
|
1001
⟩
)
=
{\displaystyle M({\frac {3}{4}}|\psi \rangle +{\frac {1}{2}}|1001\rangle )=(1-2|1001\rangle \langle 1001|)({\frac {3}{4}}|\psi \rangle +{\frac {1}{2}}|1001\rangle )=}
=
3
4
|
ψ
⟩
−
6
4
|
1001
⟩
⟨
1001
|
ψ
⟩
+
1
2
|
1001
⟩
−
2
2
|
1001
⟩
⟨
1001
|
1001
⟩
=
{\displaystyle ={\frac {3}{4}}|\psi \rangle -{\frac {6}{4}}|1001\rangle \langle 1001|\psi \rangle +{\frac {1}{2}}|1001\rangle -{\frac {2}{2}}|1001\rangle \langle 1001|1001\rangle =}
=
3
4
|
ψ
⟩
−
3
2
|
1001
⟩
1
2
4
+
1
2
|
1001
⟩
−
|
1001
⟩
=
3
4
|
ψ
⟩
−
3
2
|
1001
⟩
1
4
−
1
2
|
1001
⟩
=
{\displaystyle ={\frac {3}{4}}|\psi \rangle -{\frac {3}{2}}|1001\rangle {\frac {1}{\sqrt {2^{4}}}}+{\frac {1}{2}}|1001\rangle -|1001\rangle ={\frac {3}{4}}|\psi \rangle -{\frac {3}{2}}|1001\rangle {\frac {1}{4}}-{\frac {1}{2}}|1001\rangle =}
=
3
4
|
ψ
⟩
−
3
8
|
1001
⟩
−
1
2
|
1001
⟩
=
3
4
|
ψ
⟩
−
7
8
|
1001
⟩
=
{\displaystyle ={\frac {3}{4}}|\psi \rangle -{\frac {3}{8}}|1001\rangle -{\frac {1}{2}}|1001\rangle ={\frac {3}{4}}|\psi \rangle -{\frac {7}{8}}|1001\rangle =}
=
1
16
(
3
|
0000
⟩
+
3
|
0010
⟩
+
3
|
0001
⟩
+
3
|
0011
⟩
+
3
|
1000
⟩
+
3
|
1010
⟩
−
11
|
1001
⟩
+
3
|
1011
⟩
+
{\displaystyle ={\frac {1}{16}}(3|0000\rangle +3|0010\rangle +3|0001\rangle +3|0011\rangle +3|1000\rangle +3|1010\rangle -11|1001\rangle +3|1011\rangle +}
+
3
|
0100
⟩
+
3
|
0110
⟩
+
3
|
0101
⟩
+
3
|
0111
⟩
+
3
|
1100
⟩
+
3
|
1110
⟩
+
3
|
1101
⟩
+
3
|
1111
⟩
)
.
{\displaystyle +3|0100\rangle +3|0110\rangle +3|0101\rangle +3|0111\rangle +3|1100\rangle +3|1110\rangle +3|1101\rangle +3|1111\rangle ).}
15
(
3
4
1
4
)
2
+
(
3
16
−
7
8
)
2
=
1.
{\displaystyle 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
(
3
4
|
ψ
⟩
−
7
8
|
1001
⟩
)
=
(
2
|
ψ
⟩
⟨
ψ
|
−
1
)
(
3
4
|
ψ
⟩
−
7
8
|
1001
⟩
)
=
3
2
|
ψ
⟩
⟨
ψ
|
ψ
⟩
−
3
4
|
ψ
⟩
−
7
4
|
ψ
⟩
⟨
ψ
|
1001
⟩
+
7
8
|
1001
⟩
=
{\displaystyle B({\frac {3}{4}}|\psi \rangle -{\frac {7}{8}}|1001\rangle )=(2|\psi \rangle \langle \psi |-1)({\frac {3}{4}}|\psi \rangle -{\frac {7}{8}}|1001\rangle )={\frac {3}{2}}|\psi \rangle \langle \psi |\psi \rangle -{\frac {3}{4}}|\psi \rangle -{\frac {7}{4}}|\psi \rangle \langle \psi |1001\rangle +{\frac {7}{8}}|1001\rangle =}
=
3
2
|
ψ
⟩
−
3
4
|
ψ
⟩
−
7
4
|
ψ
⟩
1
2
4
+
7
8
|
1001
⟩
=
3
4
|
ψ
⟩
−
7
4
|
ψ
⟩
1
4
+
7
8
|
1001
⟩
=
3
4
|
ψ
⟩
−
7
16
|
ψ
⟩
+
7
8
|
1001
⟩
=
{\displaystyle ={\frac {3}{2}}|\psi \rangle -{\frac {3}{4}}|\psi \rangle -{\frac {7}{4}}|\psi \rangle {\frac {1}{\sqrt {2^{4}}}}+{\frac {7}{8}}|1001\rangle ={\frac {3}{4}}|\psi \rangle -{\frac {7}{4}}|\psi \rangle {\frac {1}{4}}+{\frac {7}{8}}|1001\rangle ={\frac {3}{4}}|\psi \rangle -{\frac {7}{16}}|\psi \rangle +{\frac {7}{8}}|1001\rangle =}
=
5
16
|
ψ
⟩
+
7
8
|
1001
⟩
{\displaystyle ={\frac {5}{16}}|\psi \rangle +{\frac {7}{8}}|1001\rangle }
Tikimybė dabar išmatuoti |1001> yra
(
5
16
⋅
1
4
+
7
8
)
2
=
(
5
64
+
7
8
)
2
=
(
5
+
7
⋅
8
64
)
2
=
(
61
64
)
2
≈
0.91
{\displaystyle ({\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}
15
(
5
16
⋅
1
4
)
2
+
(
61
64
)
2
=
1.
{\displaystyle 15({\frac {5}{16}}\cdot {\frac {1}{4}})^{2}+({\frac {61}{64}})^{2}=1.}
Kadangi n=4, o N=2n =24 =16, tai pagal idėja reikia padaryti
16
=
4
{\displaystyle {\sqrt {16}}=4}
M vartus:
t=6,
M
(
5
16
|
ψ
⟩
+
7
8
|
1001
⟩
)
=
(
1
−
2
|
1001
⟩
⟨
1001
|
)
(
5
16
|
ψ
⟩
+
7
8
|
1001
⟩
)
=
{\displaystyle M({\frac {5}{16}}|\psi \rangle +{\frac {7}{8}}|1001\rangle )=(1-2|1001\rangle \langle 1001|)({\frac {5}{16}}|\psi \rangle +{\frac {7}{8}}|1001\rangle )=}
=
5
16
|
ψ
⟩
−
5
8
|
1001
⟩
⟨
1001
|
ψ
⟩
+
7
8
|
1001
⟩
−
7
4
|
1001
⟩
⟨
1001
|
1001
⟩
=
{\displaystyle ={\frac {5}{16}}|\psi \rangle -{\frac {5}{8}}|1001\rangle \langle 1001|\psi \rangle +{\frac {7}{8}}|1001\rangle -{\frac {7}{4}}|1001\rangle \langle 1001|1001\rangle =}
=
5
16
|
ψ
⟩
−
5
8
|
1001
⟩
1
4
+
7
8
|
1001
⟩
−
7
4
|
1001
⟩
=
5
16
|
ψ
⟩
−
5
32
|
1001
⟩
−
7
8
|
1001
⟩
=
{\displaystyle ={\frac {5}{16}}|\psi \rangle -{\frac {5}{8}}|1001\rangle {\frac {1}{4}}+{\frac {7}{8}}|1001\rangle -{\frac {7}{4}}|1001\rangle ={\frac {5}{16}}|\psi \rangle -{\frac {5}{32}}|1001\rangle -{\frac {7}{8}}|1001\rangle =}
=
5
16
|
ψ
⟩
+
−
5
−
7
⋅
4
32
|
1001
⟩
=
5
16
|
ψ
⟩
−
33
32
|
1001
⟩
.
{\displaystyle ={\frac {5}{16}}|\psi \rangle +{\frac {-5-7\cdot 4}{32}}|1001\rangle ={\frac {5}{16}}|\psi \rangle -{\frac {33}{32}}|1001\rangle .}
Toliau praleidžiame pirmus keturis kubitus pro B vartus:
t=7,
B
(
5
16
|
ψ
⟩
−
33
32
|
1001
⟩
)
=
(
2
|
ψ
⟩
⟨
ψ
|
−
1
)
(
5
16
|
ψ
⟩
−
33
32
|
1001
⟩
)
=
{\displaystyle B({\frac {5}{16}}|\psi \rangle -{\frac {33}{32}}|1001\rangle )=(2|\psi \rangle \langle \psi |-1)({\frac {5}{16}}|\psi \rangle -{\frac {33}{32}}|1001\rangle )=}
=
5
8
|
ψ
⟩
⟨
ψ
|
ψ
⟩
−
5
16
|
ψ
⟩
−
33
16
|
ψ
⟩
⟨
ψ
|
1001
⟩
+
33
32
|
1001
⟩
=
5
8
|
ψ
⟩
−
5
16
|
ψ
⟩
−
33
16
|
ψ
⟩
1
4
+
33
32
|
1001
⟩
=
{\displaystyle ={\frac {5}{8}}|\psi \rangle \langle \psi |\psi \rangle -{\frac {5}{16}}|\psi \rangle -{\frac {33}{16}}|\psi \rangle \langle \psi |1001\rangle +{\frac {33}{32}}|1001\rangle ={\frac {5}{8}}|\psi \rangle -{\frac {5}{16}}|\psi \rangle -{\frac {33}{16}}|\psi \rangle {\frac {1}{4}}+{\frac {33}{32}}|1001\rangle =}
=
5
16
|
ψ
⟩
−
33
64
|
ψ
⟩
+
33
32
|
1001
⟩
=
5
⋅
4
−
33
64
|
ψ
⟩
+
33
32
|
1001
⟩
=
−
13
64
|
ψ
⟩
+
33
32
|
1001
⟩
.
{\displaystyle ={\frac {5}{16}}|\psi \rangle -{\frac {33}{64}}|\psi \rangle +{\frac {33}{32}}|1001\rangle ={\frac {5\cdot 4-33}{64}}|\psi \rangle +{\frac {33}{32}}|1001\rangle =-{\frac {13}{64}}|\psi \rangle +{\frac {33}{32}}|1001\rangle .}
Tikimybė išmatuoti |1001> yra
(
−
13
64
⋅
1
4
+
33
32
)
2
=
(
−
13
256
+
33
32
)
2
=
(
−
13
+
33
⋅
8
256
)
2
=
(
251
256
)
2
=
63001
65536
≈
0.961
{\displaystyle (-{\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}
Toliau praleidžiame visus kubitus pro M vartus:
t=8,
M
(
−
13
64
|
ψ
⟩
+
33
32
|
1001
⟩
)
=
(
1
−
2
|
1001
⟩
⟨
1001
|
)
(
−
13
64
|
ψ
⟩
+
33
32
|
1001
⟩
)
=
{\displaystyle M(-{\frac {13}{64}}|\psi \rangle +{\frac {33}{32}}|1001\rangle )=(1-2|1001\rangle \langle 1001|)(-{\frac {13}{64}}|\psi \rangle +{\frac {33}{32}}|1001\rangle )=}
=
−
13
64
|
ψ
⟩
+
13
32
|
1001
⟩
⟨
1001
|
ψ
⟩
+
33
32
|
1001
⟩
−
33
16
|
1001
⟩
⟨
1001
|
1001
⟩
=
{\displaystyle =-{\frac {13}{64}}|\psi \rangle +{\frac {13}{32}}|1001\rangle \langle 1001|\psi \rangle +{\frac {33}{32}}|1001\rangle -{\frac {33}{16}}|1001\rangle \langle 1001|1001\rangle =}
=
−
13
64
|
ψ
⟩
+
13
32
|
1001
⟩
1
4
+
33
32
|
1001
⟩
−
33
16
|
1001
⟩
=
−
13
64
|
ψ
⟩
+
13
128
|
1001
⟩
−
33
32
|
1001
⟩
=
{\displaystyle =-{\frac {13}{64}}|\psi \rangle +{\frac {13}{32}}|1001\rangle {\frac {1}{4}}+{\frac {33}{32}}|1001\rangle -{\frac {33}{16}}|1001\rangle =-{\frac {13}{64}}|\psi \rangle +{\frac {13}{128}}|1001\rangle -{\frac {33}{32}}|1001\rangle =}
=
−
13
64
|
ψ
⟩
+
13
−
33
⋅
4
128
|
1001
⟩
=
−
13
64
|
ψ
⟩
−
119
128
|
1001
⟩
.
{\displaystyle =-{\frac {13}{64}}|\psi \rangle +{\frac {13-33\cdot 4}{128}}|1001\rangle =-{\frac {13}{64}}|\psi \rangle -{\frac {119}{128}}|1001\rangle .}
Toliau praleidžiame pirmus keturis kubitus pro B vartus:
t=9,
B
(
−
13
64
|
ψ
⟩
−
119
128
|
1001
⟩
)
=
(
2
|
ψ
⟩
⟨
ψ
|
−
1
)
(
−
13
64
|
ψ
⟩
−
119
128
|
1001
⟩
)
=
{\displaystyle B(-{\frac {13}{64}}|\psi \rangle -{\frac {119}{128}}|1001\rangle )=(2|\psi \rangle \langle \psi |-1)(-{\frac {13}{64}}|\psi \rangle -{\frac {119}{128}}|1001\rangle )=}
=
−
13
32
|
ψ
⟩
⟨
ψ
|
ψ
⟩
+
13
64
|
ψ
⟩
−
119
64
|
ψ
⟩
⟨
ψ
|
1001
⟩
+
119
128
|
1001
⟩
=
−
13
32
|
ψ
⟩
+
13
64
|
ψ
⟩
−
119
64
|
ψ
⟩
1
4
+
119
128
|
1001
⟩
=
{\displaystyle =-{\frac {13}{32}}|\psi \rangle \langle \psi |\psi \rangle +{\frac {13}{64}}|\psi \rangle -{\frac {119}{64}}|\psi \rangle \langle \psi |1001\rangle +{\frac {119}{128}}|1001\rangle =-{\frac {13}{32}}|\psi \rangle +{\frac {13}{64}}|\psi \rangle -{\frac {119}{64}}|\psi \rangle {\frac {1}{4}}+{\frac {119}{128}}|1001\rangle =}
=
−
13
64
|
ψ
⟩
−
119
256
|
ψ
⟩
+
119
128
|
1001
⟩
=
−
13
⋅
4
−
119
256
|
ψ
⟩
+
119
128
|
1001
⟩
=
−
171
256
|
ψ
⟩
+
119
128
|
1001
⟩
.
{\displaystyle =-{\frac {13}{64}}|\psi \rangle -{\frac {119}{256}}|\psi \rangle +{\frac {119}{128}}|1001\rangle ={\frac {-13\cdot 4-119}{256}}|\psi \rangle +{\frac {119}{128}}|1001\rangle =-{\frac {171}{256}}|\psi \rangle +{\frac {119}{128}}|1001\rangle .}
Tikimybė išmatuoti |1001> yra
(
−
171
256
⋅
1
4
+
119
128
)
2
=
(
−
171
1024
+
119
128
)
2
=
(
−
171
+
119
⋅
8
1024
)
2
=
(
781
1024
)
2
=
609961
1048576
≈
0.582
{\displaystyle (-{\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}
visos elementų amplitudės pasidaro neigiamos (-). O be to ir nesakoma, kad reikia daryti lygiai
2
4
=
4
{\displaystyle {\sqrt {2^{4}}}=4}
2
n
{\displaystyle {\sqrt {2^{n}}}}
2
n
{\displaystyle {\sqrt {2^{n}}}}
15
(
−
171
1024
)
2
+
(
781
1024
)
2
=
1.
{\displaystyle 15({\frac {-171}{1024}})^{2}+({\frac {781}{1024}})^{2}=1.}
Turime 4 kubitus, tris pirmi kubitai yra nuliai, o ketvirtas vienetas. Praleidžiame juos visus pro Hadamardo vartus :
t=1,
|
ψ
⟩
H
|
1
⟩
=
H
|
0
⟩
H
|
0
⟩
H
|
0
⟩
H
|
1
⟩
=
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle |\psi \rangle H|1\rangle =H|0\rangle H|0\rangle H|0\rangle H|1\rangle ={\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle +|1\rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )=}
=
1
2
2
(
|
000
⟩
+
|
001
⟩
+
|
011
⟩
+
|
111
⟩
+
|
100
⟩
+
|
110
⟩
+
|
101
⟩
+
|
010
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
.
{\displaystyle ={\frac {1}{2{\sqrt {2}}}}(|000\rangle +|001\rangle +|011\rangle +|111\rangle +|100\rangle +|110\rangle +|101\rangle +|010\rangle ){\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle ).}
Toliau visus 4 kubitus praleidžiame pro M vartus. Ketvirto kubito nerašome nes jis lieka nepakitęs, nors kažkaip paįtakoja kitus kubitus. Tarkime mes ieškome |110>.
t=2,
M
|
ψ
⟩
=
M
1
2
2
(
|
000
⟩
+
|
001
⟩
+
|
011
⟩
+
|
111
⟩
+
|
100
⟩
+
|
110
⟩
+
|
101
⟩
+
|
010
⟩
)
=
(
1
−
2
|
110
⟩
⟨
110
|
)
|
ψ
⟩
=
{\displaystyle M|\psi \rangle =M{\frac {1}{2{\sqrt {2}}}}(|000\rangle +|001\rangle +|011\rangle +|111\rangle +|100\rangle +|110\rangle +|101\rangle +|010\rangle )=(1-2|110\rangle \langle 110|)|\psi \rangle =}
=
|
ψ
⟩
−
2
|
110
⟩
⟨
110
|
ψ
⟩
=
|
ψ
⟩
−
2
|
110
⟩
1
2
3
=
|
ψ
⟩
−
2
|
110
⟩
1
2
2
=
|
ψ
⟩
−
1
2
|
110
⟩
=
{\displaystyle =|\psi \rangle -2|110\rangle \langle 110|\psi \rangle =|\psi \rangle -2|110\rangle {\frac {1}{\sqrt {2^{3}}}}=|\psi \rangle -2|110\rangle {\frac {1}{2{\sqrt {2}}}}=|\psi \rangle -{\frac {1}{\sqrt {2}}}|110\rangle =}
=
1
2
2
(
|
000
⟩
+
|
001
⟩
+
|
011
⟩
+
|
111
⟩
+
|
100
⟩
−
|
110
⟩
+
|
101
⟩
+
|
010
⟩
)
.
{\displaystyle ={\frac {1}{2{\sqrt {2}}}}(|000\rangle +|001\rangle +|011\rangle +|111\rangle +|100\rangle -|110\rangle +|101\rangle +|010\rangle ).}
Toliau praleidžiame tik pirmus 3 kubitus pro B vartus:
t=3,
B
(
|
ψ
⟩
−
1
2
|
110
⟩
)
=
(
2
|
ψ
⟩
⟨
ψ
|
−
1
)
(
|
ψ
⟩
−
1
2
|
110
⟩
)
=
{\displaystyle B(|\psi \rangle -{\frac {1}{\sqrt {2}}}|110\rangle )=(2|\psi \rangle \langle \psi |-1)(|\psi \rangle -{\frac {1}{\sqrt {2}}}|110\rangle )=}
=
2
|
ψ
⟩
⟨
ψ
|
ψ
⟩
−
|
ψ
⟩
−
2
2
|
ψ
⟩
⟨
ψ
|
110
⟩
+
1
2
|
110
⟩
=
{\displaystyle =2|\psi \rangle \langle \psi |\psi \rangle -|\psi \rangle -{\frac {2}{\sqrt {2}}}|\psi \rangle \langle \psi |110\rangle +{\frac {1}{\sqrt {2}}}|110\rangle =}
=
2
|
ψ
⟩
−
|
ψ
⟩
−
2
2
|
ψ
⟩
1
2
2
+
1
2
|
110
⟩
=
{\displaystyle =2|\psi \rangle -|\psi \rangle -{\frac {2}{\sqrt {2}}}|\psi \rangle {\frac {1}{2{\sqrt {2}}}}+{\frac {1}{\sqrt {2}}}|110\rangle =}
=
|
ψ
⟩
−
2
4
|
ψ
⟩
+
1
2
|
110
⟩
=
{\displaystyle =|\psi \rangle -{\frac {2}{4}}|\psi \rangle +{\frac {1}{\sqrt {2}}}|110\rangle =}
=
1
2
|
ψ
⟩
+
1
2
|
110
⟩
.
{\displaystyle ={\frac {1}{2}}|\psi \rangle +{\frac {1}{\sqrt {2}}}|110\rangle .}
=
1
2
⋅
1
2
2
(
|
000
⟩
+
|
001
⟩
+
|
011
⟩
+
|
111
⟩
+
|
100
⟩
+
|
110
⟩
+
|
101
⟩
+
|
010
⟩
)
+
1
2
|
110
⟩
.
{\displaystyle ={\frac {1}{2}}\cdot {\frac {1}{2{\sqrt {2}}}}(|000\rangle +|001\rangle +|011\rangle +|111\rangle +|100\rangle +|110\rangle +|101\rangle +|010\rangle )+{\frac {1}{\sqrt {2}}}|110\rangle .}
=
1
4
2
(
|
000
⟩
+
|
001
⟩
+
|
011
⟩
+
|
111
⟩
+
|
100
⟩
+
5
|
110
⟩
+
|
101
⟩
+
|
010
⟩
)
.
{\displaystyle ={\frac {1}{4{\sqrt {2}}}}(|000\rangle +|001\rangle +|011\rangle +|111\rangle +|100\rangle +5|110\rangle +|101\rangle +|010\rangle ).}
(
5
4
2
)
2
=
25
32
=
0.78125
{\displaystyle ({\frac {5}{4{\sqrt {2}}}})^{2}={\frac {25}{32}}=0.78125}
7
(
1
4
2
)
2
+
25
32
=
7
(
1
32
)
+
25
32
=
1.
{\displaystyle 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
(
1
2
|
ψ
⟩
+
1
2
|
110
⟩
)
=
(
1
−
2
|
110
⟩
⟨
110
|
)
(
1
2
|
ψ
⟩
+
1
2
|
110
⟩
)
=
{\displaystyle M({\frac {1}{2}}|\psi \rangle +{\frac {1}{\sqrt {2}}}|110\rangle )=(1-2|110\rangle \langle 110|)({\frac {1}{2}}|\psi \rangle +{\frac {1}{\sqrt {2}}}|110\rangle )=}
=
1
2
|
ψ
⟩
−
2
2
|
110
⟩
⟨
110
|
ψ
⟩
+
1
2
|
110
⟩
−
2
2
|
110
⟩
⟨
110
|
110
⟩
=
1
2
|
ψ
⟩
−
1
2
2
|
110
⟩
+
1
2
|
110
⟩
−
2
2
|
110
⟩
=
{\displaystyle ={\frac {1}{2}}|\psi \rangle -{\frac {2}{2}}|110\rangle \langle 110|\psi \rangle +{\frac {1}{\sqrt {2}}}|110\rangle -{\frac {2}{\sqrt {2}}}|110\rangle \langle 110|110\rangle ={\frac {1}{2}}|\psi \rangle -{\frac {1}{2{\sqrt {2}}}}|110\rangle +{\frac {1}{\sqrt {2}}}|110\rangle -{\frac {2}{\sqrt {2}}}|110\rangle =}
=
1
2
|
ψ
⟩
+
−
|
110
⟩
+
2
|
110
⟩
−
4
|
110
⟩
2
2
=
1
2
|
ψ
⟩
−
3
|
110
⟩
2
2
.
{\displaystyle ={\frac {1}{2}}|\psi \rangle +{\frac {-|110\rangle +2|110\rangle -4|110\rangle }{2{\sqrt {2}}}}={\frac {1}{2}}|\psi \rangle -{\frac {3|110\rangle }{2{\sqrt {2}}}}.}
Toliau praleisime tris pirmus kubitus pro B vartus:
t=5,
B
(
1
2
|
ψ
⟩
−
3
|
110
⟩
2
2
)
=
(
2
|
ψ
⟩
⟨
ψ
|
−
1
)
(
1
2
|
ψ
⟩
−
3
|
110
⟩
2
2
)
=
{\displaystyle B({\frac {1}{2}}|\psi \rangle -{\frac {3|110\rangle }{2{\sqrt {2}}}})=(2|\psi \rangle \langle \psi |-1)({\frac {1}{2}}|\psi \rangle -{\frac {3|110\rangle }{2{\sqrt {2}}}})=}
=
|
ψ
⟩
⟨
ψ
|
ψ
⟩
−
1
2
|
ψ
⟩
−
3
2
|
ψ
⟩
⟨
ψ
|
110
⟩
+
3
2
2
|
110
⟩
=
|
ψ
⟩
−
1
2
|
ψ
⟩
−
3
2
⋅
1
2
2
|
ψ
⟩
+
3
2
2
|
110
⟩
=
{\displaystyle =|\psi \rangle \langle \psi |\psi \rangle -{\frac {1}{2}}|\psi \rangle -{\frac {3}{\sqrt {2}}}|\psi \rangle \langle \psi |110\rangle +{\frac {3}{2{\sqrt {2}}}}|110\rangle =|\psi \rangle -{\frac {1}{2}}|\psi \rangle -{\frac {3}{\sqrt {2}}}\cdot {\frac {1}{2{\sqrt {2}}}}|\psi \rangle +{\frac {3}{2{\sqrt {2}}}}|110\rangle =}
=
4
|
ψ
⟩
−
2
|
ψ
⟩
−
3
|
ψ
⟩
4
+
3
2
2
|
110
⟩
=
−
1
4
|
ψ
⟩
+
3
2
2
|
110
⟩
.
{\displaystyle ={\frac {4|\psi \rangle -2|\psi \rangle -3|\psi \rangle }{4}}+{\frac {3}{2{\sqrt {2}}}}|110\rangle =-{\frac {1}{4}}|\psi \rangle +{\frac {3}{2{\sqrt {2}}}}|110\rangle .}
Tikimybė išmatuoti ieškomą buseną (|110>) yra:
(
−
1
4
⋅
1
2
2
+
3
2
2
)
2
=
(
−
1
8
2
+
3
2
2
)
2
=
(
−
1
+
3
⋅
4
8
2
)
2
=
(
11
8
2
)
2
=
0.9453125
{\displaystyle (-{\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}
7
(
−
1
8
2
)
2
+
(
11
8
2
)
2
=
7
64
⋅
2
+
121
128
=
7
+
121
128
=
1.
{\displaystyle 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
(
13
16
2
)
2
≈
0.330
{\displaystyle ({\frac {13}{16{\sqrt {2}}}})^{2}\approx 0.330}
visų elementų amplitudės pasidaro neigiamos (-), kas ir parodo, kad jau viršytas iteracijų G limitas.
Groverio algoritmui groverio iteracijų r reikia:
r
→
π
2
n
4
≈
2
n
{\displaystyle r\rightarrow {\frac {\pi {\sqrt {2^{n}}}}{4}}\approx {\sqrt {2^{n}}}}
r
→
π
2
3
4
≈
2.221441469
{\displaystyle r\rightarrow {\frac {\pi {\sqrt {2^{3}}}}{4}}\approx 2.221441469}
r
→
π
2
4
4
=
π
≈
3.141592654
{\displaystyle r\rightarrow {\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.
r
→
π
2
n
4
{\displaystyle r\rightarrow {\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
1
N
:
(
2
arccos
N
−
1
N
)
=
π
:
(
4
arcsin
1
N
)
−
0.5
{\displaystyle 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=2n , kur n kubitų skaičius.
Reikia žinoti kampą:
θ
=
2
arccos
(
1
−
1
2
n
)
=
2
arcsin
1
2
n
,
{\displaystyle \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
(
2
r
+
1
2
θ
)
|
t
⟩
{\displaystyle \sin({\frac {2r+1}{2}}\theta )|t\rangle }
kur t yra ieškomas elementas, r yra groverio iteracijų skaičius.
O tikimybė išmatuoti ieškomą elementą yra:
sin
2
(
2
r
+
1
2
θ
)
.
{\displaystyle \sin ^{2}({\frac {2r+1}{2}}\theta ).}
Visų likusių elementų amplitudė kartu sudėjus yra:
cos
(
2
r
+
1
2
θ
)
(
|
ψ
⟩
−
1
2
n
|
t
⟩
)
{\displaystyle \cos({\frac {2r+1}{2}}\theta )(|\psi \rangle -{\frac {1}{2^{n}}}|t\rangle )}
O tikimybė išmatuoti klaidingą atsakymą (būseną) yra:
cos
2
(
2
r
+
1
2
θ
)
.
{\displaystyle \cos ^{2}({\frac {2r+1}{2}}\theta ).}
θ
=
2
arccos
(
1
−
1
2
3
)
=
2
arccos
0.875
≈
0.722734247.
{\displaystyle \theta =2\arccos({\sqrt {1-{\frac {1}{2^{3}}}}})=2\arccos {\sqrt {0.875}}\approx 0.722734247.}
Tikimybė išmatuoti ieškomą elementą yra:
sin
2
(
2
⋅
2
+
1
2
0.722734247
)
=
sin
2
(
2.5
⋅
0.722734247
)
≈
0.972271824
2
=
0.9453125.
{\displaystyle \sin ^{2}({\frac {2\cdot 2+1}{2}}0.722734247)=\sin ^{2}(2.5\cdot 0.722734247)\approx 0.972271824^{2}=0.9453125.}
θ
=
2
arcsin
1
2
4
≈
0.50536051.
{\displaystyle \theta =2\arcsin {\frac {1}{\sqrt {2^{4}}}}\approx 0.50536051.}
Tikimybė išmatuoti ieškomą elementą yra:
sin
2
(
2
⋅
3
+
1
2
⋅
0.50536051
)
=
sin
2
(
3.5
⋅
0.50536051
)
≈
0.98046875
2
≈
0.961318969.
{\displaystyle \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
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 tikimybe po vienos groverio iteracijos G , galima naudotis šia formule:
(
3
N
−
4
N
N
)
2
{\displaystyle ({\frac {3N-4}{N{\sqrt {N}}}})^{2}}
Kur
N
=
2
n
{\displaystyle N=2^{n}}
n kubitų skaičius.
Pavyzdžiui, kai N=8:
(
3
⋅
8
−
4
8
8
)
2
=
0.78125
{\displaystyle ({\frac {3\cdot 8-4}{8{\sqrt {8}}}})^{2}=0.78125}
Kai N=16:
(
3
⋅
16
−
4
16
16
)
2
=
0.47265625
{\displaystyle ({\frac {3\cdot 16-4}{16{\sqrt {16}}}})^{2}=0.47265625}
Kai N=1024:
(
3
⋅
1024
−
4
1024
1024
)
2
≈
0.008766189
{\displaystyle ({\frac {3\cdot 1024-4}{1024{\sqrt {1024}}}})^{2}\approx 0.008766189}
Apytiksliai sužinoti teisingo atsakymo tikimybę po bilenkiek Groverio iteracijų galima pagal formulę:
r
2
2
n
{\displaystyle {\frac {r^{2}}{2^{n}}}}
Groverio algoritmo taikymas
Nors groverio algoritmas buvo pavadintas: ieškojimas nesutvarkytoje duomenų bazėje, bet kaip sako Deividas Doičas ieškojimui nesutvarkytoje duomenų bazėje, groverio algoritmas mažiausiai tinkamas naudoti, nes duomenų bazės visada yra sutvarkytos.
Groverio algoritmas gali nulaužti kai kurias kriptografijos sistemas, besiremenčias trumpiausio vektoriaus suradimu.
Groverio algoritmo schema su 2 kubitais
Vaizdas:Grover2qb.PNG Pirmi vartų, jungiančių 3 kubitus yra tofolio vartai , o antri jungiantys 2 kubitus yra CNOT vartai . Iš paveikslėlio matyti, kad įeinant dviems viršutiniams kubitams vienodiems, atsakymas gaunasi toks koks ir įėjimas, o įeinant dviems pirmiems kubitams skirtingiems, atsakymas gaunamas apverstas. Apatinis (trečias) kubitas nesikeičia.
Atsakymas gaunamas su 100% tikimybe, nes:
r
→
π
2
n
4
=
π
2
2
4
=
π
2
≈
1.570796327
{\displaystyle r\rightarrow {\frac {\pi {\sqrt {2^{n}}}}{4}}={\frac {\pi {\sqrt {2^{2}}}}{4}}={\frac {\pi }{2}}\approx 1.570796327}
θ
=
2
arcsin
1
2
n
=
2
arcsin
1
2
2
≈
1.047197551
{\displaystyle \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:
sin
2
(
2
⋅
r
+
1
2
⋅
θ
)
=
sin
2
(
2
⋅
1
+
1
2
⋅
1.047197551
)
=
sin
2
(
1.5
⋅
1.047197551
)
=
1
2
=
1.
{\displaystyle \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 atssakymo tikimybė):
r
=
π
:
(
4
arcsin
1
2
2
)
−
0.5
=
3.141592654
4
⋅
0.523598775
−
0.5
=
1.5
−
0.5
=
1
{\displaystyle 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}
Nuorodos
