Doičo-Džozo algoritmas

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$ bandymų blogiausiu atveju (geriausiu atveju – tik dviejų bandymų, jei pasitaikė subalansuota funkcija), o kvantiniui kompiuteriui tik 1 bandymo, kur n kubitų skaičius (be paskutinio kubito |1>). Pavyzdžiui, jei $n=1$ (kubitas kuris yra busenoje |0>), tai klasikiniui kompiuteriui reikia $k=2^{1-1}+1=2$ bandymu, o kvantiniui kompiuteriui reikia $n=1$ vieno bandymo. Jei $n=2$ tai klasikiniui kompiuteriui reikia k ≤ $2^{2-1}+1=3$ bandymų, o kvantiniui tik 1 bandymo. Jei $n=3$ , tai klasikiniui kompiuteriui reikia k ≤ $2^{3-1}+1=5$ bandymų. Jei $n=4$ , tai klasikiniui kompiuteriui reikia k ≤ $2^{4-1}+1=9$ bandymų. Jei $n=5$ , tai klasikiniui kompiuteriui reikia k ≤ $2^{5-1}+1=17$ bandymų, kvanitniui kompiuteriui tik 1 bandymo.

Su tikimybiniu kompiuteriu galima nustatyti suklydymo tikimybę $\epsilon\le({1\over 2})^{k-1}$ po k bandymų, kur $k\le 2^{n-1}+1.$ Tikimybiniam kompiuteriu reikia $k=\log_2{1\over\epsilon}+1$ bandymų (priklausomai kokio tikslumo $\epsilon$ reikia), o kvantiniui kompiuteriui tik 1 bandymo. Pavyzdžiui, po 100 bandymų neteisingo atsakymo tikimybė yra $\epsilon\le 2^{-100}\approx 10^{-30}.$ Tikimybė klaidingo atsakymo tokia maža, kad ir skaičiuojant milijardus metų klaidingas atsakymas nebus apskaičiuotas. Todėl praktišku požiuriu kvantinis kompiuteris Doičo-Jozso problemą nesprendžia greičiau (nei tikimybinis kompiuteris). Kad padaryti daugiau nei 100 užklausimų bitų/kubitų skaičius turi buti $>8$ (nes $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.

Turinys

1 Doičo algoritmas su 2 kubitais
2 Doičo-Džozo algoritmas su 3 kubitais
3 Doičo-Džozo algoritmas su 4 kubitais
4 Bendras Doičo-Džozo algoritmo skaičiavimas
5 Nuorodos

Doičo algoritmas su 2 kubitais[taisyti | redaguoti kodą]

Doičo algoritmas: funkcijos nustatymas: subalansuota ar konstanta.

Praleidus per Hadamardo vartus |0>|1>=|01> gauname

{1\over \sqrt{2}}(|0\rang+|1\rang){1\over\sqrt{2}}(|0\rang-|1\rang)={1\over 2}(|00\rang-|01\rang+|10\rang-|11\rang).

Toliau praleidus pro orakulą šią buseną, gauname

{1\over 2}(|0\rang+|1\rang)(|0\oplus f_{?}(x)\rang-|1\oplus f_{?}(x)\rang)=

={1\over 2}(|0\rang|0\oplus f_{?}(0)\rang-|0\rang|1\oplus f_{?}(0)\rang+|1\rang|0\oplus f_{?}(1)\rang-|1\rang|1\oplus f_{?}(1)\rang).

Pavyzdžiui, apskaičiuosime $f_2(x)$ :

{1\over 2}(|0\rang|0\oplus f_{2}(0)\rang-|0\rang|1\oplus f_{2}(0)\rang+|1\rang|0\oplus f_{2}(1)\rang-|1\rang|1\oplus f_{2}(1)\rang)=

={1\over 2}(|0\rang|0\oplus 1\rang-|0\rang|1\oplus 1\rang+|1\rang|0\oplus 1\rang-|1\rang|1\oplus 1\rang)=

={1\over 2}(|0\rang|1\rang-|0\rang|0\rang+|1\rang| 1\rang-|1\rang|0\rang)=-{1\over 2}(|0\rang+|1\rang)(|0\rang-|1\rang).

Toliau praleidžiame pro Hadamardo vartus šią būseną:

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>))=

=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>)=

=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)

:

$|0\rang|1\rang\to{1\over \sqrt{2}}(|0\rang+|1\rang){1\over\sqrt{2}}(|0\rang-|1\rang)={1\over 2}(|00\rang-|01\rang+|10\rang-|11\rang)\to$ $\to{1\over 2}(|0\rang|0\oplus f_{3}(0)\rang-|0\rang|1\oplus f_{3}(0)\rang+|1\rang|0\oplus f_{3}(1)\rang-|1\rang|1\oplus f_{3}(1)\rang)=$ $={1\over 2}(|0\rang|0\oplus 0\rang-|0\rang|1\oplus 0\rang+|1\rang|0\oplus 1\rang-|1\rang|1\oplus 1\rang)=$ $={1\over 2}(|0\rang|0\rang-|0\rang|1\rang+|1\rang| 1\rang-|1\rang|0\rang)={1\over 2}(|0\rang-|1\rang)(|0\rang-|1\rang)\to |1\rang|1\rang.$

