Simono algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Simono algoritmas - tai kvantinis algoritmas, kuris tam tikrą užduotį išsprendžia eksponentiškai greičiau nei klasikinis kompiuteris. Klasikiniam kompiuteriui reikia 2^{n/2} laiko, o kvantiniam kompiuteriui n^2 kubitų ir O(n) arba O(n^{2.376}) laiko. Šis algoritmas padėjo pagrindą Šoro algoritmui.

Algoritmo veikimas[taisyti | redaguoti kodą]

Turime įėjime du "srautus" kubitų n:
|\psi_0\rang=|0\rang^{\otimes n}|0\rang^{\otimes n}.
Toliau praleidžiame pro Hadamardo vartus pirmus n kubitų:
|\psi_1\rang={1\over \sqrt{2^n}}\sum_{x_1}^{2^n}|x\rang^{\otimes n}|0\rang^{\otimes n}.
Toliau praleidžiame visus 2n kubitus pro funkciją:
|\psi_2\rang={1\over \sqrt{2^n}}\sum_{x_1}^{2^n}|x\rang^{\otimes n}|f(x)\rang.

Nuorodos[taisyti | redaguoti kodą]