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 {\displaystyle 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 {\displaystyle n=1} (kubitas kuris yra busenoje |0>), tai klasikiniui kompiuteriui reikia k = 2 1 − 1 + 1 = 2 {\displaystyle k=2^{1-1}+1=2} bandymu, o kvantiniui kompiuteriui reikia n = 1 {\displaystyle n=1} vieno bandymo. Jei n = 2 {\displaystyle n=2} tai klasikiniui kompiuteriui reikia k ≤ 2 2 − 1 + 1 = 3 {\displaystyle 2^{2-1}+1=3} bandymų, o kvantiniui tik 1 bandymo. Jei n = 3 {\displaystyle n=3} , tai klasikiniui kompiuteriui reikia k ≤ 2 3 − 1 + 1 = 5 {\displaystyle 2^{3-1}+1=5} bandymų. Jei n = 4 {\displaystyle n=4} , tai klasikiniui kompiuteriui reikia k ≤ 2 4 − 1 + 1 = 9 {\displaystyle 2^{4-1}+1=9} bandymų. Jei n = 5 {\displaystyle n=5} , tai klasikiniui kompiuteriui reikia k ≤ 2 5 − 1 + 1 = 17 {\displaystyle 2^{5-1}+1=17} bandymų, kvanitniui kompiuteriui tik 1 bandymo. Su tikimybiniu kompiuteriu galima nustatyti suklydymo tikimybę ϵ ≤ ( 1 2 ) k − 1 {\displaystyle \epsilon \leq ({1 \over 2})^{k-1}} po k bandymų, kur k ≤ 2 n − 1 + 1. {\displaystyle k\leq 2^{n-1}+1.} Tikimybiniam kompiuteriu reikia k = log 2 ⁡ 1 ϵ + 1 {\displaystyle k=\log _{2}{1 \over \epsilon }+1} bandymų (priklausomai kokio tikslumo ϵ {\displaystyle \epsilon } reikia), o kvantiniui kompiuteriui tik 1 bandymo. Pavyzdžiui, po 100 bandymų neteisingo atsakymo tikimybė yra ϵ ≤ 2 − 100 ≈ 10 − 30 . {\displaystyle \epsilon \leq 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 {\displaystyle >8} (nes 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.