Kvantový algoritmus pro problém bezctvercového císla

Ročník: 38 (2015/16)

Kategorie: 1: matematika a statistika

2. místo

Práce představuje komplexní, avšak snáze přístupný vhled do problematiky kvantových výpočetních systémů. Po krátkém představení základních charakteristik kvantových počítačů se autor intezivně zabývá možností, jak by bylo při využití efektivity diskutovaných systémů možné vyřešit problém bezčtvercovosti čísla. Práce prezentuje návrh takového algoritmu, který řeší problém efektivně a exaktně (řadí se tedy do složitostní třídy (EQP) a který po teoretické stránce vychází ze specifických vlastností Gaussových sum. Spolu s tím autor demonstruje možnou implementaci algoritmu v jazyce Quantum Computing Language, kdy za tímto účelem konstruuje kvantové obvody pro výpočet největšího společného dělitele (GCD) a Jacobiho symbolu, dvou elementárních funkcí z oblasti teorie čísel.

Text práce ve formátu PDF
stáhnout přílohu