6533b820fe1ef96bd12794dd
RESEARCH PRODUCT
Algoritmu sarežģītības novērtējumi bumbas meklēšanas modelī
ĒRiks Gopakssubject
Datorzinātnealgoritmikvantu skaitļošanabumbas meklēšanas modeliskombinatorikavaicājumu sarežģītībadescription
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ārās operācijas AND, OR, XOR. Rezultātā visiem darbā aprakstītajiem algoritmiem ir pierādīti kvantu vaicājumu sarežģītības novērtējumi no augšas.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2015-01-01 |