Anotācija\nKvantu mehānika un spēļu teorija tika radīta aptuveni vienā un tai\npašā laikā, 20.gadsimta pirmajā pusē.\nKlasiskā spēļu teorija ir viena no vislabāk attīstītākajām nozarēm\nmatemātikā un datorzinātnē. Tai ir daudz pielietojumu ekonomikā,\nbioloģijā, sociālās zinātnēs. Datorzinātnēs daudzi kriptogrāfiskie\nprotokoli arī ir balstīti uz spēļu teorijas elementiem.\nKvantu skaitļošana ir relatīvi jauns datorzinātnes atzarojums. Tā\napvieno dažādus sarežģītības teorijas un kvantu fizikas aspektus.\nMūsu mērķis ir spert vēl vienu soli un apvienot klasisko spēļu teoriju\nar kvantu skaitļošanā uzkrātām atziņām. Konkrētāk — pētīt efektus, kas\nrodas, izmantojot kvantu informāciju labi zināmās spēļu teorijas\nproblēmās.\nDarbā ir iegūti vairāki nelokālo kvantu spēļu novērtējumi — gan\nkonkrētām spēlēm, gan veselām spēļu klasēm. Bez tam tiek piedāvāta\njauna spēļu kvantizācijas shēma.
Anotācija\nKvantu mehānika un spēļu teorija tika radīta aptuveni vienā un tai\npašā laikā, 20.gadsimta pirmajā pusē.\nKlasiskā spēļu teorija ir viena no vislabāk attīstītākajām nozarēm\nmatemātikā un datorzinātnē. Tai ir daudz pielietojumu ekonomikā,\nbioloģijā, sociālās zinātnēs. Datorzinātnēs daudzi kriptogrāfiskie\nprotokoli arī ir balstīti uz spēļu teorijas elementiem.\nKvantu skaitļošana ir relatīvi jauns datorzinātnes atzarojums. Tā\napvieno dažādus sarežģītības teorijas un kvantu fizikas aspektus.\nMūsu mērķis ir spert vēl vienu soli un apvienot klasisko spēļu teoriju\nar kvantu skaitļošanā uzkrātām atziņām. Konkrētāk — pētīt efektus, kas\nrodas, izmantojot kvantu informāciju labi zināmās spēļu teorijas\nproblēmās.\nDarbā ir iegūti vairāki nelokālo kvantu spēļu novērtējumi — gan\nkonkrētām spēlēm, gan veselām spēļu klasēm. Bez tam tiek piedāvāta\njauna spēļu kvantizācijas shēma.
Anotācija\nKvantu skaitļošana ir datorzinātnes apakšnozare, kas balstās uz kvantu mehānikas likumiem.\nKvantu vaicājošais algoritms ir galvenais pētāmais objekts. Galvenais darba mērķis ir padarīt\nkvantu algoritma konstruēšanu pēc iespējas vienkāršāku.\nPētījumā ir aprakstīti kvantu vaicājošie algoritmi, kas rēķina Būla funkcijas uzdodot nelielu\nskaitu vaicājumu, un tiek piedāvāti kvantu vaicājošie algoritmi daudzvērtīgu funkciju\naprēķināšanai. Darbā ir aprakstīti vairāki efektīvi kvantu algoritmi konkrētu uzdevumu veikšanai.\nPaši nozīmīgākie ir kvantu vaicājošie algoritmi ar ierobežotu kļūdu, piemēram, piedāvāts algoritms\ndivu bitu AND Būla funkcijai, kas izmanto vienu vienīgu vaicājumu un izsniedz pareizu atbildi ar\nvarbūtību 9/10. Katrai aprakstītajai funkciju kopai ir veikta pamatīga kvantu un klasiskās\nsarežģītības analīze.\nPēdējā pētījuma daļa ir veltīta Būla funkcijām ar zemas pakāpes polinomiem, kuri\nreprezentē dotās funkcijas. Darbā piedāvātie paņēmieni ļauj uzkonstruēt Būla funkcijas ar\npietiekami lielu intervālu starp funkcijas determinēto sarežģītību un reprezentējošā polinoma\npakāpi.\nAtslēgas vārdi: kvantu skaitļošana, vaicājošais modelis, vaicājošais algoritms, daudzvērtīga\nfunkcija, zemas pakāpes Būla funkcija
Šajā darbā tiek pētīta algoritmu sarežģītība dažādos skaitļošanas modeļos. Konkrētāk, tiek pētītas kvantu klejošanas algoritmu īpašības un ierobežojumi, kā arī varbūtisko vaicājumalgoritmu darbības laika novērtēšanas metodes. Pirmajā daļā tiek aplūkotas Grovera kvantu klejošana un meklēšana grafos. Darbā tiek sniegts vispārīgs matemātisks apraksts klejošanas lokalizācijai un meklēšanas stacionārajiem stāvokļiem. Otrajā daļā tiek aplūkotas apakšējo novērtējumu metodes varbūtisko vaicājumalgoritmu modelī. Darbā tiek pierādīta klasisko pretinieka metožu asimptotiskā ekvivalence visur definētām funkcijām, un aprakstītas to atšķirības daļēji definētām funkcijām. Tiek arī aplūkota saistība starp bloku jutīgumu un daļskaitļu bloku jutīgumu.
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.
Darbā aprakstītas kvantu programmēšanas vides IBM Quantum Experience un Rigetti fiziskajiem kvantu datoriem — to iespējas un ierobežojumi, salīdzinājumā ar teorētisko kvantu algoritmu izstrādi. Apskatīti vairāki kvantu galīgā automāta realizācijas risinājumi, to efektivitāte un ierobežojumi darbībā fiziskā kvantu ierīcē un simulatorā. Lai gan pilnībā kvantu galīgo automātu publiski pieejamajos kvantu datoros šobrīd nevar realizēt, atsevišķus tā aspektus var. Realizācijas kvalitāti būtiski ietekmē divu kubitu loģisko elementu skaits un darbībai izvēlēto fizisko kubitu kvalitāte — dekoherences laiks un loģisko elementu izpildes kļūdas.
Nous présentons dans cette thèse un nouveau modèlepour les langages de programmation quantique. Notre modèle est uneadaptation de la sémantique de jeux probabilistes définie par Danos etHarmer: nous y ajoutons des stratégies quantiquespour permettre la représentation des états et des opérations quantiques.Nous établissons quelques propriétés de base de ces stratégies. Cespropriétés sont ensuite utilisées pour construire des sémantiquesdénotationnelles pour trois langages de programmation quantique. Le premierlangage est une formalisation du calcul par mesures proposé par Danoset al. Les deux autres langages sont nouveaux: ce sont deslangages quantiques d'ordre supérieur dont la syntaxe a été construiteà partir d'observations expliquant l'échec des tentatives précédentespour construire une sémantique dénotationnelle pour de tels langages. La sémantique de jeux présentée dans cette thèseest la première sémantique dénotationnelle pour de telslambda-calculs équipés de types et d'opérations supplémentairespermettant la programmation d'algorithmes quantiques. Les résultatsprésentés valident les deux approches différentes utilitées dans laconception de ces deux nouveaux languages d'ordre supérieur: une premièreoù les états quantiques sont indirectement accessibles via desréférences et une seconde où ils sont introduit directement comme desconstantes dans le langage. Les stratégies quantiques présentéespermettent de comprendre les contraintes devant êtreimposées aux systèmes de type quantique comportant des types d'ordresupérieurs. La contrainte la plus importante est le fait que l'abstractionsur une partie d'un état quantique comportant plusieurs qbits inconnus doitêtre prohibée. Les stratégies quantiques constituent un nouveau modèle mathématique quidécrit l'interaction entre les données classiques et quantiques par desdialogues entre système et environnement. L'interaction entre les differentespar
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.