Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum query algorithms

Taisija Miščenko-Slatenkova

Published Jan 1, 2013• 3 citations
OpenAlex

Abstract

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

Related papers

Kvantu vaicājošie algoritmi Būla funkciju rēķināšanai

Taisija Miščenko-Slatenkova

Šajā darbā ir aplūkoti kvantu vaicājošie algoritmi Būla funkciju rēķināšanai. Apskatītas problēmas ir cieši saistītas ar uzdevumu uzkonstruēt efektīvu kvantu algoritmu patvaļīgai Būla funkcijai vai funkciju kopai. Pētījuma mērķis ir atrast kvantu algoritmus ar eksaktu sarežģītību mazāku par determinētu. Darbā ir aprakstīta jaunu eksaktu algoritmu kopa ar kvantu sarežģītību divreiz mazāku par determinētu. Darbā ir aprakstītas divas plašas kvantu algoritmu ar ierobežotu kļūdu kopas: algoritmi ar sarežģītību D(f) = 2n pret , kur 2n ir Būla funkcijas mainīgo skaits, un algoritmi ar sarežģītību D(f) =3n pret , kur 3n ir Būla funkcijas mainīgo skaits. Īpaša uzmanība ir pievērsta kvantu jaukto stāvokļu jēdzienam ar cerību uzlabot iespējamu kvantu algoritma sarežģītību.

•Jan 1, 2007•0 citations

Kvantu skaitļošanas konstrukcijas

Oksana Scegulnaja-Dubrovska

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.

•Jan 1, 2011•0 citations

Kvantu algoritmu realizācija fiziskā kvantu datorā

Mārtiņš Kālis

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.

•Jan 1, 2018•4 citations

Kvantu skaitļošana un mans ceļš zinātnē

Andris Ambainis

Rakstā aprakstīts mans ceļš kā pētniekam matemātikā un teorētiskajā datorzinātnē. Mana interese par matemātiku un programmēšanu sākās pamatskolā ar matemātikas konkursiem un populārām grāmatām par programmēšanu. Universitātē es sāku veikt pētījumus teorētiskajā datorzinātnē. Tas mani noveda pie doktora studijām Kalifornijas Universitātē, Bērklijā. Bērklijā es sāku strādāt jaunā pētniecības jomā: kvantu skaitļošanā. Kvantu skaitļošana apvieno kvantu mehāniku (kas pēta dabas likumus atomu un daļiņu līmenī) ar datorzinātni, izmantojot kvantu fizikas ietekmi ātrākai skaitļošanai vai drošākai datu pārraidei. Mana pētījuma galvenais mērķis bija noteikt, ko mēs varam aprēķināt ar kvantu datoru un kā kvantu datorus var izmantot, lai meklētu lielos datu apjomos. 2007. gadā es atgriezos Latvijas Universitātē un izveidoju kvantu skaitļošanas pētniecības grupu. Mēs sadarbojamies ar citām vadošajām Eiropas pētniecības grupām šajā jomā un esam vadījuši divus Eiropas pētniecības projektus kvantu skaitļošanas jomā.

Akadēmiskā Dzīve•Nov 19, 2014•0 citations

Limitations of Quantum Walks and Randomized Algorithms

Jevgēnijs Vihrovs

Š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.

•Jan 1, 2019•0 citations

Algoritmi în calculul cuantic

Nicolae Sfetcu

Un algoritm cuantic poate fi înțeles ca o succesiune de operații asupra qubiților: pregătirea unei stări inițiale, aplicarea unor porți cuantice, amplificarea probabilităților asociate soluțiilor dorite și, în final, măsurarea sistemului. Măsurarea este esențială, dar și limitativă: ea transformă starea cuantică într-un rezultat clasic, astfel încât proiectarea algoritmului trebuie să facă soluția corectă cât mai probabilă înainte de citire. De aceea, calculul cuantic nu înseamnă „încercarea tuturor soluțiilor în paralel”, ci folosirea interferenței pentru a întări răspunsurile utile și a anula răspunsurile greșite.

IT & C•Jan 1, 2026•0 citations
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
Šajā darbā ir aplūkoti kvantu vaicājošie algoritmi Būla funkciju rēķināšanai. Apskatītas problēmas ir cieši saistītas ar uzdevumu uzkonstruēt efektīvu kvantu algoritmu patvaļīgai Būla funkcijai vai funkciju kopai. Pētījuma mērķis ir atrast kvantu algoritmus ar eksaktu sarežģītību mazāku par determinētu. Darbā ir aprakstīta jaunu eksaktu algoritmu kopa ar kvantu sarežģītību divreiz mazāku par determinētu. Darbā ir aprakstītas divas plašas kvantu algoritmu ar ierobežotu kļūdu kopas: algoritmi ar sarežģītību D(f) = 2n pret , kur 2n ir Būla funkcijas mainīgo skaits, un algoritmi ar sarežģītību D(f) =3n pret , kur 3n ir Būla funkcijas mainīgo skaits. Īpaša uzmanība ir pievērsta kvantu jaukto stāvokļu jēdzienam ar cerību uzlabot iespējamu kvantu algoritma sarežģītību.
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.
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.
Rakstā aprakstīts mans ceļš kā pētniekam matemātikā un teorētiskajā datorzinātnē. Mana interese par matemātiku un programmēšanu sākās pamatskolā ar matemātikas konkursiem un populārām grāmatām par programmēšanu. Universitātē es sāku veikt pētījumus teorētiskajā datorzinātnē. Tas mani noveda pie doktora studijām Kalifornijas Universitātē, Bērklijā. Bērklijā es sāku strādāt jaunā pētniecības jomā: kvantu skaitļošanā. Kvantu skaitļošana apvieno kvantu mehāniku (kas pēta dabas likumus atomu un daļiņu līmenī) ar datorzinātni, izmantojot kvantu fizikas ietekmi ātrākai skaitļošanai vai drošākai datu pārraidei. Mana pētījuma galvenais mērķis bija noteikt, ko mēs varam aprēķināt ar kvantu datoru un kā kvantu datorus var izmantot, lai meklētu lielos datu apjomos. 2007. gadā es atgriezos Latvijas Universitātē un izveidoju kvantu skaitļošanas pētniecības grupu. Mēs sadarbojamies ar citām vadošajām Eiropas pētniecības grupām šajā jomā un esam vadījuši divus Eiropas pētniecības projektus kvantu skaitļošanas jomā.
Š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.
Un algoritm cuantic poate fi înțeles ca o succesiune de operații asupra qubiților: pregătirea unei stări inițiale, aplicarea unor porți cuantice, amplificarea probabilităților asociate soluțiilor dorite și, în final, măsurarea sistemului. Măsurarea este esențială, dar și limitativă: ea transformă starea cuantică într-un rezultat clasic, astfel încât proiectarea algoritmului trebuie să facă soluția corectă cât mai probabilă înainte de citire. De aceea, calculul cuantic nu înseamnă „încercarea tuturor soluțiilor în paralel”, ci folosirea interferenței pentru a întări răspunsurile utile și a anula răspunsurile greșite.