Algebriskās metodes kvantu kriptogrāfijā un galīgo kvantu automātu teorijā

R.Freivalds
 

Projekta ietvaros gūti rezultāti par galīgiem automātiem un vaicājošiem algoritmiem.

Pierādīts, ka determinētiem automātiem var būt eksponenciāli lielāks stāvokļu skaits salīdzinājumā ar varbūtiskiem automātiem. Salīdzinot determinētus automātus ar kvantu automātiem ar jauktiem stāvokļiem, pierādīts, ka stāvokļu skaita atšķirība ir pat vairāk nekā eksponenciāla. Tas ir ļoti nozīmīgs rezultāts par kvantu automātu darbības iespējām.

Turpināti pētījumi par kvantu automātu konstrukciju. Pierādīts, ka kvantu automātu Būla slēgums spēj pazīt jebkuru valodu no R-triviālu valodu klases. Analizētas varbūtisku automātu īpašības, salīdzinot tos ar kvantu automātiem. Pierādīts, ka varbūtiski apgriežami automāti nespēj pazīt to pašu valodu klasi, ko kvantu automāti.

Starptautiski citējamos zinātniskajos žurnālos publicētie zinātniskie raksti (norādīt darba nosaukumu, autorus un publicēšanas avotus): 4

Ruben Agadzanyan, Rūsiņš Freivalds. Size of Quantum Finite State Transducers. Lecture Notes in Computer Science, Vol. 4362, pp. 155-163, Springer, 2007.

A. Belovs, A. Rosmanis, J. Smotrovs. Multi-letter Reversible and Quantum Finite Automata. DLT 2007, Lecture Notes in Computer Science, Vol. 4588, pp. 60-71, Springer, 2007.

R. Freivalds. Non-constructive Methods for Finite Probabilistic Automata. Lecture Notes in Computer Science, Vol. 4588, pp. 169-180, Springer, 2007.

R. Freivalds. Hamming, Permutations and Automata. Lecture Notes in Computer Science, Vol. 4665, pp. 18-29, Springer, 2007.

Citi rezultatīvie rādītāji (Citas LZP atzītās publikācijas): 8

R. Freivalds, M. Ozols, L. Mančinska. Permutation Groups and the Strength of Quantum Finite Automata with Mixed States. Proceedings of the Satellite Workshops of DLT 2007. Workshop on Probabilistic and Quantum Automata, pp. 13-27, TUCS General Publication No 45, 2007.

M. Golovkins, M. Kravtsev, and V. Kravcevs. On a Class of Languages Recognizable by Probabilistic Reversible Decide-and-Halt Automata. Proceedings of the Satellite Workshops of DLT 2007. Workshop on Probabilistic and Quantum Automata, p. 37–54, TUCS General Publication No 45, 2007.

Ilze Dzelme-Bērziņa. First Order Logic and Acceptance Probability of Quantum Finite State Automata. Proceedings of the Satellite Workshops of DLT 2007. Workshop on Probabilistic and Quantum Automata, pp. 29-36, TUCS General Publication No 45, 2007.

L. Lāce. Nondeterministic quantum query with minimal complexity. Proceedings of the Satellite Workshops of DLT 2007. Workshop on Probabilistic and Quantum Automata, pp. 55-64, TUCS General Publication No 45, 2007.

A. Dubrovska. Properties and Application of Nondeterministic Quantum Query Algorithms. SOFSEM 2007, Proccedings Vol. II, pp. 37-49, MatFyz Press, 2007.

A. Dubrovska, T. Mischenko-Slatenkova, A. Rivosh. Quantum Query Algorithms for Certain Problems and Generalization of Algorithm Designing Techniques. Proceedings of the Satellite Workshops of DLT 2007. Workshop on Probabilistic and Quantum Automata, pp. 65-80, TUCS General Publication No 45, 2007.

A. Dubrovska. Quantum Query Algorithms for Certain Functions and General Algorithm Construction Techniques. Proceedings of SPIE Vol. 6573, Quantum Information and Computation V, Article 65730F, SPIE, Bellingham, WA, 2007.

J. Artjuhs, N. Bergs, J. Borzovs, A. Brūvelis, A. Čerņakovs-Neimarks, M. Golovkins, E. Karnītis, I. Krauklis, P. Ķikusts, J. Lauznis, V. Plešs, A. Straujums, A. Vasiļjevs. Pētniecība un inovācija - informātikas nozares īpašās nozīmības pamats, lpp. 48-68, Zinātniski pētnieciskie raksti 3(14), Zinātne, 2007.