6533b86efe1ef96bd12cae6c
RESEARCH PRODUCT
Kvantu automātu un meklēšanas algoritmu iespējas un ierobežojumi
Nikolajs Nahimovssubject
Informācijas tehnoloģija datortehnika elektronika telekomunikācijas datorvadība un datorzinātneDatorzinātnesDatorzinātne#description
ANOTĀCIJA Kvantu skaitļošana ir nozare, kas pēta uz kvantu mehānikas likumiem balstīto skaitļošanas modeļu īpašības. Disertācija ir veltīta kvantu skaitļošanas algoritmiskiem aspektiem. Piedāvāti rezultāti trijos virzienos: Kvantu galīgi automāti Analizēta stāvokļu efektivitāte kvantu vienvirziena galīgam automātam. Uzlabota labāka zināmā eksponenciālā atšķirība [AF98] starp kvantu un klasiskajiem galīgajiem automātiem. Grovera algoritma analīze Pētīta Grovera algoritma noturība pret kļūdām. Vispārināts [RS08] loģisko kļūdu modelis un piedāvāti vairāki jauni rezultāti. Kvantu klejošana Pētīta meklēšana 2D režģī izmantojot kvantu klejošanu. Paātrināts [AKR05] kvantu klejošanas meklēšanas algoritms. Atslēgas vārdi: Kvantu galīgi automāti, eksponenciālā atšķirība, Grovera algoritms, noturība pret kļūdām, kvantu klejošana LITERATŪRA [AF98] A. Ambainis, R. Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalizations. Proceedings of the 39th IEEE Conference on Foundations of Computer Science, 332-341, 1998. arXiv:quant-ph/9802062v3 [AKR05] A. Ambainis, J. Kempe, A. Rivosh. Coins make quantum walks faster. Proceedings of SODA’05, 1099-1108, 2005. [RS08] O. Regev, L. Schiff. Impossibility of a Quantum Speed-up with a Faulty Oracle. Proceedings of ICALP’2008, Lecture Notes in Computer Science, 5125:773-781, 2008.
year | journal | country | edition | language |
---|---|---|---|---|
2013-01-01 |