Shor-algoritmus
A Shor-algoritmus (kvantumszámítógépekre tervezett) kvantumalgoritmus, amellyel polinomiális időben végezhető el az egész számok prímfelbontása. Az algoritmust feltalálójáról, Peter Shor amerikai matematikusról nevezték el.
Ha N jelöli a számot, amelynek prímtényezőit keressük (tehát a bemenet mérete log N), akkor az algoritmus O((log N)3) időben fut le. Ez azt jelzi, hogy a prímfelbontási probléma a BQP bonyolultsági osztályba tartozik.[1]
A Shor-algoritmus hatékonysága a kvantum Fourier-transzformáció és az ismételt négyzetre emelésekkel végrehajtott moduláris hatványozás hatékonyságán alapszik.
A prímfelbontás a rejtettrészcsoport probléma speciális esete (amelyben egy véges kommutatív csoport részcsoportját keressük); a kvantuminformatika fontos kérdése, hogy általánosítható-e az algoritmus bonyolultabb szerkezetű csoportokra. A tetszőleges permutációcsoportokra való általánosítás megoldaná a gráfizomorfizmus problémáját.
Kapcsolódó szócikkek
[szerkesztés]Irodalom
[szerkesztés]- Martín-López, Enrique; Enrique Martín-López, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou & Jeremy L. O'Brien (12): "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". (hely nélkül): Nature Photonics. 2012.
További információk
[szerkesztés]- http://web.cs.elte.hu/blobs/diplomamunkak/bsc_alkmat/2012/koronka_gabor.pdf
- http://arxiv.org/abs/quant-ph/0010034
Források
[szerkesztés]- ↑ Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H. & Chuang, Isaac L. (2001), "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance" (PDF), Nature 414 (6866): 883–887, arXiv:quant-ph/0112176, Bibcode:2001Natur.414..883V, doi:10.1038/414883a, PMID 11780055
|
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |