6533b7d3fe1ef96bd12603f2

RESEARCH PRODUCT

Kvantu algoritmu sarežģītības novērtējumi

subject

description

Anot¯acija Kvantu algoritmu veiktsp¯ejas p¯ar¯akums par klasiskajiem algoritmiem ir gal- venais iemesls paˇsreiz¯ejai lielai ieinteres¯et¯ibai par kvantu skaitl¸oˇsanu. Vieni no slaven¯akiem kvantu algoritmiem ir Grovera mekl¯eˇsanas algoritms un ˇSora skaitl¸u faktoriz¯acijas algoritms. Piem¯eram, Grovera algoritms atrisina el- ementa mekl¯eˇsanas probl¯emu N elementu sarakst¯a ar laiku Ø(pN), kaut klasiskam algoritmam ir nepiecieˇsams ­(N) laiks, lai atrisin¯atu ˇso probl¯emu. T¯atad m¯es esam l¸oti ieienteres¯eti atrast ˇs¯adas probl¯emas, kur¯am kvantu al- goritms var b¯ut par¯aks par klasisko analogu. Kvantu skaitl¸oˇsanas centr¯alais jaut¯ajums ir, cik sp¯ec¯ıgi ir kvantu algoritmi? Cik liels veiktsp¯ejas uzlabo- jums ir iesp¯ejams? ˇSaj¯a darb¯a m¯es sniedzam daˇzus jaut¯ajumus uz ˇs¯ım jaut¯ajumiem. M¯es apl¯ukojam divas lielas probl¯emas ˇsaj¯a darb¯a. Pirmk¯art, m¯es apl¯ukojam cikla eksistences graf¯a probl¯emu. M¯es pied¯av¯ajam kvantu vaic¯ajoˇso algo- ritmu, kas atrisina ˇso probl¯emu efekt¯ıv¯ak par jebkuru klasisko analogu, un pier¯ad¯am, ka m¯usu pied¯av¯atais algoritms ir optim¯als. Otrk¯art m¯es turpin¯am p¯et¯ıjumus par varb¯utiskiem apgrieˇzamiem autom¯atiem, izp¯etot apst¯adin¯amo varb¯utisko apgrieˇzamo autom¯atu (DH-PRA) ¯ıpaˇs¯ıbas. M¯es par¯ad¯am visp¯ar¯ejo valodu klasi, ko nevar paz¯ıt ar DH-PRA, un kas ir l¸oti l¯ıdz¯ıga valodu klasei, ko nevar paz¯ıt ar daudz-m¯er¯ıjumu kvantu autom¯atiem (MM-QFA). M¯es ar¯ı par¯ad¯am, ka valodu klase, kuru paz¯ıst DH-PRA nav sl¯egta pret apvienojuma oper¯aciju. Tas l¸auj mums izteikt min¯ejumu, ka val- odu klase, ko paz¯ıst DH-PRA autom¯ati iekl¸auj valodu klasi, ko paz¯ıst MM- QFA vai nu ˇs¯ıs klases ir ekvivalentas. M¯es turpin¯am str¯ad¯at pie ˇs¯ı min¯ejuma pier¯ad¯ıˇsanas.