Doičo-Džozo algoritmas yra kvantinis algoritmas , pasiūlytas David Deutsch ir Richard Jozsa 1992 m. Jis buvo vienas iš pirmų algoritmų sukurtų kvantiniams kompiuteriams , kuris naudodamas tokius reiškinius kaip superpozicija ir paralelizmas turėtų būti žymiai efektingesnis, nei klasikiniai algoritmai.
Doičo-Džozo algoritmas duoda eksponentinį paspartėjimą (atskirais atvejais ir tik tada kai reikia, kad suklydimo tikimybė būtų 0). Klasikiniam kompiuteriui, kad išspręsti tokią užduotį reikia
2
n
−
1
+
1
{\displaystyle 2^{n-1}+1}
n kubitų skaičius (be paskutinio kubito |1>). Pavyzdžiui, jei
n
=
1
{\displaystyle n=1}
k
=
2
1
−
1
+
1
=
2
{\displaystyle k=2^{1-1}+1=2}
n
=
1
{\displaystyle n=1}
n
=
2
{\displaystyle n=2}
k ≤
2
2
−
1
+
1
=
3
{\displaystyle 2^{2-1}+1=3}
n
=
3
{\displaystyle n=3}
k ≤
2
3
−
1
+
1
=
5
{\displaystyle 2^{3-1}+1=5}
n
=
4
{\displaystyle n=4}
k ≤
2
4
−
1
+
1
=
9
{\displaystyle 2^{4-1}+1=9}
n
=
5
{\displaystyle n=5}
k ≤
2
5
−
1
+
1
=
17
{\displaystyle 2^{5-1}+1=17}
Su tikimybiniu kompiuteriu galima nustatyti suklydymo tikimybę
ϵ
≤
(
1
2
)
k
−
1
{\displaystyle \epsilon \leq ({1 \over 2})^{k-1}}
k bandymų, kur
k
≤
2
n
−
1
+
1.
{\displaystyle k\leq 2^{n-1}+1.}
k
=
log
2
1
ϵ
+
1
{\displaystyle k=\log _{2}{1 \over \epsilon }+1}
ϵ
{\displaystyle \epsilon }
ϵ
≤
2
−
100
≈
10
−
30
.
{\displaystyle \epsilon \leq 2^{-100}\approx 10^{-30}.}
ne sprendžia greičiau (nei tikimybinis kompiuteris). Kad padaryti daugiau nei 100 užklausimų bitų/kubitų skaičius turi buti
>
8
{\displaystyle >8}
2
8
−
1
+
1
=
129
{\displaystyle 2^{8-1}+1=129}
Kadangi subalansuotų funkcijų gali būti eksponentiškai daugiau nei konstantų funkcijų (kurių, nepriklausomai nuo bitų/kubitų skaičiaus visada yra tik dvi), tai tokiu atvej net ir klasikinis kompiuteris už kvantinį kompiuterį nėra eksponentiškai lėtesnis, bet atotrukis kvantinio kompiuterio nuo klasikinio yra eksponentiškai mažas. Tačiau, jeigu parinkti, kad subalansuotų funkcijų būtų tiek pat kaip ir konstantų (tik 2), tai tada klasikinis kompiuteris yra eksponentiskai lėtesnis nei kvantinis kompiuteris.
Buvo pasiūlyta šį straipsnį ar skyrių, kaip parašytą vadovėlio stiliumi, perkelti į Vikiknygas . Taip pat galite šį straipsnį pritaikyti Vikipedijai - perrašyti enciklopediniu stiliumi .
Doičo algoritmas: funkcijos nustatymas: subalansuota ar konstanta. Praleidus per Hadamardo vartus |0>|1>=|01> gauname
1
2
(
|
0
⟩
+
|
1
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
1
2
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
.
{\displaystyle {1 \over {\sqrt {2}}}(|0\rangle +|1\rangle ){1 \over {\sqrt {2}}}(|0\rangle -|1\rangle )={1 \over 2}(|00\rangle -|01\rangle +|10\rangle -|11\rangle ).}
Toliau praleidus pro orakulą šią buseną, gauname
1
2
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⊕
f
?
(
x
)
⟩
−
|
1
⊕
f
?
(
x
)
⟩
)
=
{\displaystyle {1 \over 2}(|0\rangle +|1\rangle )(|0\oplus f_{?}(x)\rangle -|1\oplus f_{?}(x)\rangle )=}
=
1
2
(
|
0
⟩
|
0
⊕
f
?
(
0
)
⟩
−
|
0
⟩
|
1
⊕
f
?
(
0
)
⟩
+
|
1
⟩
|
0
⊕
f
?
(
1
)
⟩
−
|
1
⟩
|
1
⊕
f
?
(
1
)
⟩
)
.
{\displaystyle ={1 \over 2}(|0\rangle |0\oplus f_{?}(0)\rangle -|0\rangle |1\oplus f_{?}(0)\rangle +|1\rangle |0\oplus f_{?}(1)\rangle -|1\rangle |1\oplus f_{?}(1)\rangle ).}
Pavyzdžiui, apskaičiuosime
f
2
(
x
)
{\displaystyle f_{2}(x)}
1
2
(
|
0
⟩
|
0
⊕
f
2
(
0
)
⟩
−
|
0
⟩
|
1
⊕
f
2
(
0
)
⟩
+
|
1
⟩
|
0
⊕
f
2
(
1
)
⟩
−
|
1
⟩
|
1
⊕
f
2
(
1
)
⟩
)
=
{\displaystyle {1 \over 2}(|0\rangle |0\oplus f_{2}(0)\rangle -|0\rangle |1\oplus f_{2}(0)\rangle +|1\rangle |0\oplus f_{2}(1)\rangle -|1\rangle |1\oplus f_{2}(1)\rangle )=}
=
1
2
(
|
0
⟩
|
0
⊕
1
⟩
−
|
0
⟩
|
1
⊕
1
⟩
+
|
1
⟩
|
0
⊕
1
⟩
−
|
1
⟩
|
1
⊕
1
⟩
)
=
{\displaystyle ={1 \over 2}(|0\rangle |0\oplus 1\rangle -|0\rangle |1\oplus 1\rangle +|1\rangle |0\oplus 1\rangle -|1\rangle |1\oplus 1\rangle )=}
=
1
2
(
|
0
⟩
|
1
⟩
−
|
0
⟩
|
0
⟩
+
|
1
⟩
|
1
⟩
−
|
1
⟩
|
0
⟩
)
=
−
1
2
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
.
{\displaystyle ={1 \over 2}(|0\rangle |1\rangle -|0\rangle |0\rangle +|1\rangle |1\rangle -|1\rangle |0\rangle )=-{1 \over 2}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}
Toliau praleidžiame pro Hadamardo vartus šią būseną:
0.5
(
|
01
>
−
|
00
>
+
|
11
>
−
|
10
>
)
=
{\displaystyle 0.5(|01>-|00>+|11>-|10>)=}
=
0.5
(
0.5
(
|
0
>
+
|
1
>
)
(
|
0
>
−
|
1
>
)
−
0.5
(
|
0
>
+
|
1
>
)
(
|
0
>
+
|
1
>
)
+
0.5
(
|
0
>
−
|
1
>
)
(
|
0
>
−
|
1
>
)
−
0.5
(
|
0
>
−
|
1
>
)
(
|
0
>
+
|
1
>
)
)
=
{\displaystyle =0.5(0.5(|0>+|1>)(|0>-|1>)-0.5(|0>+|1>)(|0>+|1>)+0.5(|0>-|1>)(|0>-|1>)-0.5(|0>-|1>)(|0>+|1>))=}
=
0.25
(
(
|
00
>
−
|
01
>
+
|
10
>
−
|
11
>
)
−
(
|
00
>
+
|
01
>
+
|
10
>
+
|
11
>
)
+
(
|
00
>
−
|
01
>
−
|
10
>
+
|
11
>
)
−
(
|
00
>
+
|
01
>
−
|
10
>
−
|
11
>
)
)
=
{\displaystyle =0.25((|00>-|01>+|10>-|11>)-(|00>+|01>+|10>+|11>)+(|00>-|01>-|10>+|11>)-(|00>+|01>-|10>-|11>))=}
=
0.25
(
|
00
>
−
|
01
>
+
|
10
>
−
|
11
>
−
|
00
>
−
|
01
>
−
|
10
>
−
|
11
>
+
|
00
>
−
|
01
>
−
|
10
>
+
|
11
>
−
|
00
>
−
|
01
>
+
|
10
>
+
|
11
>
)
=
{\displaystyle =0.25(|00>-|01>+|10>-|11>-|00>-|01>-|10>-|11>+|00>-|01>-|10>+|11>-|00>-|01>+|10>+|11>)=}
=
0.25
(
−
4
|
01
>
)
=
−
|
01
>
.
{\displaystyle =0.25(-4|01>)=-|01>.}
Doičo algoritmas. Funkcijų „geležis“: Hadamardo vartai , Kvantiniai NOT vartai , CNOT vartai . Čia minusas reiškia fazę, tačiau fazė negali būti išmatuota, todėl atsakymas bus |01>. Kadangi pirmas kubitas yra |0> tai funkcija yra konstanta. Po antro kubito išėjimo superpozicijoje Hadamardo vartų galima ir nedėti ir jo nematuoti.
Apskaičiuosime
f
3
(
x
)
{\displaystyle f_{3}(x)}
|
0
⟩
|
1
⟩
→
1
2
(
|
0
⟩
+
|
1
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
1
2
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
→
{\displaystyle |0\rangle |1\rangle \to {1 \over {\sqrt {2}}}(|0\rangle +|1\rangle ){1 \over {\sqrt {2}}}(|0\rangle -|1\rangle )={1 \over 2}(|00\rangle -|01\rangle +|10\rangle -|11\rangle )\to }
→
1
2
(
|
0
⟩
|
0
⊕
f
3
(
0
)
⟩
−
|
0
⟩
|
1
⊕
f
3
(
0
)
⟩
+
|
1
⟩
|
0
⊕
f
3
(
1
)
⟩
−
|
1
⟩
|
1
⊕
f
3
(
1
)
⟩
)
=
{\displaystyle \to {1 \over 2}(|0\rangle |0\oplus f_{3}(0)\rangle -|0\rangle |1\oplus f_{3}(0)\rangle +|1\rangle |0\oplus f_{3}(1)\rangle -|1\rangle |1\oplus f_{3}(1)\rangle )=}
=
1
2
(
|
0
⟩
|
0
⊕
0
⟩
−
|
0
⟩
|
1
⊕
0
⟩
+
|
1
⟩
|
0
⊕
1
⟩
−
|
1
⟩
|
1
⊕
1
⟩
)
=
{\displaystyle ={1 \over 2}(|0\rangle |0\oplus 0\rangle -|0\rangle |1\oplus 0\rangle +|1\rangle |0\oplus 1\rangle -|1\rangle |1\oplus 1\rangle )=}
=
1
2
(
|
0
⟩
|
0
⟩
−
|
0
⟩
|
1
⟩
+
|
1
⟩
|
1
⟩
−
|
1
⟩
|
0
⟩
)
=
1
2
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
|
1
⟩
|
1
⟩
.
{\displaystyle ={1 \over 2}(|0\rangle |0\rangle -|0\rangle |1\rangle +|1\rangle |1\rangle -|1\rangle |0\rangle )={1 \over 2}(|0\rangle -|1\rangle )(|0\rangle -|1\rangle )\to |1\rangle |1\rangle .}
Pirmas kubitas |1>, taigi funkcija subalansuota.
Apskaičiuosime
f
4
(
x
)
{\displaystyle f_{4}(x)}
|
0
⟩
|
1
⟩
→
1
2
(
|
0
⟩
+
|
1
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
1
2
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
→
{\displaystyle |0\rangle |1\rangle \to {1 \over {\sqrt {2}}}(|0\rangle +|1\rangle ){1 \over {\sqrt {2}}}(|0\rangle -|1\rangle )={1 \over 2}(|00\rangle -|01\rangle +|10\rangle -|11\rangle )\to }
→
1
2
(
|
0
⟩
|
0
⊕
f
4
(
0
)
⟩
−
|
0
⟩
|
1
⊕
f
4
(
0
)
⟩
+
|
1
⟩
|
0
⊕
f
4
(
1
)
⟩
−
|
1
⟩
|
1
⊕
f
4
(
1
)
⟩
)
=
{\displaystyle \to {1 \over 2}(|0\rangle |0\oplus f_{4}(0)\rangle -|0\rangle |1\oplus f_{4}(0)\rangle +|1\rangle |0\oplus f_{4}(1)\rangle -|1\rangle |1\oplus f_{4}(1)\rangle )=}
=
1
2
(
|
0
⟩
|
0
⊕
1
⟩
−
|
0
⟩
|
1
⊕
1
⟩
+
|
1
⟩
|
0
⊕
0
⟩
−
|
1
⟩
|
1
⊕
0
⟩
)
=
{\displaystyle ={1 \over 2}(|0\rangle |0\oplus 1\rangle -|0\rangle |1\oplus 1\rangle +|1\rangle |0\oplus 0\rangle -|1\rangle |1\oplus 0\rangle )=}
=
1
2
(
|
01
⟩
−
|
00
⟩
+
|
10
⟩
−
|
11
⟩
)
=
−
1
2
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
−
|
1
⟩
1
2
(
|
0
⟩
−
|
1
⟩
)
=
−
|
11
⟩
→
|
11
⟩
.
{\displaystyle ={1 \over 2}(|01\rangle -|00\rangle +|10\rangle -|11\rangle )=-{1 \over 2}(|0\rangle -|1\rangle )(|0\rangle -|1\rangle )\to -|1\rangle {1 \over {\sqrt {2}}}(|0\rangle -|1\rangle )=-|11\rangle \to |11\rangle .}
Pirmas kubitas |1>, taigi funkcija subalansuota.
Funkcijos nustatymas klasikiniu algoritmu. Funkcijos nustatymas su klasikiniais loginiais elementais . Apskaičiuosime
f
1
(
x
)
{\displaystyle f_{1}(x)}
|
0
⟩
|
1
⟩
→
1
2
(
|
0
⟩
+
|
1
⟩
)
1
2
(
|
0
⟩
−
|
1
⟩
)
=
1
2
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
→
{\displaystyle |0\rangle |1\rangle \to {1 \over {\sqrt {2}}}(|0\rangle +|1\rangle ){1 \over {\sqrt {2}}}(|0\rangle -|1\rangle )={1 \over 2}(|00\rangle -|01\rangle +|10\rangle -|11\rangle )\to }
→
1
2
(
|
0
⟩
|
0
⊕
f
1
(
0
)
⟩
−
|
0
⟩
|
1
⊕
f
1
(
0
)
⟩
+
|
1
⟩
|
0
⊕
f
1
(
1
)
⟩
−
|
1
⟩
|
1
⊕
f
1
(
1
)
⟩
)
=
{\displaystyle \to {1 \over 2}(|0\rangle |0\oplus f_{1}(0)\rangle -|0\rangle |1\oplus f_{1}(0)\rangle +|1\rangle |0\oplus f_{1}(1)\rangle -|1\rangle |1\oplus f_{1}(1)\rangle )=}
=
1
2
(
|
0
⟩
|
0
⊕
0
⟩
−
|
0
⟩
|
1
⊕
0
⟩
+
|
1
⟩
|
0
⊕
0
⟩
−
|
1
⟩
|
1
⊕
0
⟩
)
=
{\displaystyle ={1 \over 2}(|0\rangle |0\oplus 0\rangle -|0\rangle |1\oplus 0\rangle +|1\rangle |0\oplus 0\rangle -|1\rangle |1\oplus 0\rangle )=}
=
1
2
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
=
1
2
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
|
01
⟩
.
{\displaystyle ={1 \over 2}(|00\rangle -|01\rangle +|10\rangle -|11\rangle )={1 \over 2}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )\to |01\rangle .}
Pirmas kubitas |0>, taigi funkcija konstanta.
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
x
=
0
{\displaystyle x=0}
0
1
0
1
x
=
1
{\displaystyle x=1}
0
1
1
0
Klasikiniu atveju neįmanoma nustatyti, ar funkcija konstanta (
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
Kita vertus, klasikinis algoritmas po dviejų paleidimų nustato ne tik funkcijos rušį (subalansuota ar konstanta), bet ir pačią funciją (pvz.,
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
in
00
out
00
01
10
11
rezultatas
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
pirmas bitas negali pasikeisti
pirmas bitas negali pasikeisti
in
01
out
00
01
10
11
resultatas
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
pirmas bitas negali pasikeisti
pirmas bitas negali pasikeisti
in
10
out
00
01
10
11
resultatas
pirmas bitas negali pasikeisti
pirmas bitas negali pasikeisti
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
in
11
out
00
01
10
11
resultatas
pirmas bitas negali pasikeisti
pirmas bitas negali pasikeisti
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
0
⊕
0
=
0
,
{\displaystyle 0\oplus 0=0,}
0
⊕
1
=
1
,
{\displaystyle 0\oplus 1=1,}
1
⊕
0
=
1
,
{\displaystyle 1\oplus 0=1,}
1
⊕
1
=
0.
{\displaystyle 1\oplus 1=0.}
Su kvantiniu kompiuteriu užtenka 1 paleidimo ir 2 pirmų kubitų matavimo, o su klasikiniu kompiuteriu reikia atlikti 4 paleidimus ir kiekvieną kartą matuoti tik 1 trečią kubitą, kad nustatyti ar funkcija
f
(
x
1
,
x
2
)
=
f
(
x
)
{\displaystyle f(x_{1},x_{2})=f(x)}
|
0
>
|
0
>
|
1
>=
|
001
>
{\displaystyle |0>|0>|1>=|001>}
Hadamardo vartus :
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
=
{\displaystyle {\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )={\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|00\rangle -|01\rangle +|10\rangle -|11\rangle )=}
=
1
2
3
(
|
000
⟩
−
|
001
⟩
+
|
010
⟩
−
|
011
⟩
+
|
100
⟩
−
|
101
⟩
+
|
110
⟩
−
|
111
⟩
)
.
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|000\rangle -|001\rangle +|010\rangle -|011\rangle +|100\rangle -|101\rangle +|110\rangle -|111\rangle ).}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
y
{\displaystyle y}
Controlled-U vartus
|
x
1
⟩
|
x
2
⟩
|
y
⟩
→
|
x
1
⟩
|
x
2
⟩
|
y
⊕
f
(
x
1
,
x
2
)
⟩
:
{\displaystyle |x_{1}\rangle |x_{2}\rangle |y\rangle \to |x_{1}\rangle |x_{2}\rangle |y\oplus f(x_{1},x_{2})\rangle :}
1
2
3
(
|
00
⟩
|
0
⊕
f
(
x
1
,
x
2
)
⟩
−
|
00
⟩
|
1
⊕
f
(
x
1
,
x
2
)
⟩
+
|
01
⟩
|
0
⊕
f
(
x
1
,
x
2
)
⟩
−
|
01
⟩
|
1
⊕
f
(
x
1
,
x
2
)
⟩
+
{\displaystyle {\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus f(x_{1},x_{2})\rangle -|00\rangle |1\oplus f(x_{1},x_{2})\rangle +|01\rangle |0\oplus f(x_{1},x_{2})\rangle -|01\rangle |1\oplus f(x_{1},x_{2})\rangle +}
+
|
10
⟩
|
0
⊕
f
(
x
1
,
x
2
)
⟩
−
|
10
⟩
|
1
⊕
f
(
x
1
,
x
2
)
⟩
+
|
11
⟩
|
0
⊕
f
(
x
1
,
x
2
)
⟩
−
|
11
⟩
|
1
⊕
f
(
x
1
,
x
2
)
⟩
)
.
{\displaystyle +|10\rangle |0\oplus f(x_{1},x_{2})\rangle -|10\rangle |1\oplus f(x_{1},x_{2})\rangle +|11\rangle |0\oplus f(x_{1},x_{2})\rangle -|11\rangle |1\oplus f(x_{1},x_{2})\rangle ).}
Apskaičiuosime
f
2
(
x
1
,
x
2
)
=
f
2
(
x
)
=
1
{\displaystyle f_{2}(x_{1},x_{2})=f_{2}(x)=1}
|
001
⟩
→
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle |001\rangle \to {\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )=}
=
1
2
3
(
|
000
⟩
−
|
001
⟩
+
|
010
⟩
−
|
011
⟩
+
|
100
⟩
−
|
101
⟩
+
|
110
⟩
−
|
111
⟩
)
→
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|000\rangle -|001\rangle +|010\rangle -|011\rangle +|100\rangle -|101\rangle +|110\rangle -|111\rangle )\to }
→
1
2
3
(
|
00
⟩
|
0
⊕
f
2
(
x
)
⟩
−
|
00
⟩
|
1
⊕
f
2
(
x
)
⟩
+
|
01
⟩
|
0
⊕
f
2
(
x
)
⟩
−
|
01
⟩
|
1
⊕
f
2
(
x
)
⟩
+
{\displaystyle \to {\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus f_{2}(x)\rangle -|00\rangle |1\oplus f_{2}(x)\rangle +|01\rangle |0\oplus f_{2}(x)\rangle -|01\rangle |1\oplus f_{2}(x)\rangle +}
+
|
10
⟩
|
0
⊕
f
2
(
x
)
⟩
−
|
10
⟩
|
1
⊕
f
2
(
x
)
⟩
+
|
11
⟩
|
0
⊕
f
2
(
x
)
⟩
−
|
11
⟩
|
1
⊕
f
2
(
x
)
⟩
)
=
{\displaystyle +|10\rangle |0\oplus f_{2}(x)\rangle -|10\rangle |1\oplus f_{2}(x)\rangle +|11\rangle |0\oplus f_{2}(x)\rangle -|11\rangle |1\oplus f_{2}(x)\rangle )=}
=
1
2
3
(
|
00
⟩
|
0
⊕
1
⟩
−
|
00
⟩
|
1
⊕
1
⟩
+
|
01
⟩
|
0
⊕
1
⟩
−
|
01
⟩
|
1
⊕
1
⟩
+
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus 1\rangle -|00\rangle |1\oplus 1\rangle +|01\rangle |0\oplus 1\rangle -|01\rangle |1\oplus 1\rangle +}
+
|
10
⟩
|
0
⊕
1
⟩
−
|
10
⟩
|
1
⊕
1
⟩
+
|
11
⟩
|
0
⊕
1
⟩
−
|
11
⟩
|
1
⊕
1
⟩
)
=
{\displaystyle +|10\rangle |0\oplus 1\rangle -|10\rangle |1\oplus 1\rangle +|11\rangle |0\oplus 1\rangle -|11\rangle |1\oplus 1\rangle )=}
=
1
2
3
(
|
001
⟩
−
|
000
⟩
+
|
011
⟩
−
|
010
⟩
+
|
101
⟩
−
|
100
⟩
+
|
111
⟩
−
|
110
⟩
)
=
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|001\rangle -|000\rangle +|011\rangle -|010\rangle +|101\rangle -|100\rangle +|111\rangle -|110\rangle )=}
=
−
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
−
|
001
⟩
→
|
001
⟩
.
{\displaystyle =-{\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )\to -|001\rangle \to |001\rangle .}
Abu pirmi kubitai |00>, todel funkcija
f
2
(
x
1
,
x
2
)
{\displaystyle f_{2}(x_{1},x_{2})}
Apskaičiuosime
f
3
(
x
1
,
x
2
)
=
f
3
(
x
)
{\displaystyle f_{3}(x_{1},x_{2})=f_{3}(x)}
|
001
⟩
→
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle |001\rangle \to {\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )=}
=
1
2
3
(
|
000
⟩
−
|
001
⟩
+
|
010
⟩
−
|
011
⟩
+
|
100
⟩
−
|
101
⟩
+
|
110
⟩
−
|
111
⟩
)
→
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|000\rangle -|001\rangle +|010\rangle -|011\rangle +|100\rangle -|101\rangle +|110\rangle -|111\rangle )\to }
→
1
2
3
(
|
00
⟩
|
0
⊕
f
3
(
x
)
⟩
−
|
00
⟩
|
1
⊕
f
3
(
x
)
⟩
+
|
01
⟩
|
0
⊕
f
3
(
x
)
⟩
−
|
01
⟩
|
1
⊕
f
3
(
x
)
⟩
+
{\displaystyle \to {\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus f_{3}(x)\rangle -|00\rangle |1\oplus f_{3}(x)\rangle +|01\rangle |0\oplus f_{3}(x)\rangle -|01\rangle |1\oplus f_{3}(x)\rangle +}
+
|
10
⟩
|
0
⊕
f
3
(
x
)
⟩
−
|
10
⟩
|
1
⊕
f
3
(
x
)
⟩
+
|
11
⟩
|
0
⊕
f
3
(
x
)
⟩
−
|
11
⟩
|
1
⊕
f
3
(
x
)
⟩
)
=
{\displaystyle +|10\rangle |0\oplus f_{3}(x)\rangle -|10\rangle |1\oplus f_{3}(x)\rangle +|11\rangle |0\oplus f_{3}(x)\rangle -|11\rangle |1\oplus f_{3}(x)\rangle )=}
=
1
2
3
(
|
00
⟩
|
0
⊕
0
⟩
−
|
00
⟩
|
1
⊕
0
⟩
+
|
01
⟩
|
0
⊕
0
⟩
−
|
01
⟩
|
1
⊕
0
⟩
+
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus 0\rangle -|00\rangle |1\oplus 0\rangle +|01\rangle |0\oplus 0\rangle -|01\rangle |1\oplus 0\rangle +}
+
|
10
⟩
|
0
⊕
1
⟩
−
|
10
⟩
|
1
⊕
1
⟩
+
|
11
⟩
|
0
⊕
1
⟩
−
|
11
⟩
|
1
⊕
1
⟩
)
=
{\displaystyle +|10\rangle |0\oplus 1\rangle -|10\rangle |1\oplus 1\rangle +|11\rangle |0\oplus 1\rangle -|11\rangle |1\oplus 1\rangle )=}
=
1
2
3
(
|
000
⟩
−
|
001
⟩
+
|
010
⟩
−
|
011
⟩
+
|
101
⟩
−
|
100
⟩
+
|
111
⟩
−
|
110
⟩
)
=
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|000\rangle -|001\rangle +|010\rangle -|011\rangle +|101\rangle -|100\rangle +|111\rangle -|110\rangle )=}
=
1
2
3
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
|
101
⟩
.
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|0\rangle -|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )\to |101\rangle .}
Funkcija
f
3
(
x
)
{\displaystyle f_{3}(x)}
Apskaičiuosime
f
5
(
x
1
,
x
2
)
=
f
5
(
x
)
{\displaystyle f_{5}(x_{1},x_{2})=f_{5}(x)}
|
001
⟩
→
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle |001\rangle \to {\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )=}
=
1
2
3
(
|
000
⟩
−
|
001
⟩
+
|
010
⟩
−
|
011
⟩
+
|
100
⟩
−
|
101
⟩
+
|
110
⟩
−
|
111
⟩
)
→
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|000\rangle -|001\rangle +|010\rangle -|011\rangle +|100\rangle -|101\rangle +|110\rangle -|111\rangle )\to }
→
1
2
3
(
|
00
⟩
|
0
⊕
f
5
(
x
)
⟩
−
|
00
⟩
|
1
⊕
f
5
(
x
)
⟩
+
|
01
⟩
|
0
⊕
f
5
(
x
)
⟩
−
|
01
⟩
|
1
⊕
f
5
(
x
)
⟩
+
{\displaystyle \to {\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus f_{5}(x)\rangle -|00\rangle |1\oplus f_{5}(x)\rangle +|01\rangle |0\oplus f_{5}(x)\rangle -|01\rangle |1\oplus f_{5}(x)\rangle +}
+
|
10
⟩
|
0
⊕
f
5
(
x
)
⟩
−
|
10
⟩
|
1
⊕
f
5
(
x
)
⟩
+
|
11
⟩
|
0
⊕
f
5
(
x
)
⟩
−
|
11
⟩
|
1
⊕
f
5
(
x
)
⟩
)
=
{\displaystyle +|10\rangle |0\oplus f_{5}(x)\rangle -|10\rangle |1\oplus f_{5}(x)\rangle +|11\rangle |0\oplus f_{5}(x)\rangle -|11\rangle |1\oplus f_{5}(x)\rangle )=}
=
1
2
3
(
|
00
⟩
|
0
⊕
0
⟩
−
|
00
⟩
|
1
⊕
0
⟩
+
|
01
⟩
|
0
⊕
1
⟩
−
|
01
⟩
|
1
⊕
1
⟩
+
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus 0\rangle -|00\rangle |1\oplus 0\rangle +|01\rangle |0\oplus 1\rangle -|01\rangle |1\oplus 1\rangle +}
+
|
10
⟩
|
0
⊕
0
⟩
−
|
10
⟩
|
1
⊕
0
⟩
+
|
11
⟩
|
0
⊕
1
⟩
−
|
11
⟩
|
1
⊕
1
⟩
)
=
{\displaystyle +|10\rangle |0\oplus 0\rangle -|10\rangle |1\oplus 0\rangle +|11\rangle |0\oplus 1\rangle -|11\rangle |1\oplus 1\rangle )=}
=
1
2
3
(
|
000
⟩
−
|
001
⟩
+
|
011
⟩
−
|
010
⟩
+
|
100
⟩
−
|
101
⟩
+
|
111
⟩
−
|
110
⟩
)
=
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|000\rangle -|001\rangle +|011\rangle -|010\rangle +|100\rangle -|101\rangle +|111\rangle -|110\rangle )=}
=
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
|
011
⟩
.
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )(|0\rangle -|1\rangle )\to |011\rangle .}
Pirmi du kubitai yra išmatuoti |01>, todėl funkcija
f
5
(
x
)
{\displaystyle f_{5}(x)}
Apskaičiuosime
f
8
(
x
1
,
x
2
)
=
f
8
(
x
)
{\displaystyle f_{8}(x_{1},x_{2})=f_{8}(x)}
|
001
⟩
→
1
2
3
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle |001\rangle \to {\frac {1}{\sqrt {2^{3}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )=}
=
1
2
3
(
|
000
⟩
−
|
001
⟩
+
|
010
⟩
−
|
011
⟩
+
|
100
⟩
−
|
101
⟩
+
|
110
⟩
−
|
111
⟩
)
→
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|000\rangle -|001\rangle +|010\rangle -|011\rangle +|100\rangle -|101\rangle +|110\rangle -|111\rangle )\to }
→
1
2
3
(
|
00
⟩
|
0
⊕
f
8
(
x
)
⟩
−
|
00
⟩
|
1
⊕
f
8
(
x
)
⟩
+
|
01
⟩
|
0
⊕
f
8
(
x
)
⟩
−
|
01
⟩
|
1
⊕
f
8
(
x
)
⟩
+
{\displaystyle \to {\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus f_{8}(x)\rangle -|00\rangle |1\oplus f_{8}(x)\rangle +|01\rangle |0\oplus f_{8}(x)\rangle -|01\rangle |1\oplus f_{8}(x)\rangle +}
+
|
10
⟩
|
0
⊕
f
8
(
x
)
⟩
−
|
10
⟩
|
1
⊕
f
8
(
x
)
⟩
+
|
11
⟩
|
0
⊕
f
8
(
x
)
⟩
−
|
11
⟩
|
1
⊕
f
8
(
x
)
⟩
)
=
{\displaystyle +|10\rangle |0\oplus f_{8}(x)\rangle -|10\rangle |1\oplus f_{8}(x)\rangle +|11\rangle |0\oplus f_{8}(x)\rangle -|11\rangle |1\oplus f_{8}(x)\rangle )=}
=
1
2
3
(
|
00
⟩
|
0
⊕
1
⟩
−
|
00
⟩
|
1
⊕
1
⟩
+
|
01
⟩
|
0
⊕
0
⟩
−
|
01
⟩
|
1
⊕
0
⟩
+
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|00\rangle |0\oplus 1\rangle -|00\rangle |1\oplus 1\rangle +|01\rangle |0\oplus 0\rangle -|01\rangle |1\oplus 0\rangle +}
+
|
10
⟩
|
0
⊕
0
⟩
−
|
10
⟩
|
1
⊕
0
⟩
+
|
11
⟩
|
0
⊕
1
⟩
−
|
11
⟩
|
1
⊕
1
⟩
)
=
{\displaystyle +|10\rangle |0\oplus 0\rangle -|10\rangle |1\oplus 0\rangle +|11\rangle |0\oplus 1\rangle -|11\rangle |1\oplus 1\rangle )=}
=
1
2
3
(
|
001
⟩
−
|
000
⟩
+
|
010
⟩
−
|
011
⟩
+
|
100
⟩
−
|
101
⟩
+
|
111
⟩
−
|
110
⟩
)
=
{\displaystyle ={\frac {1}{\sqrt {2^{3}}}}(|001\rangle -|000\rangle +|010\rangle -|011\rangle +|100\rangle -|101\rangle +|111\rangle -|110\rangle )=}
=
−
1
2
3
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
−
|
111
⟩
→
|
111
⟩
.
{\displaystyle =-{\frac {1}{\sqrt {2^{3}}}}(|0\rangle -|1\rangle )(|0\rangle -|1\rangle )(|0\rangle -|1\rangle )\to -|111\rangle \to |111\rangle .}
Funkcija
f
8
(
x
)
{\displaystyle f_{8}(x)}
Funkcijos klasikinio kompiuterio, kad viską paversti kvantiniu iš priekio ir iš galo reikia pridėti Hadamardo vartus . Funkcijos
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
f
5
(
x
)
{\displaystyle f_{5}(x)}
f
6
(
x
)
{\displaystyle f_{6}(x)}
f
7
(
x
)
{\displaystyle f_{7}(x)}
f
8
(
x
)
{\displaystyle f_{8}(x)}
x
f
(
x
1
,
x
2
)
=
f
(
x
)
{\displaystyle f(x_{1},x_{2})=f(x)}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
f
5
(
x
)
{\displaystyle f_{5}(x)}
f
6
(
x
)
{\displaystyle f_{6}(x)}
f
7
(
x
)
{\displaystyle f_{7}(x)}
f
8
(
x
)
{\displaystyle f_{8}(x)}
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
1
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
f
5
(
x
)
{\displaystyle f_{5}(x)}
f
6
(
x
)
{\displaystyle f_{6}(x)}
f
7
(
x
)
{\displaystyle f_{7}(x)}
f
8
(
x
)
{\displaystyle f_{8}(x)}
Tarkime, turime tokį įėjimą:
|0>|0>|0>|1>=|0001>.
Praleileidžiame visus kubitus pro Hadamardo vartus :
1
2
4
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
1
2
4
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
=
{\displaystyle {\frac {1}{\sqrt {2^{4}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )={\frac {1}{\sqrt {2^{4}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|00\rangle -|01\rangle +|10\rangle -|11\rangle )=}
=
1
2
4
(
|
0
⟩
+
|
1
⟩
)
(
|
000
⟩
−
|
001
⟩
+
|
010
⟩
−
|
011
⟩
+
|
100
⟩
−
|
101
⟩
+
|
110
⟩
−
|
111
⟩
)
=
{\displaystyle ={\frac {1}{\sqrt {2^{4}}}}(|0\rangle +|1\rangle )(|000\rangle -|001\rangle +|010\rangle -|011\rangle +|100\rangle -|101\rangle +|110\rangle -|111\rangle )=}
=
1
2
4
(
|
0000
⟩
−
|
0001
⟩
+
|
0010
⟩
−
|
0011
⟩
+
|
0100
⟩
−
|
0101
⟩
+
|
0110
⟩
−
|
0111
⟩
+
{\displaystyle ={\frac {1}{\sqrt {2^{4}}}}(|0000\rangle -|0001\rangle +|0010\rangle -|0011\rangle +|0100\rangle -|0101\rangle +|0110\rangle -|0111\rangle +}
+
|
1000
⟩
−
|
1001
⟩
+
|
1010
⟩
−
|
1011
⟩
+
|
1100
⟩
−
|
1101
⟩
+
|
1110
⟩
−
|
1111
⟩
)
.
{\displaystyle +|1000\rangle -|1001\rangle +|1010\rangle -|1011\rangle +|1100\rangle -|1101\rangle +|1110\rangle -|1111\rangle ).}
Toliau praleidžiame per funkciją
|
x
1
⟩
|
x
2
⟩
|
x
3
⟩
|
y
⟩
→
|
x
1
⟩
|
x
2
⟩
|
x
3
⟩
|
y
⊕
f
(
x
)
⟩
{\displaystyle |x_{1}\rangle |x_{2}\rangle |x_{3}\rangle |y\rangle \to |x_{1}\rangle |x_{2}\rangle |x_{3}\rangle |y\oplus f(x)\rangle }
f
(
x
)
=
f
(
x
1
,
x
2
,
x
3
)
{\displaystyle f(x)=f(x_{1},x_{2},x_{3})}
1
2
4
(
|
000
⟩
|
0
⊕
f
(
x
)
⟩
−
|
000
⟩
|
1
⊕
f
(
x
)
⟩
+
|
001
⟩
|
0
⊕
f
(
x
)
⟩
−
|
001
⟩
|
1
⊕
f
(
x
)
⟩
+
{\displaystyle {\frac {1}{\sqrt {2^{4}}}}(|000\rangle |0\oplus f(x)\rangle -|000\rangle |1\oplus f(x)\rangle +|001\rangle |0\oplus f(x)\rangle -|001\rangle |1\oplus f(x)\rangle +}
+
|
010
⟩
|
0
⊕
f
(
x
)
⟩
−
|
010
⟩
|
1
⊕
f
(
x
)
⟩
+
|
011
⟩
|
0
⊕
f
(
x
)
⟩
−
|
011
⟩
|
1
⊕
f
(
x
)
⟩
+
{\displaystyle +|010\rangle |0\oplus f(x)\rangle -|010\rangle |1\oplus f(x)\rangle +|011\rangle |0\oplus f(x)\rangle -|011\rangle |1\oplus f(x)\rangle +}
+
|
100
⟩
|
0
⊕
f
(
x
)
⟩
−
|
100
⟩
|
1
⊕
f
(
x
)
⟩
+
|
101
⟩
|
0
⊕
f
(
x
)
⟩
−
|
101
⟩
|
1
⊕
f
(
x
)
⟩
+
{\displaystyle +|100\rangle |0\oplus f(x)\rangle -|100\rangle |1\oplus f(x)\rangle +|101\rangle |0\oplus f(x)\rangle -|101\rangle |1\oplus f(x)\rangle +}
+
|
110
⟩
|
0
⊕
f
(
x
)
⟩
−
|
110
⟩
|
1
⊕
f
(
x
)
⟩
+
|
111
⟩
|
0
⊕
f
(
x
)
⟩
−
|
111
⟩
|
1
⊕
f
(
x
)
⟩
)
.
{\displaystyle +|110\rangle |0\oplus f(x)\rangle -|110\rangle |1\oplus f(x)\rangle +|111\rangle |0\oplus f(x)\rangle -|111\rangle |1\oplus f(x)\rangle ).}
Apskaičiuosime, pavyzdžiui,
f
7
(
x
)
=
f
7
(
x
1
,
x
2
,
x
3
)
{\displaystyle f_{7}(x)=f_{7}(x_{1},x_{2},x_{3})}
|
0001
⟩
→
1
2
4
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle |0001\rangle \to {\frac {1}{\sqrt {2^{4}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )=}
=
1
2
4
(
|
0000
⟩
−
|
0001
⟩
+
|
0010
⟩
−
|
0011
⟩
+
|
0100
⟩
−
|
0101
⟩
+
|
0110
⟩
−
|
0111
⟩
+
{\displaystyle ={\frac {1}{\sqrt {2^{4}}}}(|0000\rangle -|0001\rangle +|0010\rangle -|0011\rangle +|0100\rangle -|0101\rangle +|0110\rangle -|0111\rangle +}
+
|
1000
⟩
−
|
1001
⟩
+
|
1010
⟩
−
|
1011
⟩
+
|
1100
⟩
−
|
1101
⟩
+
|
1110
⟩
−
|
1111
⟩
)
→
{\displaystyle +|1000\rangle -|1001\rangle +|1010\rangle -|1011\rangle +|1100\rangle -|1101\rangle +|1110\rangle -|1111\rangle )\to }
→
1
2
4
(
|
000
⟩
|
0
⊕
f
7
(
x
)
⟩
−
|
000
⟩
|
1
⊕
f
7
(
x
)
⟩
+
|
001
⟩
|
0
⊕
f
7
(
x
)
⟩
−
|
001
⟩
|
1
⊕
f
7
(
x
)
⟩
+
{\displaystyle \to {\frac {1}{\sqrt {2^{4}}}}(|000\rangle |0\oplus f_{7}(x)\rangle -|000\rangle |1\oplus f_{7}(x)\rangle +|001\rangle |0\oplus f_{7}(x)\rangle -|001\rangle |1\oplus f_{7}(x)\rangle +}
+
|
010
⟩
|
0
⊕
f
7
(
x
)
⟩
−
|
010
⟩
|
1
⊕
f
7
(
x
)
⟩
+
|
011
⟩
|
0
⊕
f
7
(
x
)
⟩
−
|
011
⟩
|
1
⊕
f
7
(
x
)
⟩
+
{\displaystyle +|010\rangle |0\oplus f_{7}(x)\rangle -|010\rangle |1\oplus f_{7}(x)\rangle +|011\rangle |0\oplus f_{7}(x)\rangle -|011\rangle |1\oplus f_{7}(x)\rangle +}
+
|
100
⟩
|
0
⊕
f
7
(
x
)
⟩
−
|
100
⟩
|
1
⊕
f
7
(
x
)
⟩
+
|
101
⟩
|
0
⊕
f
7
(
x
)
⟩
−
|
101
⟩
|
1
⊕
f
7
(
x
)
⟩
+
{\displaystyle +|100\rangle |0\oplus f_{7}(x)\rangle -|100\rangle |1\oplus f_{7}(x)\rangle +|101\rangle |0\oplus f_{7}(x)\rangle -|101\rangle |1\oplus f_{7}(x)\rangle +}
+
|
110
⟩
|
0
⊕
f
7
(
x
)
⟩
−
|
110
⟩
|
1
⊕
f
7
(
x
)
⟩
+
|
111
⟩
|
0
⊕
f
7
(
x
)
⟩
−
|
111
⟩
|
1
⊕
f
7
(
x
)
⟩
)
=
{\displaystyle +|110\rangle |0\oplus f_{7}(x)\rangle -|110\rangle |1\oplus f_{7}(x)\rangle +|111\rangle |0\oplus f_{7}(x)\rangle -|111\rangle |1\oplus f_{7}(x)\rangle )=}
=
1
2
4
(
|
000
⟩
|
0
⊕
0
⟩
−
|
000
⟩
|
1
⊕
0
⟩
+
|
001
⟩
|
0
⊕
1
⟩
−
|
001
⟩
|
1
⊕
1
⟩
+
{\displaystyle ={\frac {1}{\sqrt {2^{4}}}}(|000\rangle |0\oplus 0\rangle -|000\rangle |1\oplus 0\rangle +|001\rangle |0\oplus 1\rangle -|001\rangle |1\oplus 1\rangle +}
+
|
010
⟩
|
0
⊕
0
⟩
−
|
010
⟩
|
1
⊕
0
⟩
+
|
011
⟩
|
0
⊕
1
⟩
−
|
011
⟩
|
1
⊕
1
⟩
+
{\displaystyle +|010\rangle |0\oplus 0\rangle -|010\rangle |1\oplus 0\rangle +|011\rangle |0\oplus 1\rangle -|011\rangle |1\oplus 1\rangle +}
+
|
100
⟩
|
0
⊕
0
⟩
−
|
100
⟩
|
1
⊕
0
⟩
+
|
101
⟩
|
0
⊕
1
⟩
−
|
101
⟩
|
1
⊕
1
⟩
+
{\displaystyle +|100\rangle |0\oplus 0\rangle -|100\rangle |1\oplus 0\rangle +|101\rangle |0\oplus 1\rangle -|101\rangle |1\oplus 1\rangle +}
+
|
110
⟩
|
0
⊕
0
⟩
−
|
110
⟩
|
1
⊕
0
⟩
+
|
111
⟩
|
0
⊕
1
⟩
−
|
111
⟩
|
1
⊕
1
⟩
)
=
{\displaystyle +|110\rangle |0\oplus 0\rangle -|110\rangle |1\oplus 0\rangle +|111\rangle |0\oplus 1\rangle -|111\rangle |1\oplus 1\rangle )=}
=
1
2
4
(
|
0000
⟩
−
|
0001
⟩
+
|
0011
⟩
−
|
0010
⟩
+
|
0100
⟩
−
|
0101
⟩
+
|
0111
⟩
−
|
0110
⟩
+
{\displaystyle ={\frac {1}{\sqrt {2^{4}}}}(|0000\rangle -|0001\rangle +|0011\rangle -|0010\rangle +|0100\rangle -|0101\rangle +|0111\rangle -|0110\rangle +}
+
|
1000
⟩
−
|
1001
⟩
+
|
1011
⟩
−
|
1010
⟩
+
|
1100
⟩
−
|
1101
⟩
+
|
1111
⟩
−
|
1110
⟩
)
=
{\displaystyle +|1000\rangle -|1001\rangle +|1011\rangle -|1010\rangle +|1100\rangle -|1101\rangle +|1111\rangle -|1110\rangle )=}
=
1
2
4
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
|
0011
⟩
.
{\displaystyle ={\frac {1}{\sqrt {2^{4}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )(|0\rangle -|1\rangle )\to |0011\rangle .}
3 pirmi kubitai ne nuliai (|001>), todėl funkcija
f
7
(
x
)
{\displaystyle f_{7}(x)}
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
x
f
(
x
1
,
x
2
,
x
3
)
=
f
(
x
)
{\displaystyle f(x_{1},x_{2},x_{3})=f(x)}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
f
1
(
x
)
{\displaystyle f_{1}(x)}
f
2
(
x
)
{\displaystyle f_{2}(x)}
f
3
(
x
)
{\displaystyle f_{3}(x)}
f
4
(
x
)
{\displaystyle f_{4}(x)}
f
5
(
x
)
{\displaystyle f_{5}(x)}
f
6
(
x
)
{\displaystyle f_{6}(x)}
f
7
(
x
)
{\displaystyle f_{7}(x)}
f
8
(
x
)
{\displaystyle f_{8}(x)}
f
9
(
x
)
{\displaystyle f_{9}(x)}
f
10
(
x
)
{\displaystyle f_{10}(x)}
f
11
(
x
)
{\displaystyle f_{11}(x)}
f
12
(
x
)
{\displaystyle f_{12}(x)}
f
13
(
x
)
{\displaystyle f_{13}(x)}
f
14
(
x
)
{\displaystyle f_{14}(x)}
f
15
(
x
)
{\displaystyle f_{15}(x)}
f
16
(
x
)
{\displaystyle f_{16}(x)}
0
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
1
1
0
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
0
0
1
0
1
1
0
0
1
1
1
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
1
0
Šioje lenetelėje išvardintos ne visos subalansuotos funkcijos. Pagal dernių formulę subalansuotų funkcijų yra
C
8
4
=
8
⋅
7
⋅
6
⋅
5
4
⋅
3
⋅
2
⋅
1
=
1680
24
=
70.
{\displaystyle C_{8}^{4}={8\cdot 7\cdot 6\cdot 5 \over 4\cdot 3\cdot 2\cdot 1}={1680 \over 24}=70.}
Klasikiniui kompiuteriui funkcija nustatyti yra sunku dėl to, kad reikia sugeneruoti (pavyzdžiui, tikimybiškai metant monetą) labai daug bitų variantų
2
n
2
=
2
n
−
1
,
{\displaystyle {2^{n} \over 2}=2^{n-1},}
pusė variantų sugeneruotų bitų kombinacijų (pavyzdziui: 000, 001, 011, 101) bus funkcijos "0" ir pusė "1". Atrodytų sugeneruoji atsitiktinę seka (001, 100, 101) ir to turėtų vidutiniškai užtenkti nustatyti ar funkcija subalansuota ar konstanta, nes po kelių paleidimų turėtu išryškėti, kad funkcija subalansuota (nes vienodai galimybiu, kad iškris
f
(
x
)
=
0
{\displaystyle f(x)=0}
f
(
x
)
=
1
{\displaystyle f(x)=1}
f
(
x
)
=
1
{\displaystyle f(x)=1}
2
3
=
8
{\displaystyle 2^{3}=8}
C
8
4
{\displaystyle C_{8}^{4}}
visada ta pačia tvarka . Jei bitų yra n, tai bus tokių funkcijų kurias nuosekliai tikrinant reikės
2
n
−
1
+
1
{\displaystyle 2^{n-1}+1}
2
C
2
n
2
n
−
1
2
C
2
n
2
n
−
1
−
(
n
−
1
)
≈
2
n
−
1
{\displaystyle {2^{C_{2^{n}}^{2^{n-1}}} \over 2^{C_{2^{n}}^{2^{n-1}}-(n-1)}}\approx 2^{n-1}}
2
1000
{\displaystyle 2^{1000}}
2
1002
{\displaystyle 2^{1002}}
2
C
2
n
2
n
−
1
{\displaystyle 2^{C_{2^{n}}^{2^{n-1}}}}
C
2
n
2
n
−
1
=
2
n
!
2
n
−
1
!
⋅
(
2
n
−
2
n
−
1
)
!
=
2
n
!
(
2
n
−
1
!
)
2
{\displaystyle C_{2^{n}}^{2^{n-1}}={2^{n}! \over 2^{n-1}!\cdot (2^{n}-2^{n-1})!}={2^{n}! \over (2^{n-1}!)^{2}}}
deriniai , o n bitų/kubitų skaičius (be paskutinio |1>). Manykime, turime n+1 kubitų (įėjimų) būsenoje |0> ir vieną paskutinį kubitą busenoje |1>. Pažymėkime visus kubitus taip:
|
0
⟩
|
0
⟩
|
0
⟩
.
.
.
|
0
⟩
|
1
⟩
=
|
000..01
⟩
{\displaystyle |0\rangle |0\rangle |0\rangle ...|0\rangle |1\rangle =|000..01\rangle }
Praleidžiame visus kubitus per Hadamardo vartus:
1
2
n
+
1
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
⋯
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle {1 \over {\sqrt {2^{n+1}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )\cdots (|0\rangle +|1\rangle )(|0\rangle -|1\rangle )=}
=
1
2
n
+
1
(
|
00...0
⟩
+
|
00...1
⟩
+
⋯
+
|
11...1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle ={1 \over {\sqrt {2^{n+1}}}}(|00...0\rangle +|00...1\rangle +\cdots +|11...1\rangle )(|0\rangle -|1\rangle )=}
=
1
2
n
+
1
(
|
x
1
⟩
+
|
x
2
⟩
+
⋯
+
|
x
n
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
1
2
n
+
1
∑
x
1
2
n
|
x
⟩
(
|
0
⟩
−
|
1
⟩
)
.
{\displaystyle ={1 \over {\sqrt {2^{n+1}}}}(|x_{1}\rangle +|x_{2}\rangle +\cdots +|x_{n}\rangle )(|0\rangle -|1\rangle )={1 \over {\sqrt {2^{n+1}}}}\sum _{x_{1}}^{2^{n}}|x\rangle (|0\rangle -|1\rangle ).}
Toliau praleidžiame per funkciją
|
x
⟩
|
y
⟩
→
|
x
⟩
|
y
⊕
f
(
x
)
⟩
:
{\displaystyle |x\rangle |y\rangle \to |x\rangle |y\oplus f(x)\rangle :}
1
2
n
+
1
∑
x
1
2
n
|
x
⟩
(
|
0
⊕
f
(
x
)
⟩
−
|
1
⊕
f
(
x
)
⟩
)
=
1
2
n
+
1
∑
x
1
2
n
(
−
1
)
f
(
x
)
|
x
⟩
(
|
0
⟩
−
|
1
⟩
)
.
{\displaystyle {1 \over {\sqrt {2^{n+1}}}}\sum _{x_{1}}^{2^{n}}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle )={1 \over {\sqrt {2^{n+1}}}}\sum _{x_{1}}^{2^{n}}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle ).}
Toliau vėl praleidžiame per Hadamardo vartus:
1
2
n
+
1
∑
x
1
,
z
1
2
n
(
−
1
)
f
(
x
)
(
−
1
)
x
⋅
z
|
y
⟩
|
1
⟩
=
1
2
n
+
1
∑
x
1
,
z
1
2
n
(
−
1
)
f
(
x
)
⊕
x
⋅
z
|
y
⟩
(
|
0
⟩
−
|
1
⟩
)
,
{\displaystyle {1 \over {\sqrt {2^{n+1}}}}\sum _{x_{1},z_{1}}^{2^{n}}(-1)^{f(x)}(-1)^{x\cdot z}|y\rangle |1\rangle ={1 \over {\sqrt {2^{n+1}}}}\sum _{x_{1},z_{1}}^{2^{n}}(-1)^{f(x)\oplus x\cdot z}|y\rangle (|0\rangle -|1\rangle ),}
kur
x
⋅
z
=
x
1
z
1
⊕
x
2
z
2
⋯
x
n
z
n
.
{\displaystyle x\cdot z=x_{1}z_{1}\oplus x_{2}z_{2}\cdots x_{n}z_{n}.}
Jei norime išmatuoti tikimybė, kad išmatuosime ant išėjimo
|
00...0
⟩
,
{\displaystyle |00...0\rangle ,}
x
⋅
z
=
x
1
0
⊕
x
2
0
⊕
⋯
⊕
x
n
0
=
0
⊕
0
⊕
⋯
⊕
0
=
0.
{\displaystyle x\cdot z=x_{1}0\oplus x_{2}0\oplus \cdots \oplus x_{n}0=0\oplus 0\oplus \cdots \oplus 0=0.}
Tada būsenos
|
0
⟩
⊗
n
{\displaystyle |0\rangle ^{\otimes n}}
1
2
n
∑
x
1
2
n
(
−
1
)
f
(
x
)
.
{\displaystyle {1 \over 2^{n}}\sum _{x_{1}}^{2^{n}}(-1)^{f(x)}.}
O
|
0
⟩
⊗
n
{\displaystyle |0\rangle ^{\otimes n}}
|
1
2
n
∑
x
1
2
n
(
−
1
)
f
(
x
)
|
2
=
1.
{\displaystyle |{1 \over 2^{n}}\sum _{x_{1}}^{2^{n}}(-1)^{f(x)}|^{2}=1.}
Jei funkcija subalansuota tai sumuojant pusę vienetų ir pusė nulių gaunama tikimybė 0 išmatuoti
|
0
⟩
⊗
n
{\displaystyle |0\rangle ^{\otimes n}}
|
1
2
n
∑
x
1
2
n
(
−
1
)
f
(
x
)
|
2
=
0.
{\displaystyle |{1 \over 2^{n}}\sum _{x_{1}}^{2^{n}}(-1)^{f(x)}|^{2}=0.}
Apskaičiuokime pagal šią formulę, kai
n
=
1.
{\displaystyle n=1.}
|
01
⟩
→
1
2
1
+
1
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
1
2
1
+
1
∑
x
1
2
1
|
x
⟩
(
|
0
⟩
−
|
1
⟩
)
→
1
2
1
+
1
∑
x
1
2
1
|
x
⟩
(
|
f
(
x
)
⟩
−
|
1
⊕
f
(
x
)
⟩
)
=
{\displaystyle |01\rangle \to {1 \over {\sqrt {2^{1+1}}}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )={1 \over {\sqrt {2^{1+1}}}}\sum _{x_{1}}^{2^{1}}|x\rangle (|0\rangle -|1\rangle )\to {1 \over {\sqrt {2^{1+1}}}}\sum _{x_{1}}^{2^{1}}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )=}
=
1
2
1
+
1
∑
x
1
2
1
(
−
1
)
f
(
x
)
|
x
⟩
(
|
0
⟩
−
|
1
⟩
)
=
1
2
1
+
1
[
(
−
1
)
f
(
0
)
|
0
⟩
(
|
0
⟩
−
|
1
⟩
)
+
(
−
1
)
f
(
1
)
|
1
⟩
(
|
0
⟩
−
|
1
⟩
)
]
=
{\displaystyle ={1 \over {\sqrt {2^{1+1}}}}\sum _{x_{1}}^{2^{1}}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )={1 \over {\sqrt {2^{1+1}}}}[(-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle )]=}
=
1
2
1
+
1
(
(
−
1
)
f
(
0
)
|
0
⟩
+
(
−
1
)
f
(
1
)
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
1
2
2
∑
x
1
,
z
1
2
1
(
−
1
)
f
(
x
)
(
−
1
)
x
⋅
z
|
z
⟩
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle ={1 \over {\sqrt {2^{1+1}}}}((-1)^{f(0)}|0\rangle +(-1)^{f(1)}|1\rangle )(|0\rangle -|1\rangle )\to {1 \over {\sqrt {2^{2}}}}\sum _{x_{1},z_{1}}^{2^{1}}(-1)^{f(x)}(-1)^{x\cdot z}|z\rangle (|0\rangle -|1\rangle )=}
=
1
2
1
+
1
(
(
−
1
)
f
(
0
)
(
|
0
⟩
+
|
1
⟩
)
+
(
−
1
)
f
(
1
)
(
|
0
⟩
−
|
1
⟩
)
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle ={1 \over {\sqrt {2^{1+1}}}}((-1)^{f(0)}(|0\rangle +|1\rangle )+(-1)^{f(1)}(|0\rangle -|1\rangle ))(|0\rangle -|1\rangle )=}
=
1
2
1
+
1
(
(
(
−
1
)
f
(
0
)
+
(
−
1
)
f
(
1
)
)
|
0
⟩
+
(
(
−
1
)
f
(
0
)
−
(
−
1
)
f
(
1
)
)
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
,
{\displaystyle ={1 \over {\sqrt {2^{1+1}}}}(((-1)^{f(0)}+(-1)^{f(1)})|0\rangle +((-1)^{f(0)}-(-1)^{f(1)})|1\rangle )(|0\rangle -|1\rangle ),}
jei tai konstanta, tai tikimybė išmatuoti, kad |z>=|0>,
x
⋅
z
=
x
1
z
1
=
x
1
0
=
0
{\displaystyle x\cdot z=x_{1}z_{1}=x_{1}0=0}
|
1
2
2
∑
x
1
2
1
(
−
1
)
f
(
x
)
|
2
=
|
1
2
(
(
−
1
)
f
(
0
)
+
(
−
1
)
f
(
1
)
)
|
2
=
|
1
2
(
1
+
1
)
|
2
=
1.
{\displaystyle |{1 \over {\sqrt {2^{2}}}}\sum _{x_{1}}^{2^{1}}(-1)^{f(x)}|^{2}=|{1 \over 2}((-1)^{f(0)}+(-1)^{f(1)})|^{2}=|{1 \over 2}(1+1)|^{2}=1.}
Apskaičiuosime, kai
n
=
2
:
{\displaystyle n=2:}
|
001
⟩
→
1
2
2
+
1
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle |001\rangle \to {1 \over {\sqrt {2^{2+1}}}}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )=}
=
1
2
3
∑
x
1
2
2
|
x
⟩
(
|
0
⟩
−
|
1
⟩
)
→
1
2
3
∑
x
1
4
|
x
⟩
(
|
f
(
x
)
⟩
−
|
1
⊕
f
(
x
)
⟩
)
=
1
2
3
∑
x
1
4
(
−
1
)
f
(
x
)
|
x
⟩
(
|
0
⟩
−
|
1
⟩
)
=
{\displaystyle ={1 \over {\sqrt {2^{3}}}}\sum _{x_{1}}^{2^{2}}|x\rangle (|0\rangle -|1\rangle )\to {1 \over {\sqrt {2^{3}}}}\sum _{x_{1}}^{4}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )={1 \over {\sqrt {2^{3}}}}\sum _{x_{1}}^{4}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )=}
=
1
2
3
(
(
−
1
)
f
(
00
)
|
00
⟩
+
(
−
1
)
f
(
01
)
|
01
⟩
+
(
−
1
)
f
(
10
)
|
10
⟩
+
(
−
1
)
f
(
11
)
|
11
⟩
)
(
|
0
⟩
−
|
1
⟩
)
→
{\displaystyle ={1 \over {\sqrt {2^{3}}}}((-1)^{f(00)}|00\rangle +(-1)^{f(01)}|01\rangle +(-1)^{f(10)}|10\rangle +(-1)^{f(11)}|11\rangle )(|0\rangle -|1\rangle )\to }
→
1
2
3
(
(
−
1
)
f
(
00
)
1
2
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
+
(
−
1
)
f
(
01
)
1
2
(
|
0
⟩
+
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
+
{\displaystyle \to {1 \over {\sqrt {2^{3}}}}((-1)^{f(00)}{1 \over 2}(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )+(-1)^{f(01)}{1 \over 2}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle )+}
+
(
−
1
)
f
(
10
)
1
2
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
+
|
1
⟩
)
+
(
−
1
)
f
(
11
)
1
2
(
|
0
⟩
−
|
1
⟩
)
(
|
0
⟩
−
|
1
⟩
)
)
(
1
2
(
|
0
⟩
+
|
1
⟩
)
−
1
2
(
|
0
⟩
−
|
1
⟩
)
)
=
{\displaystyle +(-1)^{f(10)}{1 \over 2}(|0\rangle -|1\rangle )(|0\rangle +|1\rangle )+(-1)^{f(11)}{1 \over 2}(|0\rangle -|1\rangle )(|0\rangle -|1\rangle ))({1 \over {\sqrt {2}}}(|0\rangle +|1\rangle )-{1 \over {\sqrt {2}}}(|0\rangle -|1\rangle ))=}
=
1
2
3
(
(
−
1
)
f
(
00
)
1
2
(
|
00
⟩
+
|
01
⟩
+
|
01
⟩
+
|
11
⟩
)
+
(
−
1
)
f
(
01
)
1
2
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
+
{\displaystyle ={1 \over {\sqrt {2^{3}}}}((-1)^{f(00)}{1 \over 2}(|00\rangle +|01\rangle +|01\rangle +|11\rangle )+(-1)^{f(01)}{1 \over 2}(|00\rangle -|01\rangle +|10\rangle -|11\rangle )+}
+
(
−
1
)
f
(
10
)
1
2
(
|
00
⟩
+
|
01
⟩
−
|
10
⟩
−
|
11
⟩
)
+
(
−
1
)
f
(
11
)
1
2
(
|
00
⟩
−
|
01
⟩
−
|
10
⟩
+
|
11
⟩
)
)
1
2
(
|
0
⟩
+
|
1
⟩
−
(
|
0
⟩
−
|
1
⟩
)
)
=
{\displaystyle +(-1)^{f(10)}{1 \over 2}(|00\rangle +|01\rangle -|10\rangle -|11\rangle )+(-1)^{f(11)}{1 \over 2}(|00\rangle -|01\rangle -|10\rangle +|11\rangle )){1 \over {\sqrt {2}}}(|0\rangle +|1\rangle -(|0\rangle -|1\rangle ))=}
=
1
2
2
3
⋅
2
(
(
−
1
)
f
(
00
)
(
|
00
⟩
+
|
01
⟩
+
|
01
⟩
+
|
11
⟩
)
+
(
−
1
)
f
(
01
)
(
|
00
⟩
−
|
01
⟩
+
|
10
⟩
−
|
11
⟩
)
+
{\displaystyle ={1 \over 2{\sqrt {2^{3}}}\cdot {\sqrt {2}}}((-1)^{f(00)}(|00\rangle +|01\rangle +|01\rangle +|11\rangle )+(-1)^{f(01)}(|00\rangle -|01\rangle +|10\rangle -|11\rangle )+}
+
(
−
1
)
f
(
10
)
(
|
00
⟩
+
|
01
⟩
−
|
10
⟩
−
|
11
⟩
)
+
(
−
1
)
f
(
11
)
(
|
00
⟩
−
|
01
⟩
−
|
10
⟩
+
|
11
⟩
)
)
(
|
0
⟩
+
|
1
⟩
−
|
0
⟩
+
|
1
⟩
)
)
=
{\displaystyle +(-1)^{f(10)}(|00\rangle +|01\rangle -|10\rangle -|11\rangle )+(-1)^{f(11)}(|00\rangle -|01\rangle -|10\rangle +|11\rangle ))(|0\rangle +|1\rangle -|0\rangle +|1\rangle ))=}
=
1
2
2
4
(
(
(
−
1
)
f
(
00
)
+
(
−
1
)
f
(
01
)
+
(
−
1
)
f
(
10
)
+
(
−
1
)
f
(
11
)
)
|
00
⟩
+
{\displaystyle ={1 \over 2{\sqrt {2^{4}}}}(((-1)^{f(00)}+(-1)^{f(01)}+(-1)^{f(10)}+(-1)^{f(11)})|00\rangle +}
+
(
(
−
1
)
f
(
00
)
−
(
−
1
)
f
(
01
)
+
(
−
1
)
f
(
10
)
−
(
−
1
)
f
(
11
)
)
|
01
⟩
+
{\displaystyle +((-1)^{f(00)}-(-1)^{f(01)}+(-1)^{f(10)}-(-1)^{f(11)})|01\rangle +}
+
(
(
−
1
)
f
(
00
)
+
(
−
1
)
f
(
01
)
−
(
−
1
)
f
(
10
)
−
(
−
1
)
f
(
11
)
)
|
10
⟩
+
{\displaystyle +((-1)^{f(00)}+(-1)^{f(01)}-(-1)^{f(10)}-(-1)^{f(11)})|10\rangle +}
+
(
(
−
1
)
f
(
00
)
−
(
−
1
)
f
(
01
)
−
(
−
1
)
f
(
10
)
+
(
−
1
)
f
(
11
)
)
|
11
⟩
)
2
|
1
⟩
=
{\displaystyle +((-1)^{f(00)}-(-1)^{f(01)}-(-1)^{f(10)}+(-1)^{f(11)})|11\rangle )2|1\rangle =}
=
1
4
(
(
(
−
1
)
f
(
00
)
+
(
−
1
)
f
(
01
)
+
(
−
1
)
f
(
10
)
+
(
−
1
)
f
(
11
)
)
|
00
⟩
+
{\displaystyle ={1 \over 4}(((-1)^{f(00)}+(-1)^{f(01)}+(-1)^{f(10)}+(-1)^{f(11)})|00\rangle +}
+
(
(
−
1
)
f
(
00
)
−
(
−
1
)
f
(
01
)
+
(
−
1
)
f
(
10
)
−
(
−
1
)
f
(
11
)
)
|
01
⟩
+
{\displaystyle +((-1)^{f(00)}-(-1)^{f(01)}+(-1)^{f(10)}-(-1)^{f(11)})|01\rangle +}
+
(
(
−
1
)
f
(
00
)
+
(
−
1
)
f
(
01
)
−
(
−
1
)
f
(
10
)
−
(
−
1
)
f
(
11
)
)
|
10
⟩
+
{\displaystyle +((-1)^{f(00)}+(-1)^{f(01)}-(-1)^{f(10)}-(-1)^{f(11)})|10\rangle +}
+
(
(
−
1
)
f
(
00
)
−
(
−
1
)
f
(
01
)
−
(
−
1
)
f
(
10
)
+
(
−
1
)
f
(
11
)
)
|
11
⟩
)
|
1
⟩
.
{\displaystyle +((-1)^{f(00)}-(-1)^{f(01)}-(-1)^{f(10)}+(-1)^{f(11)})|11\rangle )|1\rangle .}
Jei
f
(
00
)
=
f
(
01
)
=
f
(
10
)
=
f
(
10
)
=
0
,
{\displaystyle f(00)=f(01)=f(10)=f(10)=0,}
f
(
00
)
=
f
(
01
)
=
f
(
10
)
=
f
(
10
)
=
1
,
{\displaystyle f(00)=f(01)=f(10)=f(10)=1,}
f
(
x
)
=
0
{\displaystyle f(x)=0}
D. Doičo pamoka apie Doičo algoritmą (video)
![{\displaystyle ={1 \over {\sqrt {2^{1+1}}}}\sum _{x_{1}}^{2^{1}}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )={1 \over {\sqrt {2^{1+1}}}}[(-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle )]=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/404b3a6da915104259c92db9db246707e6e8c50c)
