Doičo-Džozo algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Doičo-Džozo algoritmas yra kvantinis algoritmas, pasiūlytas David Deutsch ir Richard Jozsa 1992 metais. Jis buvo vienas iš pirmų algoritmų sukurtų kvantiniams kompiuteriams, kuris naudodamas tokius reiškinius kaip superozicija ir paralelizmas turėtų būti žymiai efektingesnis nei klasikiniai algoritmai.

Doičo ir Doičo-Džozo algoritmai nustato ar įėjime yra lyginis skaičius vienetų ar nelyginis. Jeigu lyginis skaičius, tai atsakimas, kuris bus duotas iš vieno kubito, bus |0> (jeigu vienetų iš vis nėra vis tiek skaitoma, kad funkcija lyginė). O jeigu vienetų skaičius nelyginis, tai atsakymas bus duotas, iš to paties vieno kubito, |1>.

Doičo-Džozo algoritmas duoda eksponentinį paspartėjimą. Klasikiniam kompiuteriui, kad išspręsti tokią užduotį reikia 2n žingsnių, o kvantiniui kompiuteriui tik n žingsnių, kur n kubitų skaičius.


Turinys

[taisyti] Doičo-Džozo algoritmo skaičiavimai

Turime shemą kuri skirta Doičo algoritmui skaičiuoti. Ta shema turi 3 kubitų įėjimus (input) ir 3 kubitų išėjimus (output).

Apskaičiuokime koks bus išėjimas, kai įėjimas yra |1,1,-1>. Laiko momentu t=0, kubitai užsirašo taip:

t=0, |1>|1>|-1>=|1,1,-1>.

Dabar visus 3 kubitus praleisime pro Hadamardo vartus:

t=1,  \frac{1}{\sqrt{2^3}}(|1\rangle + |-1\rangle)(|1\rangle + |-1\rangle)(|1\rangle - |-1\rangle)=
 \frac{1}{\sqrt{2^3}}(|1\rangle + |-1\rangle)(|1,1\rangle-|1,-1\rangle+|-1,1\rangle-|-1,-1\rangle)=
= \frac{1}{\sqrt{2^3}}(|1,1,1\rangle-|1,1,-1\rangle+|1,-1,1\rangle-|1,-1,-1\rangle +|-1,1,1\rangle-
-|-1,1,-1\rangle+|-1,-1,1\rangle-|-1,-1,-1\rangle).

Dabar pažymėkime, kad pirmas kubitas yra x, antras kubitas yra y, o trečias kubitas yra z. Dabar laiko momentu t=2, praleisime visus tris kubitus pro Controlled-U vartus. Pirmų dviejų kubitų ket (| >) skliaustuose nekeičiame, jei trečias kubitas yra 1. Pirmi du kubitai bus padauginti iš trečio, jei trečias kubitas yra -1:

t=2,  \frac{1}{\sqrt{2^3}}(|1,1,1\rangle-|-1,-1,-1\rangle+|1,-1,1\rangle-|-1,1,-1\rangle +|-1,1,1\rangle-|1,-1,-1\rangle+|-1,-1,1\rangle-
-|1,1,-1\rangle)=\frac{1}{\sqrt{2^3}}(|1\rangle+ |-1\rangle)(|1\rangle + |-1\rangle)(|1\rangle - |-1\rangle).
Dabar toliau visus kubitus praleisime pro Hadamardo vartus. Ir tada gausime:
t=3,  |1,1,-1\rang.
Kaip matome trečias (o du pirmi jau nerupi) kubitas yra -1, jį išmatavus. Tai reiškia, kad funkcija yra subalansuota, nes funkcija bus konstanta tik tada, kai trečias kubitas bus nulis.

Suvedame visus įmanomus išėjimus, su visais įmanomais įėjimais.

|1,1,-1> ---> |1,1,-1\rang arba |0,0,1> ---> |1>;
|-1,-1,-1> ---> |-1,-1,-1\rang arba |1,1,1> ---> |1>;
|1,-1,-1> ---> |1,-1,1\rang arba |0,1,1> ---> |0>;
|-1,1,-1> ---> |-1,1,1\rang arba |1,0,1> ---> |0>.
|1,1,1> ---> |1,1,1\rang arba |0,0,0> ---> |0>;
|-1,-1,1> ---> |-1,-1,1\rang arba |1,1,0> ---> |0>;
|1,-1,1> ---> |1,-1,1\rang arba |0,1,0> ---> |1>;
|-1,1,1> ---> |-1,1,1\rang arba |1,0,0> ---> |1>.

