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-Džozo užduotis skirta nustatyti ar f(n) visada turi vienodą reikšmę (visada 0 arba visada 1) su visais kintamaisiais n ar pusei srities n būna 1, o kitai pusei srities n visada būna 0.
Kad išspręsti šią užduotį klasikiniu determinuotu algoritmu, būtina įvykdyti 2n − 1 + 1 funkcijos f skaičiavimų. Klasikiniam tikimybiniam algoritmui prireiks mažiau laiko, kad duoti atsakymą su didele tikimybę. Bet kuriuo atveju, kad gauti atsakymą su 100 % tikimybe prireiks 2n − 1 + 1 (~2n) išskaičiavimų. Doičo-Džozo algoritmas visada duoda teisingą atsakymą, padaręs tik vieną funkcijos reikšmės f išskaičiavimą.
Doičo-Džozo algoritmas pagrįstas sukurtu 1985 m. Davido Deutscho tapačiu algoritmu. Šiame algoritme funkcija f(x1) yra vieno kintamojo funkcija (x1), skirtingai nuo daugelio kintamųjų funkcijos f(x1, x2, …, xn), naudojamos vėlesniame algoritme.