Pirmas kubitas |1>, taigi funkcija subalansuota.

Apskaičiuosime

f_4(x)

:

$|0\rang|1\rang\to{1\over \sqrt{2}}(|0\rang+|1\rang){1\over\sqrt{2}}(|0\rang-|1\rang)={1\over 2}(|00\rang-|01\rang+|10\rang-|11\rang)\to$ $\to{1\over 2}(|0\rang|0\oplus f_{4}(0)\rang-|0\rang|1\oplus f_{4}(0)\rang+|1\rang|0\oplus f_{4}(1)\rang-|1\rang|1\oplus f_{4}(1)\rang)=$ $={1\over 2}(|0\rang|0\oplus 1\rang-|0\rang|1\oplus 1\rang+|1\rang|0\oplus 0\rang-|1\rang|1\oplus 0\rang)=$ $={1\over 2}(|01\rang-|00\rang+|10\rang-|11\rang)=-{1\over 2}(|0\rang-|1\rang)(|0\rang-|1\rang)\to -|1\rang{1\over \sqrt{2}}(|0\rang-|1\rang)=-|11\rang\to|11\rang.$

Pirmas kubitas |1>, taigi funkcija subalansuota.

Funkcijos nustatymas klasikiniu algoritmu.

Funkcijos nustatymas su klasikiniais loginiais elementais.

Apskaičiuosime

f_1(x)

:

$|0\rang|1\rang\to{1\over \sqrt{2}}(|0\rang+|1\rang){1\over\sqrt{2}}(|0\rang-|1\rang)={1\over 2}(|00\rang-|01\rang+|10\rang-|11\rang)\to$ $\to{1\over 2}(|0\rang|0\oplus f_{1}(0)\rang-|0\rang|1\oplus f_{1}(0)\rang+|1\rang|0\oplus f_{1}(1)\rang-|1\rang|1\oplus f_{1}(1)\rang)=$ $={1\over 2}(|0\rang|0\oplus 0\rang-|0\rang|1\oplus 0\rang+|1\rang|0\oplus 0\rang-|1\rang|1\oplus 0\rang)=$ $={1\over 2}(|00\rang-|01\rang+|10\rang-|11\rang)={1\over 2}(|0\rang+|1\rang)(|0\rang-|1\rang)\to|01\rang.$

Pirmas kubitas |0>, taigi funkcija konstanta.

$f_1(x)$ $f_2(x)$ $f_3(x)$ $f_4(x)$

$x=0$ 0 1 0 1

$x=1$ 0 1 1 0

Klasikiniu atveju neįmanoma nustatyti, ar funkcija konstanta ( $f_1(x)$ ir $f_2(x)$ ) ar subalansuota ( $f_3(x)$ ir $f_4(x)$ ), algoritmą reikia paleisti du kartus (pavyzdžiui, iš pradžių idėjus 00, o paskui 10), kvantiniu atveju užtenka vieno paleidimo išmatavus pirmą (viršutinį) kubitą. Jeigu pirmas kubitas yra ant išėjimo |0>, reiškia funkcija yra konstanta ( $f_1(x)$ arba $f_2(x)$ ) ir jeigu pirmas kubitas išmatuotas yra |1>, tai funkcija yra subalansuota ( $f_3(x)$ arba $f_4(x)$ ). Tiek klasikinio tiek kvantinio algoritmo principas veikimo yra toks. Yra jau sukurtas klasikinis ar tai kvantinis kompiuteris ir jis sukurtas taip, kad veiktų su vieną iš keturių funkcijų ( $f_1(x)$ , $f_2(x)$ , $f_3(x)$ , $f_4(x)$ ). Jis jau taip sukonstruotas, kad jame jau idėtas tam tikras veikimas, bet mes nežinome koks. Paleidus kvantinį kompiuteri (Doičo algoritmą) iš vieno paleidimo išaiškeja, kaip jis viduje padarytas ir kuri funkcija „įdėta“ (subalansuota ar konstanta). Klasikiniu kompiuteriu reikia paleisti tam tikru budu du kartus algoritmą su skirtingom kažkurio vieno kubito vertėm (0 arba 1), kad nustatyti pagal kokią funkciją sukurtas orakulas (juodoji dežė) – pats kompiuteris.

Kita vertus, klasikinis algoritmas po dviejų paleidimų nustato ne tik funkcijos rušį (subalansuota ar konstanta), bet ir pačią funciją (pvz., $f_3(x)$ ). Pavyzdžiui, įleidome į klasikinį orakulą 00 ir gavome 00, reiškia funkcija yra $f_1(x)$ arba $f_3(x)$ , tada antrą kartą įdėjome 10 ir gavome 11, vadinasi funkcija yra $f_3(x)$ .

in 00

out 00 01 10 11

