LU konferenceTemats: "Vaicājumu sarežģītība un kvantu algoritmi".
Darba zinātniskais vadītājs: Dr. sc. comp. Andris Ambainis.
Anotācija:
Šis darbs pēta dažādu skaitļošanas modeļu spējas, īpaši kvantu skaitļošanas iespējas paātrināt klasiskus algoritmus. Darba pirmajā daļā tiek pētīti dažādi Būla funkciju sarežģītības mēri, kuri tiek lietoti lai sasaistītu un ierobežotu šo funkciju skaitļošanas sarežģītību deterministiskos vai varbūtiskos klasiskos datorus un kvantu datoros. Specifiskāk, darbā tiek parādītas jaunas, ciešākas saiknes starp kopu ar vairākiem plaši lietotiem sarežģītības mēriem – sertifikātu sarežģītību, jutīgumu un bloku jutīgumu. Vēl darbā parādītas jaunas konstrukcijas, kas sasniedz minimālu spektrālo jutīgumu – relatīvi jaunāku mēru, kas no lejas ierobežo daudzus citus. Darbā aplūkota arī atšķirība starp bloku jutīgumu un daļskaitļu bloku jutīgumu, pazīstamu arī kā varbūtisko sertifikātu sarežģītību, un parādīta uzlabota konstrukcija to atšķiršanai visur definētām funkcijām un cieša no ievades izmēra atkarīga augšējā robeža daļēji definētām funkcijām. Darba otrajā daļā pētīts kvantu datoru potenciāls klasisku algoritmu paātrināšanai. Specifiskāk, tiek pētīti kvantu meklēšanas pielietojumi divām NP-grūtām problēmām, kuras klasiski risina ar dinamisko programmēšanu – metodi, kas nepieļauj vieglus kvantu paātrinājumus. Izmantojot vairākas jaunas metodes, darbā izveidoti kvantu algoritmi ceļojošā tirgotāja uzdevumam un grafa joslas platuma minimizēšanai, kas asimptotiski ātrāki par zināmajiem klasiskajiem algoritmiem.
Recenzenti:
1) Dr. sc. comp. Juris Vīksna, Latvijas Universitāte;
2) Dr. Stacey Jeffery, Nacionālais matemātikas un datorzinātņu pētniecības institūts, Nīderlande;
3) Dr. Xiaoming Sun, Ķīnas Zinātņu akadēmija, Ķīna.
Ar promocijas darbu var iepazīties LU Bibliotēkā, Raiņa bulvārī 19.
Attālināta dalība sēdē ar iepriekšēju pieteikšanos, rakstot uz sintija.silina@lu.lv līdz 11. novembrim. Dalībai klātienē pieteikšanās nav nepieciešama.