Š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.
Š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 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
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.
A computação quântica é um modelo computacional baseado nas leis da mecânica quântica, que pode ser utilizado para desenvolver algoritmos mais eficientes que seus correspondentes clássicos. O desenvolvimento de algoritmos quânticos eficientes, no entanto, é uma tarefa altamente desafiadora. Uma abordagem recente que vem se mostrando bem-sucedida é a utilização de caminhadas quânticas. Neste trabalho, estudamos a caminhada quântica no hipercubo, calculando analiticamente sua distribuição estacionária e analisando propriedades de seu mixing time, tanto na situação ideal como na situação com descoerência gerada por ligações interrompidas. Também estudamos a caminhada na malha bidimensional, calculando sua distribuição estacionária analiticamente e explorando a relação entre o mixing time e a complexidade do algoritmo de busca nesse grafo. Desenvolvemos uma ferramenta computacional para simulação numérica de caminhadas quânticas em malhas uni- e bidimensionais com diversas condições de contorno. Finalmente, estudamos alguns algoritmos de busca em grafos e analisamos numericamente o impacto que a descoerência exerce sobre seus desempenhos.
V posledných rokoch, bolo do výzkumu kvantových počítačov vynaložené veľke úsilie, s ktorým prišla aj potreba porozumieť kvantovému počítaniu. Kvantové algoritmy sú nevyhnutnými nástrojmi, ktoré potrebujeme vymyslieť a vylepšiť, aby sme efektívne využili teoretickú výpočetnú silu kvantových počítačov. Táto bakalárska práca, sa zaoberá čím viac populárnejším kvantovým modelom nazývaným kvantová prechádzka, konkrétne variantou diskrétneho času. V tejto práci skúmame základy kvantového počítania spolu so základnými pojmami parametrov riadiacich vlastnosti kvantových prechádzok. Rozsiahlo popisujeme kvantové prechádzky, vymenujeme a krátko predstavujeme rôzne modely kvantových prechádzok a ukážeme prepojenie medzi nimi a Groverovým algoritmom. Okrem toho, skúmame využitie kvantových prechádzok na vyľadávanie v databázach, perfektný prenos stavu a transport, kde táto časť tvorí jadro tejto práce. Následne vyšetrujeme vlastnosti vyhĺadávania a transportu na konkrétnych grafoch ako hviezdový graf a kompletý graf.
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.
O objetivo do trabalho é estudar algoritmos quânticos de busca, usados em computadores quânticos. Até então, algoritmos de busca utilizados em computadores clássicos dependem da estrutura na qual os dados estão organizados para serem ou não eficientes. Para conjuntos de dados não estruturados, o único jeito é verificar cada elemento do conjunto procurando o elemento passado na entrada do algoritmo, e dependendo da quantidade de elementos nesse conjunto, pode-se levar muito tempo, mesmo para computadores muito rápidos. Portanto, algoritmos que realizem busca de maneira eficiente são um atrativo e tanto para cientistas da computação, que podem pensar em inúmeras aplicações dos mesmos e tornar vários softwares cada vez mais eficientes. Tendo isso em vista, a computação quântica traz artifícios inexistentes na computação clássica que podem acelerar esse processo, como, por exemplo, o paralelismo quântico. Basicamente, consiste na capacidade de sobrepor todos os dados do conjunto em um único registrador, ou a grosso modo, analisar todos ao mesmo tempo, apesar de não ser tão simples quanto isso. É baseado nisso que temos o Algoritmo de Grover, que utilizando o paralelismo quântico, e reflexões no conjunto de dados, através do uso de transformações unitárias feitas por portas quânticas, temos uma probabilidade alta de que quando medirmos este registrador quântico, termos como resultado o dado procurado.