Jaunas zinātniskās grupas izveide kvantu skaitļošanā un datorzinātņu teorijā

A. Ambainis
 

Sākts veidot  zinātnisko grupu. Šobrīd tā sastāv no projekta vadītāja A. Ambaiņa un 3 doktorantiem. Veikti pētījumi par kvantu klejošanu, kvantu algoritmiem  un apakšējiem novērtējumiem kvantu skaitļošanai.

Izstrādāti kvantu algoritmi loģikas formulu aprēķinam (publikācija Nr. 5) un meklēšanas uzdevumiem (publikācija Nr. 6), kā arī uzlabotas agrāk zināmās konstrukcijas kvantu automātiem (publikācija Nr. 4). Izpētītas kvantu klejošanas īpašības vairākās situācijās (publikācija Nr. 3).

Šie pētījumi ļaus ar kvantu datora palīdzību atrisināt minētās problēmas ātrāk nekā to var izdarīt ar tradicionālajiem datoriem.

Publicēti vai pieņemti publicēšanai 6 raksti (4 no tiem SCI izdevumos, 2 pārējie starptautiski atzītos konferenču rakstu krājumos). Divos no pētījumiem piedalījušies doktoranti (A. Rivošs publikācijā Nr. 3 un N. Nahimovs publikācijā Nr. 4).

Projekta mērķi pirmajiem 4,5 mēnešiem sasniegti.

1. A. Ambainis, R. Spalek and R. de Wolf. A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs.
Algorithmica, pieemts publicanai, 40 lpp..

2. A. Ambainis. Quantum Random Walks - New Method for Designing Quantum Algorithms. Lecture Notes in Computer Science, vol. 4810, pp. 1-4.

3. A. Ambainis, A. Rivosh. Quantum Walks with Multiple or Moving Marked Locations.Lecture Notes in Computer Science, vol. 4810, pp. 485-496.

4. A. Ambainis, N. Nahimovs. Improved constructions of quantum automata.
Lecture Notes in Computer Science (numurs, kas veltts konferencei TQC08), pieemts publicanai, 10 lpp.

5. A.Ambainis, A. Childs, B. Reichardt, R. Spalek, and S. Zhang. Any AND-OR formula of size N can be evaluated in time N^{+o(1)} on a quantum computer. Proceedings of IEEE Conference on Foundations of Computer Science (FOCS), IEEE Press, 2007, pages 363-372.

6. A. Ambainis. Quantum search with variable times. Proceedings of STACS08 (25th International Symposium on Theoretical Aspects of Computer Science), pieemts publicanai, 12 lpp.