Quantum algorithm complexity
Vasilijs Kravcevs
Abstract
Kvantu algoritmu veiktspējas pārākums par klasiskajiem algoritmiem ir galvenais iemesls pašreizējai lielai ieinteresētībai par kvantu skaitļošanu. Vieni no slavenākiem kvantu algoritmiem ir Grovera meklēšanas algoritms un šora skaitļu faktorizācijas algoritms. Piemēram, Grovera algoritms atrisina elementa meklēšanas problēmu N elementu sarakstā ar laiku Ø(pN), kaut klasiskam algoritmam ir nepieciešams ¬(N) laiks, lai atrisinātu šo problēmu. Tātad mēs esam ļoti ieinteresēti atrast šādas problēmas, kurām kvantu algoritms var būt pārāks par klasisko analogu. Kvantu skaitļošanas centrālais jautājums ir, cik spēcīgi ir kvantu algoritmi? Cik liels veiktspējas uzlabo jums ir iespējams? Šajā darbā mēs sniedzam dažus jautājumus uz šīm jautājumiem. Mēs aplūkojam divas lielas problēmas. Pirmkārt, mēs aplūkojam cikla eksistences grafā problēmu. Mēs piedāvājam kvantu vaicājošo algo ritmu, kas atrisina šo problēmu efektīvāk par jebkuru klasisko analogu, un pierādām, ka mūsu piedāvātais algoritms ir optimāls. Otrkārt mēs turpinām pētījumus par varbūtiskiem apgriežamiem automātiem, izpētot apstādināmo varbūtisko apgriežamo automātu (DH-PRA) īpašības. Mēs parādām vispārējo valodu klasi, ko nevar pazīt ar DH-PRA, un kas ir ļoti līdzīga valodu klasei, ko nevar pazīt ar daudzmērījumu kvantu automātiem (MM-QFA). Mēs arī parādām, ka valodu klase, kuru pazīst DH-PRA nav slēgta pret apvienojuma operāciju. Tas ļauj mums izteikt minējumu, ka valodu klase, ko pazīst DH-PRA automāti iekļauj valodu klasi, ko pazīst MM- QFA vai nu šīs klases ir ekvivalentas. Mēs turpinām strādāt pie šī minējuma pierādīšanas.