Egy új kvantum algoritmus a Z^n_{2^t} csoport rejtett eltolás problémájára Fizika, Földtudományok és Matematika

35 OTDK, Fizika, Földtudományok és Matematika Szekció, Számítástudomány és operációkutatás Tagozat.

Egy új kvantum algoritmus a Z^n_{2^t} csoport rejtett eltolás problémájára

Helyezés: 1

Hallgató: Csáji Gergely
Szak: Matematikus, Képzés típusa: msc, Intézmény: Eötvös Loránd Tudományegyetem, Kar: Természettudományi Kar

Témavazető: Ivanyos Gábor - egyetemi tanár (BME), N N SZTAKI

A dolgozatomban a kvantum algoritmusok két jelentős problémájával, a rejtett eltolás és rejtett részcsoport problémákkal foglalkozom. Ezeknek speciális esetei például a prímfaktorizáció és a diszkrét logaritmus probléma is (sőt majdnem minden olyan feladat, amire ismert a klasszikusnál exponenciálisan gyorsabb kvantum algoritmus). Ezen problémákra már több,  különböző hatékonyságú algoritmus is ismert, azonban főleg csak speciális esetekre (pl. diédercsoport).
Dolgozatomban egy új, önállóan készített algoritmust mutatok be, mely a ` ` `mathbb{Z}_{2^t}^n`  csoport rejtett eltolásproblémáját oldja meg `n` -ben polinomiális és `t` -ben exponenciális időben, valamint négyzetes klasszikus és lineáris kvantum tárban . Eddig alapvetően két algoritmus (és változataik) ismert erre a feladatra, az egyik Kuperbergé, mely szubexponenciális  idejű és polinomiális tárigényű, a másik a FIMSS algoritmus, mely szintén `n` -ben polinomiális, `t` -ben exponenciális idejű, de exponenciális a tárigénye.
A második fejezetben adok egy rövid bevezetést a kvantumszámítástudományba, melyben vázolom a kvantumszámítógépek egyik alapvető modelljét, amelyet a dolgozatomban is felhasználok.
A harmadik fejezet tartalmazza az algoritmus részletes leírását.
A negyedik fejezetben az algoritmus elemzése, a helyességének bizonyítása, a felhasznált módszerek kifejtése, illetve a jelenlegi algoritmusokkal való összehasonlítása található. Befejezésül pedig az algoritmus egy módosított változatát is felvázolom, mellyel speciális inputokra is futtatható.