COMPLEXITY OF QUANTUM ALGORITHMS AND COMMUNICATION PROTOCOLS

Kvantu skaitļošana ir datorzinātnes apakšnozare, kas balstās uz kvantu mehānikas likumiem, kuru iespējas un priekšrocības tiek izmantotas, lai efektīvāk risinātu skaitļošanas uzdevumus. Galvenais darbā pētāmais objekts ir kvantu vaicājošo algoritmu modelis. Pētījuma galvenais mērķis ir efektīvo kvantu vaicājošo algoritmu atrašana konkrētām problēmām, kā arī vispārīgo algoritmu konstruēšanas metožu izstrādāšana. Ir iegūti rezultāti attiecībā uz dažādiem kvantu vaicājošo algoritmu tipiem, kā eksaktais algoritms, algoritms ar kļūdas varbūtību un nedeterminētais algoritms. Promocijas darba pirmajā daļā ir apskatīti kvantu eksaktie algoritmi un kvantu algoritmi ar kļūdas varbūtību Būla funkciju rēķināšanai. Otrajā daļā vaicājošo algoritmu modelis ir pielietots daudzvērtīgu funkciju rēķināšanai. Trešā daļa ir veltīta nedeterminētiem vaicājošiem algoritmiem.Quantum computing is a method of computation based on the laws of quantum mechanics. This subfield of computer science aims to employ quantum mechanical effects for the efficient performance of computational tasks. The main research object of this thesis is the quantum query model. The aim of the present research study is to discover efficient quantum query algorithms for certain problems and to develop general techniques for designing algorithms. The study has produced several outcomes regarding different kinds of quantum algorithms: exact, bounded-error, and nondeterministic. In the first part of the thesis, exact and bounded-error quantum query algorithms for computing Boolean functions are presented. In the second part, a query model is applied for computing multivalued functions. The third part is devoted to nondeterministic query algorithms