rezultatas $f_1(x)$ arba $f_3(x)$ $f_2(x)$ arba $f_4(x)$ pirmas bitas negali pasikeisti pirmas bitas negali pasikeisti

in 01

out 00 01 10 11

resultatas $f_2(x)$ arba $f_4(x)$ $f_1(x)$ arba $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)$ arba $f_4(x)$ $f_2(x)$ arba $f_3(x)$

in 11

out 00 01 10 11

resultatas pirmas bitas negali pasikeisti pirmas bitas negali pasikeisti $f_2(x)$ arba $f_3(x)$ $f_1(x)$ arba $f_4(x)$

0\oplus 0=0,

0\oplus 1=1,

1 \oplus 0=1,

1 \oplus 1=0.

Doičo-Džozo algoritmas su 3 kubitais[taisyti | redaguoti kodą]

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)$ subalansuota ar konstanta.

Dabar visus 3 kubitus $|0>|0>|1>=|001>$ praleisime pro Hadamardo vartus: $\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\rang+|10\rang-|11\rang)=$ $= \frac{1}{\sqrt{2^3}}(|000\rang-|001\rang+|010\rang-|011\rang +|100\rangle-|101\rangle+|110\rangle-|111\rangle).$ Dabar pažymėkime, kad pirmas kubitas yra $x_1$ , antras kubitas yra $x_2$ , o trečias kubitas yra $y$ . Dabar praleisime visus tris kubitus pro Controlled-U vartus $|x_1\rang |x_2\rang| y\rang\to|x_1\rang |x_2\rang| y\oplus f(x_1,x_2)\rang:$ $\frac{1}{\sqrt{2^3}}(|00\rang|0\oplus f(x_1, x_2)\rang-|00\rang|1\oplus f(x_1, x_2)\rang+|01\rang|0\oplus f(x_1, x_2)\rang-|01\rang|1\oplus f(x_1, x_2)\rang +$ $+|10\rang|0\oplus f(x_1, x_2)\rangle-|10\rang|1\oplus f(x_1, x_2)\rangle+|11\rang|0\oplus f(x_1, x_2)\rangle-|11\rang|1\oplus f(x_1, x_2)\rangle).$

Apskaičiuosime

f_2(x_1,x_2)=f_2(x)=1

:

$|001\rang\to\frac{1}{\sqrt{2^3}}(|0\rangle + |1\rangle)(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)=$ $=\frac{1}{\sqrt{2^3}}(|000\rang-|001\rang+|010\rang-|011\rang +|100\rang-|101\rang+|110\rang-|111\rang)\to$ $\to \frac{1}{\sqrt{2^3}}(|00\rang|0\oplus f_2(x)\rang-|00\rang|1\oplus f_2(x)\rang+|01\rang|0\oplus f_2(x)\rang-|01\rang|1\oplus f_2(x)\rang +$ $+|10\rang|0\oplus f_2(x)\rang-|10\rang|1\oplus f_2(x)\rang+|11\rang|0\oplus f_2(x)\rang-|11\rang|1\oplus f_2(x)\rang)=$ $=\frac{1}{\sqrt{2^3}}(|00\rang|0\oplus 1\rang-|00\rang|1\oplus 1\rang+|01\rang|0\oplus 1\rang-|01\rang|1\oplus 1\rang +$ $+|10\rang|0\oplus 1\rang-|10\rang|1\oplus 1\rang+|11\rang|0\oplus 1\rang-|11\rang|1\oplus 1\rang)=$ $=\frac{1}{\sqrt{2^3}}(|001\rang-|000\rang+|011\rang-|010\rang +|101\rang-|100\rang+|111\rang-|110\rang)=$ $=-\frac{1}{\sqrt{2^3}}(|0\rangle + |1\rangle)(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)\to -|001\rang\to|001\rang.$

Abu pirmi kubitai |00>, todel funkcija $f_2(x_1,x_2)$ yra konstanta.

Apskaičiuosime

f_3(x_1,x_2)=f_3(x)

:

$|001\rang\to\frac{1}{\sqrt{2^3}}(|0\rangle + |1\rangle)(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)=$ $=\frac{1}{\sqrt{2^3}}(|000\rang-|001\rang+|010\rang-|011\rang +|100\rang-|101\rang+|110\rang-|111\rang)\to$ $\to \frac{1}{\sqrt{2^3}}(|00\rang|0\oplus f_3(x)\rang-|00\rang|1\oplus f_3(x)\rang+|01\rang|0\oplus f_3(x)\rang-|01\rang|1\oplus f_3(x)\rang +$ $+|10\rang|0\oplus f_3(x)\rang-|10\rang|1\oplus f_3(x)\rang+|11\rang|0\oplus f_3(x)\rang-|11\rang|1\oplus f_3(x)\rang)=$ $=\frac{1}{\sqrt{2^3}}(|00\rang|0\oplus 0\rang-|00\rang|1\oplus 0\rang+|01\rang|0\oplus 0\rang-|01\rang|1\oplus 0\rang +$ $+|10\rang|0\oplus 1\rang-|10\rang|1\oplus 1\rang+|11\rang|0\oplus 1\rang-|11\rang|1\oplus 1\rang)=$ $=\frac{1}{\sqrt{2^3}}(|000\rang-|001\rang+|010\rang-|011\rang +|101\rang-|100\rang+|111\rang-|110\rang)=$ $=\frac{1}{\sqrt{2^3}}(|0\rangle - |1\rangle)(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)\to |101\rang.$

