Kvantu skaitļošanas konstrukcijas

Abstract

Kvantu modelis ar pēcatlasi tiek definēts Scott Aaronson darbā. Beigu stāvokĜu kopa,\nkas parasti sastāv no akceptējošiem un noraidošiem stāvokĜiem, tiek papildināta ar\nparametru, kas norāda, vai dotais beigu stāvoklis ietilpst atlases kopā. Mērījumi tiek\nveikti tikai atlases kopas beigu stāvokĜos. Tiek ieviests papildus stāvoklis + q , un ja\nvisu pēcatlases stāvokĜu amplitūdas ir 0, tad + q amplitūda saĦem vērtību 1.\nPēcatlase Ĝauj pētīt ne tikai kvantu, bet arī tradicionālo algoritumu īpašības.\nPētījuma mērėis ir salīdzināt varbūtisko un kvantu galīgo pēcatlases automātu klases\nun aprakstīt valodu klases, ko atpazīst kvantu galīgs automāts ar pēcatlasi.\nPētījuma procesā iegūti šādi rezultāti:\n• Definēts kvantu galīgā automāta ar pēcatlasi jēdziens;\n• Aprakstīta valoda PALINDROMES, ko atpazīst galīgs kvantu automāts ar\npēcatlasi ar mērījumu katrā solī un galīgs kvantu automāts ar pēcatlasi ar\nmērījumu beigās;\n• Aprakstīta valoda, kuru nevar atpazīt galīgs kvantu automāts ar pēcatlasi ar\nmērījumu katrā solī un galīgs kvantu automāts ar pēcatlasi ar mērījumu beigās:\nL = {w | w∈{0,1}* and there exist x, y,u, z such that w = x1y = u1z and\nx = z }\nViens no promocijas darba uzdevumiem ir aplūkot kvantu vaicājošos algoritmus Bula\nfunkciju rēėināšanai. Darba sākumā tiek pierādīti kvantu algoritmu apakšējie\nnovērtējumi dažādām funkcijām, kas apraksta grafu problēmas. Ir izveidoti efektīvi\nkvantu vaicājošie algoritmi. Šajā sadaĜā iegūti rezultāti sekojošām funkcijām:\n• 3-sum problēma,\n• Hamiltona ceĜš,\n• Hamiltona aplis,\n• CeĜojošais pārdevējs.\nVēl promocijas darbā tiek apskatīta reāla laika Tjūringa mašīnas kvantu analoăija.\nTiek parādīts, ka eksistē valoda, kuru pazīst reāla laika kvantu Tjūringa mašīna un\nnepazīst reāla laika determinēta Tjūringa mašīna.