Ugrás a tartalomhoz

Shor-algoritmus

Ellenőrzött
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.

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]

Források

[szerkesztés]
  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