Funkcija $f_3(x)$ yra subalansuota, nes abu pirmi kubitai |10> nėra nuliai (funkcija yra konstanta tik tuo atveju kai du pirmi kubitai ant išėjimo yra nuliai).

Apskaičiuosime

f_5(x_1,x_2)=f_5(x)

:

$|001\rang\to\frac{1}{\sqrt{2^3}}(|0\rangle + |1\rangle)(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)=$ $=\frac{1}{\sqrt{2^3}}(|000\rang-|001\rang+|010\rang-|011\rang +|100\rang-|101\rang+|110\rang-|111\rang)\to$ $\to \frac{1}{\sqrt{2^3}}(|00\rang|0\oplus f_5(x)\rang-|00\rang|1\oplus f_5(x)\rang+|01\rang|0\oplus f_5(x)\rang-|01\rang|1\oplus f_5(x)\rang +$ $+|10\rang|0\oplus f_5(x)\rang-|10\rang|1\oplus f_5(x)\rang+|11\rang|0\oplus f_5(x)\rang-|11\rang|1\oplus f_5(x)\rang)=$ $=\frac{1}{\sqrt{2^3}}(|00\rang|0\oplus 0\rang-|00\rang|1\oplus 0\rang+|01\rang|0\oplus 1\rang-|01\rang|1\oplus 1\rang +$ $+|10\rang|0\oplus 0\rang-|10\rang|1\oplus 0\rang+|11\rang|0\oplus 1\rang-|11\rang|1\oplus 1\rang)=$ $=\frac{1}{\sqrt{2^3}}(|000\rang-|001\rang+|011\rang-|010\rang +|100\rang-|101\rang+|111\rang-|110\rang)=$ $=\frac{1}{\sqrt{2^3}}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)(|0\rangle - |1\rangle)\to |011\rang.$

Pirmi du kubitai yra išmatuoti |01>, todėl funkcija $f_5(x)$ yra subalansuota.

Apskaičiuosime

f_8(x_1,x_2)=f_8(x)

:

$|001\rang\to\frac{1}{\sqrt{2^3}}(|0\rangle + |1\rangle)(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)=$ $=\frac{1}{\sqrt{2^3}}(|000\rang-|001\rang+|010\rang-|011\rang +|100\rang-|101\rang+|110\rang-|111\rang)\to$ $\to \frac{1}{\sqrt{2^3}}(|00\rang|0\oplus f_8(x)\rang-|00\rang|1\oplus f_8(x)\rang+|01\rang|0\oplus f_8(x)\rang-|01\rang|1\oplus f_8(x)\rang +$ $+|10\rang|0\oplus f_8(x)\rang-|10\rang|1\oplus f_8(x)\rang+|11\rang|0\oplus f_8(x)\rang-|11\rang|1\oplus f_8(x)\rang)=$ $=\frac{1}{\sqrt{2^3}}(|00\rang|0\oplus 1\rang-|00\rang|1\oplus 1\rang+|01\rang|0\oplus 0\rang-|01\rang|1\oplus 0\rang +$ $+|10\rang|0\oplus 0\rang-|10\rang|1\oplus 0\rang+|11\rang|0\oplus 1\rang-|11\rang|1\oplus 1\rang)=$ $=\frac{1}{\sqrt{2^3}}(|001\rang-|000\rang+|010\rang-|011\rang +|100\rang-|101\rang+|111\rang-|110\rang)=$ $=-\frac{1}{\sqrt{2^3}}(|0\rangle - |1\rangle)(|0\rangle - |1\rangle)(|0\rangle - |1\rangle)\to -|111\rang\to |111\rang.$

Funkcija $f_8(x)$ subalansuota, nes primi du kubitai vienetai.

Funkcijos klasikinio kompiuterio, kad viską paversti kvantiniu iš priekio ir iš galo reikia pridėti Hadamardo vartus.

Funkcijos $f_1(x)$ ir $f_2(x)$ yra konstantos, o visos kitos funkcijos $f_3(x)$ , $f_4(x)$ , $f_5(x)$ , $f_6(x)$ , $f_7(x)$ , $f_{8}(x)$ yra subalansuotos.

x $f(x_1,x_2)=f(x)$

$x_1$ $x_2$ $f_1(x)$ $f_2(x)$ $f_3(x)$ $f_4(x)$ $f_5(x)$ $f_6(x)$ $f_7(x)$ $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

Suvedame visus įmanomus išėjimus, funkcijos patikrinimui, kai įėjimas |001>:

f_1(x)

---> |001>;

f_2(x)