Kaip matome, funkcija yra konstanta kai ant įėjimo vienetų yra lyginis skaičius. Jei ant įėjimo vienetų yra nelyginis skaičius, tai funkcija yra subalansuota. Orakulas nustato ar funkcija yra lyginė ar nelyginė. Pavyzdžiui, galima manyti, kad |000> tai yra f(x)=x0, |100> - tai f(x)=x1, |110> - tai f(x)=x2, |111> - tai f(x)=x3, |011> - tai f(x)=x4, |001> - tai f(x)=x5, |101> - tai f(x)=x6, o |010> - tai f(x)=x7. Jeigu x yra pakeltas lyginiu skaičiumi, tai f(x) visada bus teigiamas atsakymas (pvz.: (-3)2=9), o jeigu x pakeltas nelyginiu skaičiumi, tai atsakymas gali buti neigiamas ir teigiamas priklausomai nuo to ar x teigiamas ar neigiamas (pvz.: (-3)3=-27; 33=27).

[taisyti] Doičo algoritmas su 2 kubitais

Doičo algoritmas tai XOR vartai.
Doičo algoritmas tai XOR vartai.
Ar Doičo algoritmas neįmanomas be Hadamardo vartų?
Ar Doičo algoritmas neįmanomas be Hadamardo vartų?
Nuo visu funkcijų, kur prasmę turi tik f(x)=x ir f(x)=1
Nuo visu funkcijų, kur prasmę turi tik f(x)=x ir f(x)=1
Viršutinis (pirmas) kubitas apsiverčia tik kai apatinis (antras) kubitas yra 1.
Viršutinis (pirmas) kubitas apsiverčia tik kai apatinis (antras) kubitas yra 1.

Iš pradžiu abu kubitus praleisime pro Hadamardo vartus. Įėjime turime |1,-1> (pirmas kubitas yra 1, antras yra -1), šiuo laiku t=0. Taigi praleidžiame pro Hadamardo vartus:

t=1,  \frac{1}{\sqrt{2}}(|1\rangle + |-1\rangle)\frac{1}{\sqrt{2}}(|1\rangle - |-1\rangle)=
=\frac{1}{2}(|1,1\rangle+|-1,1\rangle-|1,-1\rangle-|-1,-1\rangle).
Dabar toliau abu kubitai praeis pro orakulą (pro CNOT vartus). Pirmo kubito reikšmė nepasikeis, o antro kubito reikšmę ket skliaustuose gauname sudauginus pirmo ir antro kubitų reikšmes iki praėjimo pro CNOT vartus ir gausime:
t=2,  \frac{1}{2}(|1,1\rangle+|-1,-1\rangle-|1,-1\rangle-|-1,1\rangle)=
=\frac{1}{2}(|1\rangle - |-1\rangle)(|1\rangle - |-1\rangle).

Toliau praleidžiame tik pirmą kubitą pro Hadamardo vartus ir gauname atsakyma:

t=3, |-1\rangle \frac{1}{\sqrt{2}}(|1\rangle - |-1\rangle).


Taigi loginė šio algoritmo reikšmė yra ta, kad Doičo algoritmas iš dviejų kubitų nustato ar dviejų kubitų sandauga yra +1 ar -1. Štai visos įmanomos kubitų reikšmės:

|1,-1> ---> |-1\rangle \frac{1}{\sqrt{2}}(|1\rangle - |-1\rangle) ---> -1 arba |0,1> ---> |1\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) ---> 1;
|-1,1> ---> |-1\rangle \frac{1}{\sqrt{2}}(|1\rangle + |-1\rangle) ---> -1 arba |1,0> ---> |1\rangle \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) ---> 1;
|1,1> ---> |1\rangle \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) ---> 1 arba |0,0> ---> |0\rangle \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) ---> 0;
|-1,-1> ---> |1\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) ---> 1 arba |1,1> ---> |0\rangle \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) ---> 0.

