Quantum algorithms for string problems

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(, ) + ).We consider three string processing problems. The first is the ”string matching” problem:given textof lengthand a stringof length, find whether stringis present in text. Classically this problem can be solved in( + )time, due to Knuth­Morris­Pratt, bestknown quantum algorithm has query complexity of̃(√ +√) =̃(√). For generalcase query complexity lower bound ofΩ(√)exists, it is unknown whether this holds for allvalues. In this paper we prove, that lower boundΩ(√)for all values of. The secondis the ”most frequent string search”: givenstrings of size, output string that occurs mostfrequently. Best known quantum algorithm have query complexity of̃(√). We give twoquantum algorithms for specials cases: when there is only one string appearing more than oncewith query complexitỹ(23√), its generalization when every other string occurs less thattimes, with quantum query complexitỹ(+1√), and when there are onlyunique stringwith query complexitỹ(√ + √). The third problem we call ”constructing text fromdictionary”: given textof size, and dictionary withwords of total size, find whethertextcan be constructed from the dictionary without overlaps. We provide a quantum algorithmwith time complexitỹ( ⋅√min(, ) + )