---> -|001>;

f_3(x)

---> |101>;

f_4(x)

---> -|101>;

f_5(x)

---> |011>;

f_6(x)

---> -|011>;

f_7(x)

---> |111>;

f_8(x)

---> -|111>.

Doičo-Džozo algoritmas su 4 kubitais[taisyti | redaguoti kodą]

Tarkime, turime tokį įėjimą: |0>|0>|0>|1>=|0001>. Praleileidžiame visus kubitus pro Hadamardo vartus: $\frac{1}{\sqrt{2^4}}(|0\rang + |1\rang)(|0\rang + |1\rang)(|0\rang + |1\rang)(|0\rangle - |1\rangle)=\frac{1}{\sqrt{2^4}}(|0\rang + |1\rang)(|0\rangle + |1\rangle)(|00\rangle-|01\rang+|10\rang-|11\rang)=$ $= \frac{1}{\sqrt{2^4}}(|0\rang + |1\rang)(|000\rang-|001\rang+|010\rang-|011\rang +|100\rangle-|101\rangle+|110\rangle-|111\rangle)=$ $= \frac{1}{\sqrt{2^4}}(|0000\rang-|0001\rang+|0010\rang-|0011\rang +|0100\rang-|0101\rangle+|0110\rang-|0111\rang+$ $+ |1000\rang-|1001\rang+|1010\rang-|1011\rang +|1100\rang-|1101\rang+|1110\rang-|1111\rang).$

Toliau praleidžiame per funkciją

|x_1\rang|x_2\rang|x_3\rang|y\rang\to|x_1\rang|x_2\rang|x_3\rang|y\oplus f(x)\rang

(

f(x)=f(x_1,x_2,x_3)

):

$\frac{1}{\sqrt{2^4}}(|000\rang|0\oplus f(x)\rang-|000\rang|1\oplus f(x)\rang+|001\rang|0\oplus f(x)\rang-|001\rang|1\oplus f(x)\rang +$ $+|010\rang|0\oplus f(x)\rang-|010\rang|1\oplus f(x)\rangle+|011\rang|0\oplus f(x)\rang-|011\rang|1\oplus f(x)\rang+$ $+ |100\rang|0\oplus f(x)\rang-|100\rang|1\oplus f(x)\rang+|101\rang|0\oplus f(x)\rang-|101\rang|1\oplus f(x)\rang +$ $+|110\rang|0\oplus f(x)\rang-|110\rang|1\oplus f(x)\rang+|111\rang|0\oplus f(x)\rang-|111\rang|1\oplus f(x)\rang).$

Apskaičiuosime, pavyzdžiui,

f_7(x)=f_7(x_1,x_2,x_3)

:

$|0001\rang\to\frac{1}{\sqrt{2^4}}(|0\rang + |1\rang)(|0\rang + |1\rang)(|0\rang + |1\rang)(|0\rangle - |1\rangle)=$ $=\frac{1}{\sqrt{2^4}}(|0000\rang-|0001\rang+|0010\rang-|0011\rang +|0100\rang-|0101\rangle+|0110\rang-|0111\rang+$ $+ |1000\rang-|1001\rang+|1010\rang-|1011\rang +|1100\rang-|1101\rang+|1110\rang-|1111\rang)\to$ $\to \frac{1}{\sqrt{2^4}}(|000\rang|0\oplus f_7(x)\rang-|000\rang|1\oplus f_7(x)\rang+|001\rang|0\oplus f_7(x)\rang-|001\rang|1\oplus f_7(x)\rang +$ $+|010\rang|0\oplus f_7(x)\rang-|010\rang|1\oplus f_7(x)\rangle+|011\rang|0\oplus f_7(x)\rang-|011\rang|1\oplus f_7(x)\rang+$ $+ |100\rang|0\oplus f_7(x)\rang-|100\rang|1\oplus f_7(x)\rang+|101\rang|0\oplus f_7(x)\rang-|101\rang|1\oplus f_7(x)\rang +$ $+|110\rang|0\oplus f_7(x)\rang-|110\rang|1\oplus f_7(x)\rang+|111\rang|0\oplus f_7(x)\rang-|111\rang|1\oplus f_7(x)\rang)=$ $= \frac{1}{\sqrt{2^4}}(|000\rang|0\oplus 0\rang-|000\rang|1\oplus 0\rang+|001\rang|0\oplus 1\rang-|001\rang|1\oplus 1\rang +$ $+|010\rang|0\oplus 0\rang-|010\rang|1\oplus 0\rangle+|011\rang|0\oplus 1\rang-|011\rang|1\oplus 1\rang+$ $+ |100\rang|0\oplus 0\rang-|100\rang|1\oplus 0\rang+|101\rang|0\oplus 1\rang-|101\rang|1\oplus 1\rang +$ $+|110\rang|0\oplus 0\rang-|110\rang|1\oplus 0\rang+|111\rang|0\oplus 1\rang-|111\rang|1\oplus 1\rang)=$ $= \frac{1}{\sqrt{2^4}}(|0000\rang-|0001\rang+|0011\rang-|0010\rang +|0100\rang-|0101\rangle+|0111\rang-|0110\rang+$ $+ |1000\rang-|1001\rang+|1011\rang-|1010\rang +|1100\rang-|1101\rang+|1111\rang-|1110\rang)=$ $=\frac{1}{\sqrt{2^4}}(|0\rang + |1\rang)(|0\rang + |1\rang)(|0\rang - |1\rang)(|0\rangle - |1\rangle)\to|0011\rang.$

