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 algorithm complexity

Vasilijs Kravcevs

Published Jan 1, 2008• 1 citation
OpenAlex

Abstract

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.

Related papers

Quantum query algorithms

Taisija Miščenko-Slatenkova

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

•Jan 1, 2013•3 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

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

Representation of Quantum Algorithms with Symbolic Language and Simulation on Classical Computer

Peter Nyman

Utvecklandet av kvantdatorn är ett ytterst lovande projekt som kombinerar teoretisk och experimental kvantfysik, matematik, teori om kvantinformation och datalogi. Under första steget i utvecklandet av kvantdatorn låg huvudintresset på att skapa några algoritmer med framtida tillämpningar, klargöra grundläggande frågor och utveckla en experimentell teknologi för en leksakskvantdator som verkar på några kvantbitar. Då dominerade förväntningarna om snabba framsteg bland kvantforskare. Men det verkar som om dessa stora förväntningar inte har besannats helt. Många grundläggande och tekniska problem som dekoherens hos kvantbitarna och instabilitet i kvantstrukturen skapar redan vid ett litet antal register tvivel om en snabb utveckling av kvantdatorer som verkligen fungerar. Trots detta kan man inte förneka att stora framsteg gjorts inom kvantteknologin. Det råder givetvis ett stort gap mellan skapandet av en leksakskvantdator med 10-15 kvantregister och att t.ex. tillgodose de tekniska förutsättningarna för det projekt på 100 kvantregister som aviserades för några år sen i USA. Det är också uppenbart att svårigheterna ökar ickelinjärt med ökningen av antalet register. Därför är simulering av kvantdatorer i klassiska datorer en viktig del av kvantdatorprojektet. Självklart kan man inte förvänta sig att en kvantalgoritm skall lösa ett NP-problem i polynomisk tid i en klassisk dator. Detta är heller inte syftet med klassisk simulering. Den klassiska simuleringen av kvantdatorer kommer att täcka en del av gapet mellan den teoretiskt matematiska formuleringen av kvantmekaniken och ett förverkligande av en kvantdator. Ett av de viktigaste problemen i vetenskapen om kvantdatorn är att utveckla ett nytt symboliskt språk för kvantdatorerna och att anpassa redan existerande symboliska språk för klassiska datorer till kvantalgoritmer. Denna avhandling ägnas åt en anpassning av det symboliska språket Mathematica till kända kvantalgoritmer och motsvarande simulering i klassiska datorer. Konkret kommer vi att representera Simons algoritm, Deutsch-Joszas algoritm, Grovers algoritm, Shors algoritm och kvantfelrättande koder i det symboliska språket Mathematica. Vi använder samma stomme i alla dessa algoritmer. Denna stomme representerar de karaktäristiska egenskaperna i det symboliska språkets framställning av kvantdatorn och det är enkelt att inkludera denna stomme i framtida algoritmer.

•Jan 1, 2008•0 citations

Quantum Games, Quantum States, Their Properties and Applications

Dmitrijs Kravcenko

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.

•Jan 1, 2013•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 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.
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.
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.
Utvecklandet av kvantdatorn är ett ytterst lovande projekt som kombinerar teoretisk och experimental kvantfysik, matematik, teori om kvantinformation och datalogi. Under första steget i utvecklandet av kvantdatorn låg huvudintresset på att skapa några algoritmer med framtida tillämpningar, klargöra grundläggande frågor och utveckla en experimentell teknologi för en leksakskvantdator som verkar på några kvantbitar. Då dominerade förväntningarna om snabba framsteg bland kvantforskare. Men det verkar som om dessa stora förväntningar inte har besannats helt. Många grundläggande och tekniska problem som dekoherens hos kvantbitarna och instabilitet i kvantstrukturen skapar redan vid ett litet antal register tvivel om en snabb utveckling av kvantdatorer som verkligen fungerar. Trots detta kan man inte förneka att stora framsteg gjorts inom kvantteknologin. Det råder givetvis ett stort gap mellan skapandet av en leksakskvantdator med 10-15 kvantregister och att t.ex. tillgodose de tekniska förutsättningarna för det projekt på 100 kvantregister som aviserades för några år sen i USA. Det är också uppenbart att svårigheterna ökar ickelinjärt med ökningen av antalet register. Därför är simulering av kvantdatorer i klassiska datorer en viktig del av kvantdatorprojektet. Självklart kan man inte förvänta sig att en kvantalgoritm skall lösa ett NP-problem i polynomisk tid i en klassisk dator. Detta är heller inte syftet med klassisk simulering. Den klassiska simuleringen av kvantdatorer kommer att täcka en del av gapet mellan den teoretiskt matematiska formuleringen av kvantmekaniken och ett förverkligande av en kvantdator. Ett av de viktigaste problemen i vetenskapen om kvantdatorn är att utveckla ett nytt symboliskt språk för kvantdatorerna och att anpassa redan existerande symboliska språk för klassiska datorer till kvantalgoritmer. Denna avhandling ägnas åt en anpassning av det symboliska språket Mathematica till kända kvantalgoritmer och motsvarande simulering i klassiska datorer. Konkret kommer vi att representera Simons algoritm, Deutsch-Joszas algoritm, Grovers algoritm, Shors algoritm och kvantfelrättande koder i det symboliska språket Mathematica. Vi använder samma stomme i alla dessa algoritmer. Denna stomme representerar de karaktäristiska egenskaperna i det symboliska språkets framställning av kvantdatorn och det är enkelt att inkludera denna stomme i framtida algoritmer.
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.
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.