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 ${\displaystyle 2^{n/2}}$ laiko, o kvantiniam kompiuteriui ${\displaystyle n^{2}}$ kubitų ir O(n) arba ${\displaystyle O(n^{2.376})}$ laiko. Šis algoritmas padėjo pagrindą Šoro algoritmui.^[1]

Algoritmo veikimas

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

${\displaystyle |\psi _{0}\rangle =|0\rangle ^{\otimes n}|0\rangle ^{\otimes n}.}$

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

${\displaystyle |\psi _{1}\rangle ={1 \over {\sqrt {2^{n}}}}\sum _{x_{1}}^{2^{n}}|x\rangle ^{\otimes n}|0\rangle ^{\otimes n}.}$

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

${\displaystyle |\psi _{2}\rangle ={1 \over {\sqrt {2^{n}}}}\sum _{x_{1}}^{2^{n}}|x\rangle ^{\otimes n}|f(x)\rangle .}$

Šaltiniai

1. Shor, Peter W. (1999-01-01). „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer“. SIAM Review. 41 (2): 303–332. arXiv:quant-ph/9508027. doi:10.1137/S0036144598347011. ISSN 0036-1445.

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