Simono algoritmas

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

Turime įėjime du "srautus" kubitų n:

$|{\psi }_0⟩=|0{⟩}^{\otimes n}|0{⟩}^{\otimes n}.$

Toliau praleidžiame pro Hadamardo vartus pirmus n kubitų:

$|{\psi }_1⟩=\frac{1}{\sqrt{2^n}}\sum _{x_1}^{2^n}|x{⟩}^{\otimes n}|0{⟩}^{\otimes n}.$

Toliau praleidžiame visus 2n kubitus pro funkciją:

$|{\psi }_2⟩=\frac{1}{\sqrt{2^n}}\sum _{x_1}^{2^n}|x{⟩}^{\otimes n}|f(x)⟩.$

Nuorodos

• http://arxiv.org/pdf/quant-ph/0511272.pdf
• http://www.cs.berkeley.edu/~vazirani/f04quantum/notes/lec7.pdf
• http://www.cs.berkeley.edu/~vazirani/s07quantum/notes/lecture7.pdf