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)³) 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.

• Rejtettrészcsoport-probléma

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

• http://web.cs.elte.hu/blobs/diplomamunkak/bsc_alkmat/2012/koronka_gabor.pdf
• http://arxiv.org/abs/quant-ph/0010034

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!