3 pirmi kubitai ne nuliai (|001>), todėl funkcija $f_7(x)$ subalansuota.

Konstantos yra tik funkcijos $f_1(x)$ ir $f_2(x)$ , o visos kitos subalansuotos.

x $f(x_1,x_2,x_3)=f(x)$

$x_1$ $x_2$ $x_3$ $f_1(x)$ $f_2(x)$ $f_3(x)$ $f_4(x)$ $f_5(x)$ $f_6(x)$ $f_7(x)$ $f_8(x)$ $f_9(x)$ $f_{10}(x)$ $f_{11}(x)$ $f_{12}(x)$ $f_{13}(x)$ $f_{14}(x)$ $f_{15}(x)$ $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^{4}_{8} = {8\cdot 7\cdot 6\cdot 5\over 4\cdot 3\cdot 2\cdot 1} = {1680\over 24}=70.$ Bendrai su konstantomis funkcijų yra 72.

Klasikiniui kompiuteriui funkcija nustatyti yra sunku dėl to, kad reikia sugeneruoti (pavyzdžiui, tikimybiškai metant monetą) labai daug bitų variantų

{2^n\over 2}=2^{n-1},

nes 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

ir

f(x)=1

, tačiau tikimybiniu tikrinimu bus beveik neįmanoma patikrinti ar funkcija konstanta, nes vis tiek lieka tikimybė, kad tai gali būti vis ta pati subalansuota funkcija, kurios ta pati reikšmė (pvz.,

f(x)=1

(subalansuotos)), kartojasi ir kad būti 100 % užtikrintam, kad mes vis nepapuolėm ant subalansuotos funkcijos reikšmes, kai ji vis išduoda "1", reikia arba pakartoti begalybę kartų „tikimybinių bitų“ generavimą arba skaičiuoti ne tikimybiškai, o deterministiškai, nuosekliai. Bet skaičiuojant nuosekliai

2^3=8

bitų/kubitų variantai. Tai turės

C_8^4

subalansuotų funkcijų iš kurių bent maža dalis turės 00001111 arba 11110000 ar 00011101 sekas, kurias iš eilės tikrinant prireiks kaip šiuo atvejų 5 ar 4 patikrinimų. Aišku dažniausiai bus funkcijos 001100101, 100010101, kada užtenka 2 ar 3 patikrinimų paleidžiant tam tikras kubitų kombinacijas visada ta pačia tvarka. Jei bitų yra n, tai bus tokių funkcijų kurias nuosekliai tikrinant reikės

2^{n-1}+1

patikrinimų. Aišku tokių (subalansuotų) funkcijų bus vos 1 % ir tokių funkcijų su daugiau ir daugiau kubitų bus vis mažiau eksponentiškai, bet kvantinis kompiuteris vis tiek bus

{2^{C_{2^n}^{2^{n-1}}}\over 2^{C_{2^n}^{2^{n-1}}-(n-1)}}\approx 2^{n-1}

kartų greitesnis, bet abu kompiuteriai užtruks labai daug laiko ir, palyginus, kvantinis kompiuteris užtruks apytiksliai

2^{1000}

laiko, o klasikinis

2^{1002}

laiko. Subalansuotų funkcijų iš viso gali būti

2^{C_{2^n}^{2^{n-1}}}

, o konstantų – tik 2, kur

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}

yra deriniai, o n bitų/kubitų skaičius (be paskutinio |1>).

Bendras Doičo-Džozo algoritmo skaičiavimas[taisyti | redaguoti kodą]

Manykime, turime n+1 kubitų (įėjimų) būsenoje |0> ir vieną paskutinį kubitą busenoje |1>. Pažymėkime visus kubitus taip:

|0 \rang |0 \rang |0 \rang...|0 \rang|1\rang=|000..01 \rang

.

Praleidžiame visus kubitus per Hadamardo vartus:

${1\over \sqrt{2^{n+1}}}(|0\rang+|1\rang)(|0\rang+|1\rang)\cdots(|0\rang+|1\rang)(|0\rang-|1\rang)=$ $={1\over \sqrt{2^{n+1}}}(|00...0\rang+|00...1\rang+\cdots+|11...1\rang)(|0\rang-|1\rang)=$ $={1\over \sqrt{2^{n+1}}}(|x_1\rang+|x_2\rang+\cdots+|x_n\rang)(|0\rang-|1\rang)={1\over \sqrt{2^{n+1}}}\sum_{x_1}^{2^n}|x\rang(|0\rang-|1\rang).$

