Algoritmu sarežģītības novērtējumi bumbas meklēšanas modelī

2015

Viena no aktuālākajām problēmām kvantu skaitļošanas nozarē ir kvantu datoru priekšrocību noteikšana salīdzinājumā ar klasiskajiem datoriem. Priekšrocības bieži tiek demonstrētas, pierādot kvantu algoritmu sarežģītības novērtējumu no augšas, kurš ir labāks par novērtējumu jebkuram klasiskajam algoritmam tādas pašas problēmas risināšanai. Darba mērķis ir izpētīt vairākas skaitļošanas problēmas nesen izgudrota „bumbas meklēšanas” skaitļošanas modeļa ietvaros, lai iegūtu tiem atbilstošu algoritmu kvantu vaicājumu sarežģītības novērtējumus, kuri ir potenciāli labāki par zināmajiem. Pētīto algoritmu starpā ir vairāki algoritmi uz simbolu virknēm, daži algoritmi uz grafiem, kā arī vairāku bitu bin…