Shor-algoritmus

A Wikipédiából, a szabad enciklopédiából

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.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Irodalom[szerkesztés | forrásszöveg szerkesztése]

  • 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 | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

  1. 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