Toliau praleidžiame per funkciją $|x\rang|y\rang\to|x\rang|y\oplus f(x)\rang:$ ${1\over \sqrt{2^{n+1}}}\sum_{x_1}^{2^n}|x\rang(|0\oplus f(x)\rang-|1\oplus f(x)\rang)={1\over \sqrt{2^{n+1}}}\sum_{x_1}^{2^n}(-1)^{f(x)}|x\rang(|0\rang-|1\rang).$

Toliau vėl praleidžiame per Hadamardo vartus:

{1\over \sqrt{2^{n+1}}}\sum_{x_1,z_1 }^{2^n}(-1)^{f(x)}(-1)^{x\cdot z}|y\rang|1\rang={1\over \sqrt{2^{n+1}}}\sum_{x_1,z_1 }^{2^n}(-1)^{f(x)\oplus x\cdot z}|y\rang(|0\rang-|1\rang),

kur

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\rang,

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\rang^{\otimes n}

amplitudė yra tokia:

{1\over 2^{n}}\sum_{x_1}^{2^n}(-1)^{f(x)}.

O

|0\rang^{\otimes n}

išmatavimo tikimybė:

|{1\over2^{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\rang^{\otimes n}

:

|{1\over 2^{n}}\sum_{x_1}^{2^n}(-1)^{f(x)}|^2=0.

Apskaičiuokime pagal šią formulę, kai

n=1.

$|01\rang\to{1\over \sqrt{2^{1+1}}}(|0\rang+|1\rang)(|0\rang-|1\rang)={1\over \sqrt{2^{1+1}}}\sum_{x_1}^{2^1}|x\rang(|0\rang-|1\rang)\to{1\over \sqrt{2^{1+1}}}\sum_{x_1}^{2^1}|x\rang(|f(x)\rang-|1\oplus f(x)\rang)=$ $={1\over \sqrt{2^{1+1}}}\sum_{x_1}^{2^1}(-1)^{f(x)}|x\rang(|0\rang-|1\rang)={1\over \sqrt{2^{1+1}}}[(-1)^{f(0)}|0\rang(|0\rang-|1\rang)+(-1)^{f(1)}|1\rang(|0\rang-|1\rang)]=$ $={1\over\sqrt{2^{1+1}}}((-1)^{f(0)}|0\rang+(-1)^{f(1)}|1\rang)(|0\rang-|1\rang)\to{1\over \sqrt{2^2}}\sum_{x_1,z_1}^{2^1}(-1)^{f(x)}(-1)^{x\cdot z}|z\rang(|0\rang-|1\rang)=$ $={1\over\sqrt{2^{1+1}}}((-1)^{f(0)}(|0\rang+|1\rang)+(-1)^{f(1)}(|0\rang-|1\rang))(|0\rang-|1\rang)=$ $={1\over\sqrt{2^{1+1}}}(((-1)^{f(0)}+(-1)^{f(1)})|0\rang+((-1)^{f(0)}-(-1)^{f(1)})|1\rang)(|0\rang-|1\rang),$

jei tai konstanta, tai tikimybė išmatuoti, kad |z>=|0>,

x\cdot z=x_1 z_1=x_1 0=0

:

$|{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:

$|001\rang\to{1\over \sqrt{2^{2+1}}}(|0\rang+|1\rang)(|0\rang+|1\rang)(|0\rang-|1\rang)=$ $={1\over \sqrt{2^3}}\sum_{x_1}^{2^2}|x\rang(|0\rang-|1\rang)\to{1\over \sqrt{2^3}}\sum_{x_1}^{4}|x\rang(|f(x)\rang-|1\oplus f(x)\rang)={1\over \sqrt{2^3}}\sum_{x_1}^{4}(-1)^{f(x)}|x\rang(|0\rang-|1\rang)=$ $={1\over \sqrt{2^3}}((-1)^{f(00)}|00\rang+(-1)^{f(01)}|01\rang+(-1)^{f(10)}|10\rang+(-1)^{f(11)}|11\rang)(|0\rang-|1\rang)\to$ $\to {1\over \sqrt{2^3}}((-1)^{f(00)}{1\over 2}(|0\rang+|1\rang)(|0\rang+|1\rang)+(-1)^{f(01)}{1\over 2}(|0\rang+|1\rang)(|0\rang-|1\rang)+$ $+(-1)^{f(10)}{1\over 2}(|0\rang-|1\rang)(|0\rang+|1\rang)+(-1)^{f(11)}{1\over 2}(|0\rang-|1\rang)(|0\rang-|1\rang))({1\over \sqrt{2}}(|0\rang+|1\rang)-{1\over\sqrt{2}}(|0\rang-|1\rang))=$

$= {1\over \sqrt{2^3}}((-1)^{f(00)}{1\over 2}(|00\rang+|01\rang+|01\rang+|11\rang)+(-1)^{f(01)}{1\over 2}(|00\rang-|01\rang+|10\rang-|11\rang)+$ $+(-1)^{f(10)}{1\over 2}(|00\rang+|01\rang-|10\rang-|11\rang)+(-1)^{f(11)}{1\over 2}(|00\rang-|01\rang-|10\rang+|11\rang)){1\over \sqrt{2}}(|0\rang+|1\rang-(|0\rang-|1\rang))=$

$= {1\over 2\sqrt{2^3}\cdot\sqrt{2}}((-1)^{f(00)}(|00\rang+|01\rang+|01\rang+|11\rang)+(-1)^{f(01)}(|00\rang-|01\rang+|10\rang-|11\rang)+$ $+(-1)^{f(10)}(|00\rang+|01\rang-|10\rang-|11\rang)+(-1)^{f(11)}(|00\rang-|01\rang-|10\rang+|11\rang))(|0\rang+|1\rang-|0\rang+|1\rang))=$

$= {1\over 2\sqrt{2^4}}(((-1)^{f(00)}+(-1)^{f(01)}+(-1)^{f(10)}+(-1)^{f(11)})|00\rang+$ $+((-1)^{f(00)}-(-1)^{f(01)}+(-1)^{f(10)}-(-1)^{f(11)})|01\rang+$ $+((-1)^{f(00)}+(-1)^{f(01)}-(-1)^{f(10)}-(-1)^{f(11)})|10\rang+$ $+((-1)^{f(00)}-(-1)^{f(01)}-(-1)^{f(10)}+(-1)^{f(11)})|11\rang)2|1\rang=$

$= {1\over 4}(((-1)^{f(00)}+(-1)^{f(01)}+(-1)^{f(10)}+(-1)^{f(11)})|00\rang+$ $+((-1)^{f(00)}-(-1)^{f(01)}+(-1)^{f(10)}-(-1)^{f(11)})|01\rang+$ $+((-1)^{f(00)}+(-1)^{f(01)}-(-1)^{f(10)}-(-1)^{f(11)})|10\rang+$ $+((-1)^{f(00)}-(-1)^{f(01)}-(-1)^{f(10)}+(-1)^{f(11)})|11\rang)|1\rang.$

Jei

f(00)=f(01)=f(10)=f(10)=0,

tai gausime |001>, o jei

f(00)=f(01)=f(10)=f(10)=1,

tai gausime -|001>. Akivaizdu, kad jeigu 50 %

f(x)=0

ir 50 % f(x)=1, tai jos susiprastins ir būsenos (pirmų dviejų kubitų) |00> niekada negausime (ir funkcija bus subalansuota).

Nuorodos[taisyti | redaguoti kodą]

D. Doičo pamoka apie Doičo algoritmą (video)

http://cam.qubit.org/lectures/artur/Part%202%20Algorithms.pdf Doičo-Jozo algoritmas. PDF.
http://arxiv.org/pdf/quant-ph/0111032 Adiabatinis Doičo algoritmas. PDF.
http://www.cs.umd.edu/class/fall2006/cmsc351/notes/qubits/node1.html
http://www.research.ibm.com/ss_computing/iedm2000fin.ppt
http://arxiv.org/pdf/quant-ph/0611186
http://www.cs.man.ac.uk/~ballhyse/myfiles/MSThesis.pdf
http://beige.ovpit.indiana.edu/M743-talk-2/node13.html
http://arxiv.org/pdf/quant-ph/0410042

Doičo-Džozo algoritmas

Turinys

Doičo algoritmas su 2 kubitais[taisyti | redaguoti kodą]

Doičo-Džozo algoritmas su 3 kubitais[taisyti | redaguoti kodą]

Doičo-Džozo algoritmas su 4 kubitais[taisyti | redaguoti kodą]

Bendras Doičo-Džozo algoritmo skaičiavimas[taisyti | redaguoti kodą]

Nuorodos[taisyti | redaguoti kodą]

Naršymo meniu

Asmeniniai įrankiai

Vardų sritys

Variantai

Žiūrėti

Daugiau

Paieška

Naršymas

Spausdinti/eksportuoti

Įrankiai

Kitomis kalbomis

in	00
out	00	01	10	11
rezultatas	$f_1(x)$ arba $f_3(x)$	$f_2(x)$ arba $f_4(x)$	pirmas bitas negali pasikeisti	pirmas bitas negali pasikeisti

in	01
out	00	01	10	11
resultatas	$f_2(x)$ arba $f_4(x)$	$f_1(x)$ arba $f_3(x)$	pirmas bitas negali pasikeisti	pirmas bitas negali pasikeisti

x		$f(x_1,x_2)=f(x)$
$x_1$	$x_2$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$	$f_5(x)$	$f_6(x)$	$f_7(x)$	$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

x			$f(x_1,x_2,x_3)=f(x)$
$x_1$	$x_2$	$x_3$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$	$f_5(x)$	$f_6(x)$	$f_7(x)$	$f_8(x)$	$f_9(x)$	$f_{10}(x)$	$f_{11}(x)$	$f_{12}(x)$	$f_{13}(x)$	$f_{14}(x)$	$f_{15}(x)$	$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