Algebrai kvantumalgoritmusok
| Témavezető: | Ivanyos Gábor |
| SZTAKI, Informatikai Kutatólaboratórium | |
| email: | Ivanyos.Gabor@sztaki.hu |
Projekt leírás
Napjainkban jelentősen megnőtt az érdeklődés a kvantumszámítástudomány iránt. Egyrészt Peter Shor forradalmi algoritmusai nyomán, melyek polinomiális időben megoldják a prímfaktorizációs és diszkrét-log problémákat, másrészt az első kvantumszámítógépek sikeres létrehozása miatt. Azóta kiderült, hogy ezen két probléma és még rengeteg más is, mind egy algebrai feladat, az úgynevezett rejtett részcsoport probléma speciális esetei. Erre Abel-csoportok esetében már létezik általános polinomiális idejű kvantumalgoritmus, a nemkommutatív eset viszont jóval bonyolultabb, itt még csak speciális esetekre ismertek hatékony megoldások (pl. diédercsoport), azonban ezek legjobb esetben is szubexponenciális idejűek. A feladat a témakörhöz kapcsolódó cikkek és szakirodalom feldolgozása és elsajátítása, illetve új algoritmusok keresése.