6533b839fe1ef96bd12a6c6b
RESEARCH PRODUCT
Kvantu vaicājumu sarežģītība dinamiskās programmēšanas problēmām
Ansis Zvirbulissubject
kvantu vaicājums1-dimensiju dinamiskā programmēšanaDatorzinātneLWSkvantu minimuma meklēšanakvantu vaicājumu sarežģītībadescription
Dinamiskā programmēšana (DP) ir plaši pētīta no klasiskās skaitļošanas puses, un jauni rezultāti tiek atrasti katru gadu. Taču no kvantu skaitļošanas puses tā ir pētīta daudz mazāk. Tāpēc tika izvēlētas un pētītas vairākas plaši pazīstamas 1-dimensiju DP problēmas, izmantojot kvantu vaicājumu modeli. Darbā tika aplūkotas mazākā svara apakš-sekvences (LWS) problēmas, kā, piemēram, kastu komplektēšanas (NestedBoxes) problēma, kā arī dažas saistītās problēmas. Darba mērķis bija atrast aplūkotajām LWS problēmām augšējo novērtējumu, kas labāks par triviālo O ̃(n^1.5 ) vai labu apakšējo novērtējumu. Izdevās atrast vairākus mazākus rezultātus NestedBoxes problēmai – kvantu apakšējo novērtējumu Ω(n√d), klasisku O ̃(n) algoritmu pie konstanta dimensiju skaita, kvantu O ̃(n^1.34 ) algoritmu 4-ķēdes meklēšanai. Kā arī dažus rezultātus saistīto problēmu speciālgadījumiem.
year | journal | country | edition | language |
---|---|---|---|---|
2022-01-01 |