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.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
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 Rejtettrészcsoport-probléma
Irodalom
További információk http://web.cs.elte.hu/blobs/diplomamunkak/bsc_alkmat/2012/koronka_gabor.pdf http://arxiv.org/abs/quant-ph/0010034 Jegyzetek
Kategória:Algoritmusok