Limitations of Quantum Walks and Randomized Algorithms
Jevgēnijs Vihrovs · E-resource repository of the University of Latvia (University of Latvia) · 2019
Šajā darbā tiek pētīta algoritmu sarežģītība dažādos skaitļošanas modeļos. Konkrētāk, tiek 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. Pirmajā daļā tiek aplūkotas Grovera kvantu klejošana un meklēšana grafos. Darbā tiek sniegts vispārīgs matemātisks apraksts klejošanas lokalizācijai un meklēšanas stacionārajiem stāvokļiem. 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.