Kaip matome atsakymas pirmo kubito yra 0, tik tada kai funkcija yra konstanta, t.y. kai įėjimo kubitai visi yra tie patys (vienodi).

[taisyti] Doičo-Džozo algoritmas su 4 kubitais

Tarkime, turime tokį įėjimą:

t=0, |1>|-1>|1>|-1>=|1,-1,1,-1>.

Praleileidžiame visus kubitus pro Hadamardo vartus:

t=1, \frac{1}{4}(|1\rangle + |-1\rangle)(|1\rangle - |-1\rangle)(|1\rangle + |-1\rangle)(|1\rangle - |-1\rangle).

Toliau iškeliame koficientą priešais |-1>. Pirmo kubito šis koficientas bus +1, antro kubito -1, trečio kubito +1 ir ketvirto kubito -1. Dabar, kad apskaičiuoti koks bus rezultatas perėjus per Controlled-U vartus reikia pirmų 3 kubitų koficientus padauginti iš ketvirto (paskutinio) kubito koficiento (paskutinio kubito reikšmė,jei pirmas kubitas a, antras b, trečias c, o ketviratas d, tai ketviratas kubitas po perėjimo per Controlled-U vartus taps visų kubitų sandauga abcd=1*(-1)*1*(-1)=1):

t=2, \frac{1}{4}(|1\rangle + |-1\rangle)(|1\rangle - |-1\rangle)(|1\rangle + |-1\rangle)(|1\rangle + |-1\rangle).

Toliau praleidžiame visus kubitus pro Hadamardo vartus ir gauname rezultatą:

t=3, |1\rangle  |-1\rangle |1\rangle  |1\rangle =|1,-1,1,1\rangle  .

Pažiurekime kaip išėjimas priklauso nuo įėjimo (atsakymai pateikti be pirmų trijų kubitų, nes jie nesikeičia):

|-1,-1,-1,-1> ---> |1> arba |1,1,1,1> ---> |0>;
|1,1,1,-1> ---> |-1> arba |0,0,0,1> ---> |1>;
|1,1,-1,-1> ---> |1> arba |0,0,1,1> ---> |0>;
|1,-1,-1,-1> ---> |-1> arba |0,1,1,1> ---> |1>;
|-1,1,1,-1> ---> |1> arba |1,0,0,1> ---> |0>;
|1,1,-1,-1> ---> |1> arba |0,0,1,1> ---> |0>;
|1,-1,1,-1> ---> |1,-1,1,1\rang arba |0,1,0,1> ---> |0>.
|-1,-1,1,-1> ---> |-1> arba |1,1,0,1> ---> |1>;
|1,1,1,1> ---> |1> arba |0,0,0,0> ---> |0>;
|-1,-1,-1,1> ---> |1> arba |1,1,1,0> ---> |1>;
|-1,-1,1,1> ---> |1> arba |1,1,0,0> ---> |0>;
|-1,1,1,1> ---> |1> arba |1,0,0,0> ---> |1>;
|1,-1,-1,1> ---> |1> arba |0,1,1,0> ---> |0>;
|1,1,-1,1> ---> |1> arba |0,0,1,0> ---> |1>;
|1,-1,1,1> ---> |1> arba |0,1,0,0> ---> |1>;
|-1,1,-1,1> ---> |1> arba |1,0,1,0> ---> |0>;

Kaip matome funkcija yra konstanta kai vienetų skaičius lyginis, ir funkcija yra subalansuota, kai vienetų skaičius nelyginis (ir jeigu ant įėjimo visi nuliai funkcija konstantaa).

[taisyti] Bendras Doičo-Džozo algoritmo skaičiavimas

Manykime, turime n kubitų (įėjimų) |1>|-1>|1>|-1>...|n>=|1,-1,1,-1,...,n> (0=1; 1=-1). Pažymėkime visus kubitus taip:

t=0 |x_1 \rang |x_2 \rang |x_3 \rang...|x_n \rang=|x_1,x_2,x_3,..,x_n \rangle .

Tuomet ant išėjimo turėsime:

t=3 |x_1  ,x_2, x_3  ,..., x_{n-1},  x_n \times x_1 \times x_2 \times x_3 \times...\times  x_{n-1}  \rang.


[taisyti] Nuorodos

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