6533b82cfe1ef96bd12903f7

RESEARCH PRODUCT

Kvantu algoritmi simbolu virkņu uzdevumiem

subject

description

Darbā tiek apskatīti trīs simbolu virkņu uzdevumi. Pirmais no tiem ir nosaukts ”vārda meklēšana tekstā”: dotajam tekstam 𝑠 garuma 𝑛 un vārdam 𝑡 garumā 𝑚, pateikt, vai vārds atro­ das tekstā. Klasiski šo var atrisināt laikā 𝑂(𝑛 + 𝑚) ar Knuta­Morisa­Prata algoritmu, kvantiski ̃ √𝑛 + √𝑚) = 𝑂( ̃ √𝑛) laika algoritms. Kaut gan zināms, ka vispārīgajā gadījumā ne­ eksistē 𝑂( √ pieciešami Ω( 𝑛) vaicājumi virknes simboliem, nav skaidrs, vai šī apakšējā robeža izpildās pie √ jebkuras m vērtības. Šajā darbā mēs pierādām, ka arī tad nepieciešami Ω( 𝑛) vaicājumi. Otrais uzdevums ir nosaukts ”visbiežāk sastopamas virknes meklēšana”: dotiem 𝑛 virknēm garumā 𝑘 √ ̃ pateikt, kāda virknē sastopas visbiežāk. Kvantiski to var atrisināt 𝑂(𝑛 𝑘). Mēs piedāvājam ātrāku zināmu algoritmu diviem īpašiem gadījumiem, kad var atkārtoties tikai viena virkne ar √ ̃ 3 2 𝑘), kā arī vispārinājumu, kad parējās virknes var atkārtoties ma­ vaicājuma sarežģītību 𝑂(𝑛 𝐿 √ ̃ 𝐿+1 zāk par 𝐿 reizēm ar vaicājuma sarežģītību 𝑂(𝑛 𝑘), un gadījumam, kad ir 𝑐 unikālas virknes √ ̃ √𝑐 + 𝑐 𝑛𝑘). Trešais uzdevums ir ”tekstā konstruēšana no vārdnī­ ar vaicājuma sarežģītību 𝑂(𝑛 cas”: dotajām tekstam 𝑠 garumā 𝑛 un vārdnīcai no 𝑚 vārdiem ar kopējo garumu 𝐿 pateikt, vai var uzbūvēt 𝑠 tikai no vārdnīcas vārdiem. Mēs apskatām gadījumu kad vārdi nevar pārklāties ̃ ⋅ √ min(𝑛, 𝑚) + 𝐿).