Jevgēnijs Vihrovs - jaunais datorzinātņu doktors

Darbu recenzēja profesors, Dr.sc.comp. J.Vīksna (LU), docents, Dr.math. M. Ozols (Amsterdamas Universitāte, Nīderlande), asociētais profesors, Dr. E. Montanaro (Bristoles Universitāte, Lielbritānija).

Par promocijas darbu

Promocijas darbā tika pētīta algoritmu sarežģītība dažādos skaitļošanas modeļos, konkrētāk, pētītas kvantu klejošanas algoritmu īpašības un ierobežojumi, kā arī varbūtisko vaicājumalgoritmu darbības laika novērtēšanas metodes.

Darba pirmajā daļā tiek aplūkotas Grovera kvantu klejošana un meklēšana grafos un sniegts vispārīgs matemātisks apraksts klejošanas lokalizācijai un meklēšanas stacionārajiem stāvokļiem. Savukārt otrajā daļā tiek aplūkotas apakšējo novērtējumu metodes varbūtisko vaicājumalgoritmu modelī. Darbā tiek pierādīta klasisko pretinieka metožu asimptotiskā ekvivalence visur definētām funkcijām, un aprakstītas to atšķirības daļēji definētām funkcijām. Tiek arī aplūkota saistība starp bloku jutīgumu un daļskaitļu bloku jutīgumu.

Darba rezultāti matemātiski izskaidro kvantu klejošanas lokalizāciju (kad klejotājs iesprūst vienā vietā), kā arī kvantu klejošanas stacionārus stāvokļus, kuros kvantu meklēšanas stāvoklis vienmēr paliek nemainīgs (un līdz ar to kvantiski nav priekšrocības). Tāpat tika pierādīts, ka vairākas metodes (pretinieka apakšējie novērtējumi), ar kurām novērtē, cik ilgi ir jāstrādā varbūtiskajiem algoritmiem, ir savā starpā ekvivalentas visur definētām funkcijām, un var būt atšķirīgas daļēji definētām funkcijām (funkcija šajā gadījumā ir skaitļošanas uzdevums).